Reconstructing noisy polynomial evaluation in residue rings

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)

Abstract

Let q > 1 be an integer and let a and b be elements of the residue ring Zq of integers modulo q. We show how, when given a polynomial f ∈ Zq [X] and approximations to v0, v1 ∈ Zq such that v1 ≡ f (v0) mod q one can recover v0 and v1 efficiently. This result has direct applications to predicting the polynomial congruential generator: a sequence (vn) of pseudorandom numbers defined by the relation vn + 1 ≡ f (vn) mod q for some polynomial f ∈ Zq [X]. The applications lead to analogues of results known for the linear congruential generator xn + 1 ≡ a xn + b mod q, although the results are much more restrictive due to nonlinearity of the problem.

Original languageEnglish
Pages (from-to)47-59
Number of pages13
JournalJournal of Algorithms
Volume61
Issue number2
DOIs
Publication statusPublished - Nov 2006

Fingerprint

Dive into the research topics of 'Reconstructing noisy polynomial evaluation in residue rings'. Together they form a unique fingerprint.

Cite this