next up previous
Next: On the Number of Up: The Post-Doctoral Period (1983-86) Previous: Finding the Shortest Move-Sequence

The Weakest Pseudo-Random Generator Implies the Strongest One

It is shown that any pseudorandom generator that stretches its seed by only one bit can be used to construct pseudorandom generators of arbitrary strecthing functions.


Comments: Authored by O. Goldreich and S. Micali.

Unpublished manuscript, October 1984.



Oded Goldreich
2003-07-30