Adleman-Manders-Miller root extraction method revisited

DOI10.1007/978-3-642-34704-7_6MaRDI QIDQ4899196zbMATH OpenOpenAlexFDO

Authors Zhengjun Cao, Qian Sha, Xiao Fan

Publication date 7 January 2013

Published in Information Security and Cryptology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.4877

zbMATH Keywords

higher root extractionsquare root extraction

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Cryptography (94A60)

Abstract: In 1977, Adleman, Manders and Miller had briefly described how to extend their square root extraction method to the general $r$th root extraction over finite fields, but not shown enough details. Actually, there is a dramatic difference between the square root extraction and the general $r$th root extraction because one has to solve discrete logarithms for $r$th 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.

Recommendations

• Efficient computation of roots in finite fields
• Taking roots over high extensions of finite fields
• Trace expression of \(r\)-th root over finite field
• On the computation of square roots in finite fields
• On taking square roots without quadratic nonresidues over finite fields. With an Appendix by Lawrence C. Washington

Cited in

(9)

• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• On the Cipolla-Lehmer type algorithms in finite fields
• Improving the Pocklington and Padró-Sáez cube root algorithm
• A Note on the Insecurity of Cryptosystems Based on Chebyshev Polynomials
• Trace expression of \(r\)-th root over finite field
• Computing square roots faster than the Tonelli-Shanks/Bernstein algorithm
• On the computation of r-th roots in finite fields
• Root extraction in finite abelian groups
• New results on the -hiding assumption and factoring related RSA moduli

This page was built for publication: Adleman-Manders-Miller root extraction method revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899196)