Bulletin of the
Korean Mathematical Society
BKMS

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

Article

HOME ALL ARTICLES View

Bull. Korean Math. Soc. 2019; 56(2): 277-283

Online first article March 12, 2019      Printed March 1, 2019

https://doi.org/10.4134/BKMS.b160769

Copyright © The Korean Mathematical Society.

Improving the Pocklington and Padr\'{o}-S\'{a}ez cube root Algorithm

Gook Hwa Cho, Hyang-Sook Lee

Ewha Womans University; Ewha Womans University

Abstract

In this paper, we present a cube root algorithm using a recurrence relation. Additionally, we compare the implementations of the Pocklington and Padr\'{o}-S\'{a}ez algorithm with the Adleman-Manders-Miller algorithm. With the recurrence relations, we improve the Pocklington and Padr\'{o}-S\'{a}ez algorithm by using a smaller base for exponentiation. Our method can reduce the average number of $\mathbb F_q$ multiplications.

Keywords: cube root algorithm, finite field, Pocklington algorithm, Adleman-Manders-Miller algorithm, Cipolla-Lehmer algorithm

MSC numbers: 11T06, 11Y16, 68W40

Supported by: This research was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education (2009-0093827). The work of G. H. Cho was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education (2018R1D1A1B07041716).