Mathematics of Computation · 1988 · 70 citations · 17 references
ComputingComputer ScienceMathematicsAlgebraAlgorithmsTheory Of ComputationAlgebraic Number TheoryComputational AlgebraNumber-theoretic AlgorithmsRandomized ComputationAlgebraic IntegersAlgebraic Number ComputationPolynomial DecompositionPolynomial Time ComplexityPolynomial-time AlgorithmsPseudorandom FunctionsPseudorandom GeneratorsSimple Algorithm
We show that the binary expansions of algebraic numbers do not form secure pseudorandom sequences; given sufficiently many initial bits of an algebraic number, its minimal polynomial can be reconstructed, and therefore the further bits of the algebraic number can be computed. This also enables us to devise a simple algorithm to factor polynomials with rational coefficients. All algorithms work in polynomial time.
17
Factoring polynomials with rational coefficients
A. K. Lenstra, H. W. Lenstra, László Lovász · Mathematische Annalen · 1982 · 4K citations · Full text
How to construct random functions
Oded Goldreich, Shafi Goldwasser, Silvio Micali · Journal of the ACM · 1986 · 2.1K citations · Full text
Theory and application of trapdoor functions
Andrew Chi-Chih Yao · 1982 · 1K citations
The Art of Computer Programming, Vol. 2
Donald E. Knuth · Medical Entomology and Zoology · 1981 · 863 citations