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?)


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.