## Cryptology ePrint Archive: Report 2009/233

A strategy for recovering roots of bivariate polynomials modulo a prime

Paula Bustillo and Domingo Gomez and 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.

Category / Keywords: applications / number theory, lattices and crypto