Title :
Inferring a sequence generated by a linear congruence
Author :
Plumstead, Joan B. ; Plumstead, Joan B. ; Plumstead, Joan B. ; Plumstead, Joan B.
Abstract :
Suppose it is known that {X0, X1,...,Xn} is produced by a pseudo-random number generator of the form Xi+1 = aXi + b mod m, but a, b, and m are unknown. Can one efficiently predict the remainder of the sequence with knowledge of only a few elements from that sequence? This question is answered in the affirmative and an algorithm is given.
Keywords :
Algorithm design and analysis; Computer science; Cryptography; Data analysis; Error correction; Inference algorithms; Power generation; Random number generation; Sections; Tiles;
Conference_Titel :
Foundations of Computer Science, 1982. SFCS '08. 23rd Annual Symposium on
Conference_Location :
Chicago, IL, USA
DOI :
10.1109/SFCS.1982.73
