Predicting the Inversive Generator

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

Predicting the Inversive Generator

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

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-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 (u_n) of pseudorandom numbers defined by the relation u_n+1 ≡ au_n ^-1 + b mod p. We show that if b and sufficiently many of the most significant bits of three consecutive values u_n of the ICG are given, one can recover in polynomial time the initial value u₀(even in the case where the coefficient a s unknown) provided that the initial value u₀does 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

Cite this

@article{aa45b06481e54385bf068e3eb8273ba2,

title = "Predicting the Inversive Generator",

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.",

author = "Blackburn, {Simon R.} and Domingo Gomez-Perez and Jaime Gutierrez and Shparlinski, {Igor E.}",

year = "2003",

language = "English",

volume = "2898",

pages = "264--275",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer, Springer Nature",

}

TY - JOUR

T1 - Predicting the Inversive Generator

AU - Blackburn, Simon R.

AU - Gomez-Perez, Domingo

AU - Gutierrez, Jaime

AU - Shparlinski, Igor E.

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33947358812&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:33947358812

VL - 2898

SP - 264

EP - 275

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -

Predicting the Inversive Generator

Abstract

Other files and links

Fingerprint

Cite this