On the Cipolla-Lehmer type algorithms in finite fields

DOI10.1007/S00200-018-0362-2MaRDI QIDQ2631927zbMATH OpenOpenAlexFDO

Authors Gook Hwa Cho, Byeonghwan Go, Chang Heon Kim, Namhun Koo, Soonhak Kwon

Publication date 16 May 2019

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00200-018-0362-2

zbMATH Keywords

\(r\)-th rootAdleman-Manders-Miller algorithmCipolla-Lehmer algorithmfinite fieldprimitive root

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• New cube root algorithm based on the third order linear recurrence relations in finite fields
• On the computation of square roots in finite fields
• scientific article; zbMATH DE number 2154289
• Trace expression of \(r\)-th root over finite field
• A Refinement of H. C. Williams' qth Root Algorithm

Cites work

• A complete generalization of Atkin's square root algorithm
• A Refinement of H. C. Williams' qth Root Algorithm
• A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)
• Adleman-Manders-Miller root extraction method revisited
• Efficient computation of roots in finite fields
• Fast polynomial factorization and modular composition
• scientific article; zbMATH DE number 3480679 (Why is no real title available?)
• scientific article; zbMATH DE number 1253982 (Why is no real title available?)
• scientific article; zbMATH DE number 1305523 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 3341170 (Why is no real title available?)
• scientific article; zbMATH DE number 3417539 (Why is no real title available?)
• Improved generalized Atkin algorithm for computing square roots in finite fields
• New cube root algorithm based on the third order linear recurrence relations in finite fields
• On taking square roots without quadratic nonresidues over finite fields. With an Appendix by Lawrence C. Washington
• On the computation of square roots in finite fields
• Structure computation and discrete logarithms in finite abelian \(p\)-groups
• Taking cube roots in \(\mathbb Z_{m}\)
• Taking roots over high extensions of finite fields

Cited in

(5)

• A Refinement of H. C. Williams' qth Root Algorithm
• scientific article; zbMATH DE number 4153897 (Why is no real title available?)
• scientific article; zbMATH DE number 2154289 (Why is no real title available?)
• Trace expression of \(r\)-th root over finite field
• On the computation of r-th roots in finite fields

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: On the Cipolla-Lehmer type algorithms in finite fields

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