A refinement of Müller's cube root algorithm
- 주제(키워드) Cipolla-Lehmer algorithm , Cube root , Finite field , Linear recurrence relation
- 관리정보기술 faculty
- 등재 SCIE, SCOPUS
- 발행기관 Academic Press Inc.
- 발행년도 2020
- 총서유형 Journal
- URI http://www.dcollection.net/handler/ewha/000000168809
- 본문언어 영어
- Published As https://dx.doi.org/10.1016/j.ffa.2020.101708
초록/요약
Let p be a prime such that p≡1(mod3). Let c be a cubic residue (modp) such that [Formula presented]. In this paper, we present a refinement of Müller's algorithm for computing a cube root of c [11], which also improves Williams' [14,15] Cipolla-Lehmer type algorithms. Under the assumption that a suitable irreducible polynomial of degree 3 is given, Müller gave a cube root algorithm which requires 8.5logp modular multiplications. Our algorithm requires only 7.5logp modular multiplications and is based on the recurrence relations arising from the irreducible polynomial h(x)=x3+ct3x−ct3 for some integer t. © 2020 Elsevier Inc.
more