Attacking the Pollard Generator
Domingo Gómez‐Pérez, Jaime Gutiérrez, lvar Ibeas · IEEE Transactions on Information Theory · 2006
Let p be a prime and let c be an integer modulo p. The Pollard generator is a sequence (un) of pseudorandom numbers defined by the relation un+1equivun2+c mod p. It is shown that if c and 9/14 of the most significant bits of two consecutive values un,un+1of the Pollard generator are given, one can recover in polynomial time the initial value u0with a probabilistic algorithm. This result is an improvement of a theorem in a recent paper which requires that 2/3 of the most significant bits be known