RECONSTRUCTING POINTS OF SUPERELLIPTIC CURVES OVER A PRIME FINITE FIELD

Let p be a prime and F-p, the finite field with p elements. We show how, when given an superelliptic curve Y-n + f(X) is an element of F-p [X,Y] and an approximation to (v(0), v(1)) is an element of F-p(2) such that v(1)(n) = -f (v(0)), one can recover (v(0), v(1)) efficiently, if the approximation is good enough. As consequence we provide an upper bound on the number of roots of such bivariate polynomials where the roots have certain restrictions. The results has been motivated by the predictability problem for non-linear pseudorandom number generators and, other potential applications to cryptography.