Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers
It is shown 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 the authors to devise a simple algorithm to factorise polynomials with rational coefficients. All algorithms work in polynomial time
Cite this item
Kannan, R., Lenstra, A. K., & Lovasz, L. (1988). Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. Mathematics of Computation, 50(181), 235–250. https://doi.org/10.1090/S0025-5718-1988-0917831-4
Click Copy to copy the citation, or select the text manually.
EPFL-ARTICLE-149482.pdf
openaccess
1.61 MB
Adobe PDF
19e2bac7ba58d44e24bcc59cb257abcf