Improving the Pocklington and Padr\'{o}-S\'{a}ez cube root Algorithm
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
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.
참고문헌 (9)
- L. Adleman, "On taking roots in nite elds", 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977), pp.175~178 (1977), IEEE Comput. Sci.
- Z. Cao, "Information security and cryptology", pp.77~85 (2012), Springer
- M. Cipolla, "Rendiconto dell`Accademia Scienze Fisiche e Matematiche", pp.154~163 (1903)
- G. Heo, "Remarks on the Pocklington and Padro-Saez cube root algorithm in Fq", Electronics Letters, 50(14), pp.1002~1003 (2014)
- D. H. Lehmer, "Studies in Number Theory", pp.117~151 (1969), Math. Assoc. Amer, Prentice-Hall
- C. Padro, "Taking cube roots in Zm", Appl. Math. Lett, 15(6), pp.703~708 (2002)
- H. C. Pocklington, "The direct solution of the quadratic and cubic binomial congruences with prime moduli", Proceedings of the Cambridge Philosophical Society, 19, pp.57~59 (1917)
- D. Shanks, "Five number-theoretic algorithms", Proceedings of the Second Manitoba Conference on Numerical Mathematics, pp.51~70 (1972), Univ. Manitoba
- A. Tonelli, "Bemerkung uber die Auosung quadratischer Congruenzen, Nachrichten von der Konigl", Gesellschaft der Wissenschaften und der Georg-Augusts-Universitat zu Gottingen, 344~346 (1891)