Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

Recovering zeros of polynomials modulo a prime


Authors: Domingo Gómez and Jaime Gutierrez
Journal: Math. Comp. 83 (2014), 2953-2965
MSC (2010): Primary 11H06, 11Y16, 12Y05; Secondary 11K16, 11T71
DOI: https://doi.org/10.1090/S0025-5718-2014-02808-1
Published electronically: February 7, 2014
MathSciNet review: 3246817
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ p$ be a prime and $ \mathbb{F}_p$ the finite field with $ p$ elements. We show how, when given an irreducible bivariate polynomial $ F \in \mathbb{F}_p[X,Y]$ and an approximation to a zero, one can recover the root efficiently, if the approximation is good enough. The strategy can be generalized to polynomials in the variables $ X_1,\ldots ,X_m$ over the field $ \mathbb{F}_p$. These results have been motivated by the predictability problem for nonlinear pseudorandom number generators and other potential applications to cryptography.


References [Enhancements On Off] (What's this?)

  • [1] L. Babai, On Lovász' lattice reduction and the nearest lattice point problem, Combinatorica 6 (1986), no. 1, 1-13. MR 856638 (88a:68049), https://doi.org/10.1007/BF02579403
  • [2] Simon R. Blackburn, Domingo Gomez-Perez, Jaime Gutierrez, and Igor E. Shparlinski, Predicting nonlinear pseudorandom number generators, Math. Comp. 74 (2005), no. 251, 1471-1494. MR 2137013 (2005m:11142), https://doi.org/10.1090/S0025-5718-04-01698-9
  • [3] Simon R. Blackburn, Domingo Gomez-Perez, Jaime Gutierrez, and Igor E. Shparlinski, Reconstructing noisy polynomial evaluation in residue rings, J. Algorithms 61 (2006), no. 2, 47-59. MR 2281416 (2007j:11168), https://doi.org/10.1016/j.jalgor.2004.07.002
  • [4] Johannes Blömer and Alexander May, A tool kit for finding small roots of bivariate polynomials over the integers, Advances in cryptology--EUROCRYPT 2005, Lecture Notes in Comput. Sci., vol. 3494, Springer, Berlin, 2005, pp. 251-267. MR 2352192 (2008h:94046), https://doi.org/10.1007/11426639_15
  • [5] Dan Boneh, Shai Halevi, and Nick Howgrave-Graham, The modular inversion hidden number problem, Advances in cryptology--ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., vol. 2248, Springer, Berlin, 2001, pp. 36-51. MR 1934514 (2003h:94022), https://doi.org/10.1007/3-540-45682-1_3
  • [6] Joan Boyar, Inferring sequences produced by pseudo-random number generators, J. Assoc. Comput. Mach. 36 (1989), no. 1, 129-141. MR 1072416 (91g:68035), https://doi.org/10.1145/58562.59305
  • [7] Don Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology 10 (1997), no. 4, 233-260. MR 1476612 (99b:94027), https://doi.org/10.1007/s001459900030
  • [8] Don Coppersmith, Finding small solutions to small degree polynomials, Cryptography and lattices (Providence, RI, 2001) Lecture Notes in Comput. Sci., vol. 2146, Springer, Berlin, 2001, pp. 20-31. MR 1903884 (2003f:11034), https://doi.org/10.1007/3-540-44670-2_3
  • [9] Jean-Sébastien Coron, Finding small roots of bivariate integer polynomial equations: a direct approach, Advances in cryptology--CRYPTO 2007, Lecture Notes in Comput. Sci., vol. 4622, Springer, Berlin, 2007, pp. 379-394. MR 2423860 (2009f:12001), https://doi.org/10.1007/978-3-540-74143-5_21
  • [10] Alan M. Frieze, Johan Håstad, Ravi Kannan, Jeffrey C. Lagarias, and Adi Shamir, Reconstructing truncated integer variables satisfying linear congruences, SIAM J. Comput. 17 (1988), no. 2, 262-280. Special issue on cryptography. MR 935340 (89d:11115), https://doi.org/10.1137/0217016
  • [11] Domingo Gómez, Jaime Gutierrez, and Álvar Ibeas, Attacking the Pollard generator, IEEE Trans. Inform. Theory 52 (2006), no. 12, 5518-5523. MR 2300710 (2007m:94160), https://doi.org/10.1109/TIT.2006.885451
  • [12] Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics: Study and Research Texts, vol. 2, Springer-Verlag, Berlin, 1988. MR 936633 (89m:90135)
  • [13] Jaime Gutierrez and Álvar Ibeas, Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits, Des. Codes Cryptogr. 45 (2007), no. 2, 199-212. MR 2341883 (2008g:11204), https://doi.org/10.1007/s10623-007-9112-3
  • [14] Nicholas Howgrave-Graham, Finding small roots of univariate modular equations revisited, Cryptography and coding (Cirencester, 1997) Lecture Notes in Comput. Sci., vol. 1355, Springer, Berlin, 1997, pp. 131-142. MR 1660500 (99j:94049), https://doi.org/10.1007/BFb0024458
  • [15] Ellen Jochemsz and Alexander May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, Advances in cryptology--ASIACRYPT 2006, Lecture Notes in Comput. Sci., vol. 4284, Springer, Berlin, 2006, pp. 267-282. MR 2444641 (2009h:94128), https://doi.org/10.1007/11935230_18
  • [16] Antoine Joux and Jacques Stern, Lattice reduction: a toolbox for the cryptanalyst, J. Cryptology 11 (1998), no. 3, 161-185. MR 1633944 (99c:94031), https://doi.org/10.1007/s001459900042
  • [17] Ravi Kannan, Minkowski's convex body theorem and integer programming, Math. Oper. Res. 12 (1987), no. 3, 415-440. MR 906415 (89c:90078), https://doi.org/10.1287/moor.12.3.415
  • [18] Hugo Krawczyk, How to predict congruential generators, J. Algorithms 13 (1992), no. 4, 527-545. MR 1187200 (93g:65013), https://doi.org/10.1016/0196-6774(92)90054-G
  • [19] A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515-534. MR 682664 (84a:12002), https://doi.org/10.1007/BF01457454
  • [20] Daniele Micciancio and Shafi Goldwasser, Complexity of lattice problems, The Kluwer International Series in Engineering and Computer Science, 671, Kluwer Academic Publishers, Boston, MA, 2002. A cryptographic perspective. MR 2042139 (2004m:94067)
  • [21] Phong Q. Nguyen and Jacques Stern, Lattice reduction in cryptology: an update, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 85-112. MR 1850600 (2002h:94064), https://doi.org/10.1007/10722028_4
  • [22] Phong Q. Nguyen and Jacques Stern, The two faces of lattices in cryptology, Cryptography and lattices (Providence, RI, 2001) Lecture Notes in Comput. Sci., vol. 2146, Springer, Berlin, 2001, pp. 146-180. MR 1903893 (2003d:94082), https://doi.org/10.1007/3-540-44670-2_12
  • [23] Igor Shparlinski, Cryptographic applications of analytic number theory, Progress in Computer Science and Applied Logic, vol. 22, Birkhäuser Verlag, Basel, 2003. Complexity lower bounds and pseudorandomness. MR 1954519 (2004h:94049)
  • [24] Joseph H. Silverman (ed.), Cryptography and lattices, Lecture Notes in Computer Science, vol. 2146, Springer-Verlag, Berlin, 2001. MR 1903881 (2002m:11002)
  • [25] Serguei A. Stepanov, Arithmetic of algebraic curves, Monographs in Contemporary Mathematics, Consultants Bureau, New York, 1994. Translated from the Russian by Irene Aleksanova. MR 1321599 (95j:11055)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11H06, 11Y16, 12Y05, 11K16, 11T71

Retrieve articles in all journals with MSC (2010): 11H06, 11Y16, 12Y05, 11K16, 11T71


Additional Information

Domingo Gómez
Affiliation: Faculty of Science, University of Cantabria, E-39071 Santander, Spain
Email: gomezd@unican.es

Jaime Gutierrez
Affiliation: E.T.S. Industrial Engineering and Telecommunications, University of Cantabria, E-39071 Santander, Spain
Email: aime.gutierrez@unican.es

DOI: https://doi.org/10.1090/S0025-5718-2014-02808-1
Received by editor(s): October 29, 2012
Received by editor(s) in revised form: January 16, 2013, and February 6, 2013
Published electronically: February 7, 2014
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society