×

Trace expression of \(r\)-th root over finite field. (English) Zbl 1478.11143

Summary: Efficient computation of \(r\)-th root in \(\mathbb{F}_q\) has many applications in computational number theory and many other related areas. We present a new \(r\)-th root formula which generalizes Müller’s result on square root, and which provides a possible improvement of the Cipolla-Lehmer type algorithms for general case. More precisely, for given \(r\)-th power \(c\in\mathbb{F}_q\), we show that there exists \(\alpha\in\mathbb{F}_{q^r}\) such that
\[ Tr\left(\alpha^\frac{(\sum_{i=0}^{r-1}q^i)-r}{r^2}\right)^r=c, \]
where \(Tr(\alpha)=\alpha+\alpha^q+\alpha^{q^2}+\cdots +\alpha^{q^{r-1}}\) and \(\alpha\) is a root of certain irreducible polynomial of degree \(r\) over \(\mathbb{F}_q\).

MSC:

11T06 Polynomials over finite fields
11Y16 Number-theoretic algorithms; complexity
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. Adleman, K. Manders, and G. Miller,On taking roots in finite fields, in 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977), 175-178, IEEE Comput. Sci., Long Beach, CA, 1977.
[2] A. O. L. Atkin,Probabilistic primality testing, summary by F. Morain, Inria Research Report1779(1992), 159-163,
[3] D. Bernstein,Faster square root in annoying finite field, Preprint, Available from http://cr.yp.to/papers/sqroot.pdf, 2001.
[4] Z. Cao, Q. Sha, and X. Fan,Adleman-Manders-Miller root extraction method revisited, in Information security and cryptology, 77-85, Lecture Notes in Comput. Sci.,7537, Springer, Heidelberg, 2012.https://doi.org/10.1007/978-3-642-34704-7_6 · Zbl 1292.94044
[5] G. H. Cho, N. Koo, E. Ha, and S. Kwon,,New cube root algorithm based on the third order linear recurrence relations in finite fields, Des. Codes Cryptogr.75(2015), no. 3, 483-495.https://doi.org/10.1007/s10623-013-9910-8 · Zbl 1361.11083
[6] M. Cipolla,Un metodo per la risolutione della congruenza di secondo grado, Rendiconto dell’Accademia Scienze Fisiche e Matematiche, Napoli, Ser. 3,9(1903), 154-163. · JFM 34.0219.02
[7] I. B. Damg˚ard and G. S. Frandsen,Efficient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers, J. Symbolic Comput.39(2005), no. 6, 643-652. https://doi.org/10.1016/j.jsc.2004.02.006 · Zbl 1156.11346
[8] K. J. Giuliani and G. Gong,A new algorithm to compute remote terms in special types of characteristic sequences, in Sequences and their applications—SETA 2006, 237-247, · Zbl 1152.94382
[9] G. Gong and L. Harn,Public-key cryptosystems based on cubic finite field extensions, IEEE Trans. Inform. Theory45(1999), no. 7, 2601-2605.https://doi.org/10.1109/ 18.796413 · Zbl 0986.94027
[10] F. Kong, Z. Cai, J. Yu, and D. Li,Improved generalized Atkin algorithm for computing square roots in finite fields, Inform. Process. Lett.98(2006), no. 1, 1-5.https://doi. org/10.1016/j.ipl.2005.11.015 · Zbl 1195.11166
[11] D. H. Lehmer,Computer technology applied to the theory of numbers, in Studies in Number Theory, 117-151, Math. Assoc. Amer. (distributed by Prentice-Hall, Englewood Cliffs, N.J.), 1969. · Zbl 0215.06404
[12] R. Lidl and H. Niederreiter,Finite fields, second edition, Encyclopedia of Mathematics and its Applications,20, Cambridge University Press, Cambridge, 1997.
[13] S. Lindhurst,An analysis of Shanks’s algorithm for computing square roots in finite fields, in Number theory (Ottawa, ON, 1996), 231-242, CRM Proc. Lecture Notes,19, Amer. Math. Soc., Providence, RI, 1999. · Zbl 0928.11055
[14] A. J. Menezes, I. F. Blake, X. Gao, R. C. Mullin, S. A. Vanstone, and T. Yaghoobian, Applications of finite fields, The Kluwer International Series in Engineering and Computer Science,199, Kluwer Academic Publishers, Boston, MA, 1993.https://doi.org/ 10.1007/978-1-4757-2226-0
[15] S. M¨uller,On the computation of square roots in finite fields, Des. Codes Cryptogr.31 (2004), no. 3, 301-312.https://doi.org/10.1023/B:DESI.0000015890.44831.e2 · Zbl 1052.11084
[16] NIST,Digital Signature Standard, Federal Information Processing Standard 186-3, National Institute of Standards and Technology, Available from http://csrc.nist.gov/ publications/fips/, 2000.
[17] D. Shanks,Five number-theoretic algorithms, in Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972), 51-70. Congressus Numerantium, VII, Utilitas Math., Winnipeg, MB, 1973. · Zbl 0307.10015
[18] I. Shparlinski,Finite fields:Theory and computation, Springer, 1999. · Zbl 0967.11052
[19] A.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.