@article{cd04ec0a33f94f3aa52c72c981427fb2,

title = "A refinement of M{\"u}ller's cube root algorithm",

abstract = "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{\"u}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{\"u}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.",

keywords = "Cipolla-Lehmer algorithm, Cube root, Finite field, Linear recurrence relation",

author = "Cho, {Gook Hwa} and Soonhak Kwon and Lee, {Hyang Sook}",

note = "Funding Information: The authors would like to thank the anonymous reviewers for their kind comments and valuable suggestions. This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (No. 2019R1A6A1A11051177 ). Gook Hwa Cho was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (No. NRF-2018R1D1A1B07041716 ). Soonhak Kwon was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (No. 2016R1D1A1B03931912 and No. 2016R1A5A1008055 ). Hyang-Sook Lee was also supported by the Korea government ( MSIT ) (No. NRF-2018R1A2A1A05079095 ). Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

year = "2020",

month = oct,

doi = "10.1016/j.ffa.2020.101708",

language = "English",

volume = "67",

journal = "Finite Fields and their Applications",

issn = "1071-5797",

publisher = "Academic Press Inc.",

}