본문 바로가기
KERD
논문KCI 등재

POLYNOMIAL REPRESENTATIONS FOR n-TH ROOTS IN FINITE FIELDS

이향숙|김빛나라|장승환
대한수학회 (The Korean Mathematical Society)|2015.01|대한수학회지 (Journal of the KMS)|제52권 제1호|pp. 209-224

2

조회

0

다운로드

0

인용

0

참고문헌

키워드

finite fieldscube rootsn-th roots
주제분류수학

초록

Computing square, cube and n-th roots in general, in finite fields, are important computational problems with significant applications to cryptography. One interesting approach to computational problems is by using polynomial representations. Agou, Del´eglise and Nicolas proved results concerning the lower bounds for the length of polynomials representing square roots modulo a prime p. We generalize the results by considering n-th roots over finite fields for arbitrary n > 2.

Abstract

Computing square, cube and n-th roots in general, in finite fields, are important computational problems with significant applications to cryptography. One interesting approach to computational problems is by using polynomial representations. Agou, Del´eglise and Nicolas proved results concerning the lower bounds for the length of polynomials representing square roots modulo a prime p. We generalize the results by considering n-th roots over finite fields for arbitrary n > 2.

참고문헌 (23)

  1. L. M. Adleman, "On taking roots in finite fields", Proceedings of 18th Annual Symposium on Foundations of Computer Science, pp.175~178 (1977), IEEE Comput. Sci.
  2. S. J. Agou, "Short polynomial representations for square roots modulo p", Des. Codes Cryptogr, 28(1), pp.33~44 (2003)
  3. P. S. L. M. Barreto, "Efficient computation of roots in finite fields", Des. Codes Cryptogr, 39(2), pp.275~280 (2006)
  4. M. Cipolla, "Un metodo per la risoluzione della congruenza di secondo grado", Napoli Rend, 9, pp.154~163 (1903)
  5. D. Coppersmith, "On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping", J. Cryptology, 13(3), pp.339~360 (2000)
  6. J. von zur Gathen, "Modern Computer Algebra" (2013), Cambridge University Press
  7. E. Kiltz, "On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping", Bull. Aust. Math. Soc, 69(2), pp.305~315 (2004)
  8. T. Lange, "Polynomial interpolation of the elliptic curve and XTR discrete logarithm, Computing and combinatorics", Lecture Notes in Comput. Sci., 2387, pp.137~143 (2002), Springer
  9. T. Lange, "Interpolation of the discrete logarithm in Fq by Boolean functions and by polynomials in several variables modulo a divisor of q−1", Discrete Appl. Math, 128(1), pp.193~206 (2003)
  10. T. Lange, "Interpolation of the elliptic curve Diffie-Hellman mapping, Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 2003)", Lecture Notes in Comput. Sci, 2643, pp.51~60 (2003), Springer
  11. D. H. Lehmer, "Studies in number theory, volume 6 of MAA Studies in Mathematics", pp.117~151 (1969), Prentice-Hall
  12. R. Lidl, "Finite fields, Encyclopedia of Mathematics and its Applications", pp.20~ (1983), Addison-Wesley Publishing Company
  13. G. L. Mullen, "A polynomial representation for logarithms in GF(q)", Acta Arith, 47(3), pp.255~261 (1986)
  14. H. Niederreiter, "A short proof for explicit formulas for discrete logarithms in finite fields", Appl. Algebra Engrg. Comm. Comput, 1(1), pp.55~57 (1990)
  15. T. Satoh, "On polynomial interpolations related to Verheul homomorphisms", LMS J. Comput. Math, 9, pp.135~158 (2006)
  16. T. Satoh, "On degrees of polynomial interpolations related to elliptic curve cryptography, Coding and cryptography", Lecture Notes in Comput. Sci., 3969, pp.155~163 (2006), Springer
  17. T. Satoh, "On pairing inversion problems, Pairing-based cryptography-Pairing 2007", Lecture Notes in Comput. Sci., 4575, pp.317~328 (2007), Springer
  18. T. Satoh, "Closed formulae for the Weil pairing inversion", Finite Fields Appl, 14(3), pp.743~765 (2008)
  19. R. Schoof, "Elliptic curves over finite fields and the computation of square roots mod p", Math. Comp, 44(170), pp.483~494 (1985)
  20. D. Shanks, "Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics", Congressus Numerantium, 7, pp.51~70 (1972), Utilitas Math.
  21. A. Tonelli, "Bemerkung ¨uber die Aufl¨osung quadratischer Congruenzen, Nachrichten von der K¨oniglichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universit¨at zu G¨ottingen", 344~346 (1891)
  22. Z.-X.Wan, "A shorter proof for an explicit formula for discrete logarithms in finite fields", Discrete Math, 308(21), pp.4914~4915 (2008)
  23. A. Winterhof, "Polynomial interpolation of the discrete logarithm", Des. Codes Cryptogr, 25(1), pp.63~72 (2002)

관련 논문AI추천

Trace expression of $r$-th root over finite field구남훈, 권순학, 조국화대한수학회 · 대한수학회지2020 · 제57권 제4호Certain cubic polynomials over finite fields김재문, 김형돈, 이익권대한수학회 · 대한수학회지2009 · 제46권 제1호On the Pocklington-Peralta square root algorithm in finite fields구남훈, 권순학, 김창헌대한수학회 · 대한수학회보2022 · 제59권 제6호Improving the Pocklington and Padr\'{o}-S\'{a}ez cube root Algorithm이향숙, 조국화대한수학회 · 대한수학회보2019 · 제56권 제2호Generating certain quintic irreducible polynomials over finite fields김기태, 안영우강원경기수학회 · 한국수학논문집2011 · 제19권 제3호SUMS OF (pr + 1)-TH POWERS IN THE POLYNOMIAL RING F pm[T]Mireille Car대한수학회 · 대한수학회지2012 · 제49권 제6호

이 간행물의 다른 논문 (12건)

ON v-MAROT MORI RINGS AND C-RINGSSebastian Ramacher, Alfred Geroldinger, Andreas Reinhartpp. 1-21EXPANDING THE CONVERGENCE DOMAIN FOR CHUN-STANICA-NETA FAMILY OF THIRD ORDER METHODS IN BANACH SPACESAngel Alberto Magrenan, Ioannis Konstantinos Argyros, Santhosh Georgepp. 23-41BROYDEN’S METHOD FOR OPERATORS WITH REGULARLY CONTINUOUS DIVIDED DIFFERENCESAnatoly M. Galperinpp. 43-65REGULAR INJECTIVITY AND EXPONENTIABILITY IN THE SLICE CATEGORIES OF ACTIONS OF POMONOIDS ON POSETSFarideh Farsad, Ali Madanshekafpp. 67-80FINITE GROUPS WHOSE INTERSECTION GRAPHS ARE PLANARSelcuk Kayacan, Ergun Yaraneripp. 81-96
원문 보기