Abstract
Let p be a prime and let a and b be integers modulo p. The inversive congruential generator (ICG) is a sequence (un) of pseudorandom numbers defined by the relation un+1 ≡ aun -1 + b mod p. We show that if b and sufficiently many of the most significant bits of three consecutive values un of the ICG are given, one can recover in polynomial time the initial value u0(even in the case where the coefficient a s unknown) provided that the initial value u0does not lie in a certain small subset of exceptional values.
Original language | English |
---|---|
Pages (from-to) | 264-275 |
Number of pages | 12 |
Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
Volume | 2898 |
Publication status | Published - 2003 |