Name
Abstract | ||
|---|---|---|
Let q1 be an integer and let a and b be elements of the residue ring Z"q of integers modulo q. We show how, when given a polynomial f@?Z"q[X] and approximations to v"0,v"1@?Z"q such that v"1=f(v"0)modq one can recover v"0 and v"1 efficiently. This result has direct applications to predicting the polynomial congruential generator: a sequence (v"n) of pseudorandom numbers defined by the relation v"n"+"1=f(v"n)modq for some polynomial f@?Z"q[X]. The applications lead to analogues of results known for the linear congruential generator x"n"+"1=ax"n+bmodq, although the results are much more restrictive due to nonlinearity of the problem. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.jalgor.2004.07.002 | J. Algorithms |
Keywords | Field | DocType |
linear congruential generator,integers modulo q,residue ring z,pseudorandom number,noisy polynomial evaluation,relation v,direct application,polynomial congruential generator,lattice basis reduction | Integer,Discrete mathematics,Combinatorics,Polynomial,Modulo,Linear congruential generator,Polynomial ring,Function composition,Mathematics,Lattice reduction,Pseudorandom number generator | Journal |
Volume | Issue | ISSN |
61 | 2 | 0196-6774 |
Citations | PageRank | References |
13 | 0.77 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Simon R. Blackburn | 1 | 357 | 36.95 |
| Domingo Gomez-perez | 2 | 61 | 10.22 |
| Jaime Gutierrez | 3 | 154 | 18.15 |
| Igor E. Shparlinski | 4 | 1339 | 164.66 |