In this paper, we present a cube root algorithm using a recurrence relation. Additionally, we compare the implementations of the Pocklington and Padró-Sáez algorithm with the Adleman-Manders-Miller algorithm. With the recurrence relations, we improve the Pocklington and Padró-Sáez algorithm by using a smaller base for exponentiation. Our method can reduce the average number of Fq multiplications.
Bibliographical noteFunding Information:
Acknowledgements. 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).
© 2019 Korean Mathematical Society.
- Adleman-Manders-Miller algorithm
- Cipolla-Lehmer algorithm
- Cube root algorithm
- Finite field
- Pocklington algorithm