2011/11/21 by Zhengjun Cao, Cao, Zhengjun, Qian Sha +3
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Symbolic Computation (cs.SC) #cs.SC #math.NT
paper · pdf · doi:10.48550/arxiv.1111.4877
10 pages
arxiv created 2011/11/21 · arxiv updated 2011/11/22
In 1977, Adleman, Manders and Miller had briefly described how to extend their square root extraction method to the general rth root extraction over finite fields, but not shown enough details. Actually, there is a dramatic difference between the square root extraction and the general rth root extraction because one has to solve discrete logarithms for rth root extraction. In this paper, we clarify their method and analyze its complexity. Our heuristic presentation is helpful to grasp the method entirely and deeply.