Dr. Damien Stehle
Universities Nancy 1 and Sydney
On the Randomness of Bits Generated by Sufficiently Regular Functions
Elementary functions such as sin or exp may naively
be considered as good generators of random bits: the bit-runs
output by these functions are believed to be statistically random most of
the time. But what about their computational hardness? Given a part
of the binary expansion of exp(x), can one recover x?
In this talk, I will describe a heuristic technique to address
this type of questions. It relies upon Coppersmith's heuristic
method --- itself based on lattice reduction --- for finding
the small roots of multivariate polynomials modulo an integer.
The main result can be described as follows. Suppose we have a
'nice' function f. Suppose that the desired x is in [0,1] and
can be written on n digits. Then if we are given the first n^2 digits
of f(x) except the n most significant ones, we can recover x
in time heuristically polynomial in n.