Bull. Korean Math. Soc. 2022; 59(6): 1523-1537
Online first article July 12, 2022 Printed November 30, 2022
https://doi.org/10.4134/BKMS.b210870
Copyright © The Korean Mathematical Society.
Chang Heon Kim, Namhun Koo , Soonhak Kwon
Sungkyunkwan University; Ewha Womans University; Sungkyunkwan University
We present a new square root algorithm in finite fields which is a variant of the Pocklington-Peralta algorithm. We give the complexity of the proposed algorithm in terms of the number of operations (multiplications) in finite fields, and compare the result with other square root algorithms, the Tonelli-Shanks algorithm, the Cipolla-Lehmer algorithm, and the original Pocklington-Peralta square root algorithm. Both the theoretical estimation and the implementation result imply that our proposed algorithm performs favorably over other existing algorithms. In particular, for the NIST suggested field P-224, we show that our proposed algorithm is significantly faster than other proposed algorithms.
Keywords: Square root algorithm, finite field, Pocklington-Peralta algorithm, Tonelli-Shanks algorithm, Cipolla-Lehmer algorithm
MSC numbers: 11T06, 11Y16, 68W40
Supported by: This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIP) (No.~2016R1A5A1008055). Namhun Koo was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No.~2021R1C1C2003888). Soonhak Kwon was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No.~2019R1F1A1058920 and No.~2021R1F1A1050721).
2019; 56(2): 277-283
2022; 59(3): 781-787
2017; 54(5): 1779-1801
2004; 41(1): 19-25
© 2022. The Korean Mathematical Society. Powered by INFOrang Co., Ltd