Trace expression of $r$-th root over finite field
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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\"{u}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$.
Abstract
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\"{u}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$.
참고문헌 (19)
- L. Adleman, "On taking roots in nite elds", 18th Annual Symposium on Foundations of Computer Science, pp.175~178 (1977), IEEE Comput. Sci
- Probabilistic primality testing, "A. O. L. Atkin", 159~163, pp.Inria Research Report 1779 (1992)
- "Faster square root in annoying nite eld" (2001)[URL]
- Z. Cao, "Adleman-Manders-Miller root extraction method revisited, in Information security and cryptology", Lecture Notes in Comput. Sci., 7537, pp.77~85 (2012), Springer[DOI]
- G. H. Cho, "New cube root algorithm based on the third order linear recurrence relations in nite elds", Des. Codes Cryptogr, 75(3), pp.483~495 (2015)[DOI]
- M. Cipolla, "Un metodo per la risolutione della congruenza di secondo grado, Rendiconto dell'Accademia Scienze Fisiche e Matematiche", Napoli, Ser, 3(9), pp.154~163 (1903)
- I. B. Damgard, "Ecient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers", J. Symbolic Comput, 39(6), pp.643~652 (2005)[DOI]
- K. J. Giuliani, "A new algorithm to compute remote terms in special types of characteristic sequences, in Sequences and their applications|SETA 2006", Lecture Notes in Comput. Sci., 4086, pp.237~247 (2006), Springer[DOI]
- G. Gong, "Public-key cryptosystems based on cubic nite eld extensions", IEEE Trans. Inform. Theory, 45(7), pp.2601~2605 (1999)[DOI]
- F. Kong, "Improved generalized Atkin algorithm for computing square roots in nite elds", Inform. Process. Lett, 98(1), pp.1~5 (2006)[DOI]
- D. H. Lehmer, "Computer technology applied to the theory of numbers, in Studies in Number Theory", Math. Assoc. Amer, pp.117~151 (1969)
- R. Lidl, "Encyclopedia of Mathematics and its Applications, 20" (1997), Cambridge University Press
- S. Lindhurst, "An analysis of Shanks's algorithm for computing square roots in nite elds, in Number theory", CRM Proc. Lecture Notes, 19, pp.231~242 (1996), Amer. Math. Soc
- A. J. Menezes, "Applications of nite elds", The Kluwer International Series in Engineering and Computer Science, 199 (1993), Kluwer Academic Publishers
- S. Muller, "On the computation of square roots in nite elds", Des. Codes Cryptogr, 31(3), pp.301~312 (2004)[DOI]
- "Digital Signature Standard, Federal Information Processing Standard 186-3" (2000)[URL]
- D. Shanks, "Five number-theoretic algorithms", Proceedings of the Second Manitoba Conference on Numerical Mathematics, pp.51~70 (1972)
- I. Shparlinski, "Finite elds: Theory and computation" (1999), Springer
- A. Tonelli, "Bemerkung uber die Auosung quadratischer Congruenzen", Gottinger Nachrichten, 344~346 (1891)