Paper 2009/233

A strategy for recovering roots of bivariate polynomials modulo a prime

Paula Bustillo, Domingo Gomez, Jaime Gutierrez, and Alvar Ibeas

Abstract

Let $p$ be a prime and $\F_p$ the finite field with $p$ elements. We show how, when given an irreducible bivariate polynomial $f \in \F_p[X,Y]$ and approximations to $(v_0,v_1) \in \F_p^2$ such that $f(v_0,v_1)=0 $, one can recover $(v_0,v_1)$ efficiently, if the approximations are good enough. This result has been motivated by the predictability problem for non-linear pseudorandom number generators and, other potential applications to cryptography.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Unknown where it was published
Keywords
number theorylattices and crypto
Contact author(s)
jaime gutierrez @ unican es
History
2009-05-30: received
Short URL
https://ia.cr/2009/233
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/233,
      author = {Paula Bustillo and Domingo Gomez and Jaime Gutierrez and Alvar Ibeas},
      title = {A strategy for recovering  roots of  bivariate polynomials modulo a prime},
      howpublished = {Cryptology ePrint Archive, Paper 2009/233},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/233}},
      url = {https://eprint.iacr.org/2009/233}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.