Predicting the Inversive Generator

Simon R. Blackburn*, Domingo Gomez-Perez, Jaime Gutierrez, Igor E. Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)

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 languageEnglish
Pages (from-to)264-275
Number of pages12
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2898
Publication statusPublished - 2003

Fingerprint

Dive into the research topics of 'Predicting the Inversive Generator'. Together they form a unique fingerprint.

Cite this