Bulletin of the
Korean Mathematical Society
BKMS

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016

Ahead of Print Articles

HOME VIEW ARTICLES View

Bull. Korean Math. Soc.

Published online July 12, 2022

Copyright © The Korean Mathematical Society.

On the Pocklington-Peralta Square Root Algorithm in Finite Fields

Chang Heon Kim, Namhun Koo, and Soonhak Kwon

Sungkyunkwan University, Ewha Womans University

Abstract

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

Share this article on :