Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers
Authors:
R. Kannan, A. K. Lenstra and L. Lovász
Journal:
Math. Comp. 50 (1988), 235250
MSC:
Primary 68Q20; Secondary 11A51, 11A63, 11J99, 11Y16, 68Q25
MathSciNet review:
917831
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: 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.
 [1]
A.
Baker, Linear forms in the logarithms of algebraic numbers. I, II,
III, Mathematika 13 (1966), 204216; ibid. 14 (1967), 102107; ibid.
14 (1967), 220–228. MR 0220680
(36 #3732)
 [2]
L. Blum, M. Blum & M. Shub, A Simple Secure Pseudo Random Number Generator, Proceedings of Crypto 82.
 [3]
Manuel
Blum and Silvio
Micali, How to generate cryptographically strong sequences of
pseudorandom bits, 23rd annual symposium on foundations of computer
science (Chicago, Ill., 1982) IEEE, New York, 1982,
pp. 112–117. MR
780388
 [4]
É. Borel, Leçons sur la Théorie des Fonctions, 2nd ed., 1914, pp. 182216.
 [5]
A.
J. Brentjes, Multidimensional continued fraction algorithms,
Computational methods in number theory, Part II, Math. Centre Tracts,
vol. 155, Math. Centrum, Amsterdam, 1982, pp. 287–319. MR 702520
(85f:11096)
 [6]
Arthur
H. Copeland and Paul
Erdös, Note on normal numbers, Bull. Amer. Math. Soc. 52 (1946), 857–860. MR 0017743
(8,194b), http://dx.doi.org/10.1090/S000299041946086577
 [7]
D. G. Champernowne, "The construction of decimals normal in the scale of ten," J. London Math. Soc., v. 8, 1933, pp. 254260.
 [8]
O.
Goldreich, S.
Goldwasser, and S.
Micali, How to construct random functions, Theory of
algorithms (Pécs, 1984) Colloq. Math. Soc. János Bolyai,
vol. 44, NorthHolland, Amsterdam, 1985, pp. 161–189. MR 872307
(88b:68082)
 [9]
Shafi
Goldwasser, Silvio
Micali, and Po
Tong, Why and how to establish a private code on a public
network, 23rd annual symposium on foundations of computer science
(Chicago, Ill., 1982) IEEE, New York, 1982, pp. 134–144. MR
780391
 [10]
Peter
Henrici, Applied and computational complex analysis,
WileyInterscience [John Wiley & Sons], New YorkLondonSydney, 1974.
Volume 1: Power series—integration—conformal
mapping—location of zeros; Pure and Applied Mathematics. MR 0372162
(51 #8378)
 [11]
I.
N. Herstein, Topics in algebra, 2nd ed., Xerox College
Publishing, Lexington, Mass.Toronto, Ont., 1975. MR 0356988
(50 #9456)
 [12]
M.P. Van der Hulst & A. K. Lenstra, Polynomial Factorization by Transcendental Evaluation, Proceedings Eurocal 85.
 [13]
R. Kannan, A. K. Lenstra & L. Lovász, Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers, Proc. 16th Annual ACM Symposium on Theory of Computing, 1984, pp. 191200.
 [14]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [15]
S. Landau & G. Miller, Solvability by Radicals is in Polynomial Time, Proc. 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 140151.
 [16]
A.
K. Lenstra, H.
W. Lenstra Jr., and L.
Lovász, Factoring polynomials with rational
coefficients, Math. Ann. 261 (1982), no. 4,
515–534. MR
682664 (84a:12002), http://dx.doi.org/10.1007/BF01457454
 [17]
R.
Loos, Computing in algebraic extensions, Computer algebra,
Springer, Vienna, 1983, pp. 173–187. MR
728972, http://dx.doi.org/10.1007/9783709175514_12
 [18]
M.
Mignotte, An inequality about factors of
polynomials, Math. Comp. 28 (1974), 1153–1157. MR 0354624
(50 #7102), http://dx.doi.org/10.1090/S00255718197403546243
 [19]
Michael
O. Rabin, Probabilistic algorithms in finite fields, SIAM J.
Comput. 9 (1980), no. 2, 273–280. MR 568814
(81g:12002), http://dx.doi.org/10.1137/0209024
 [20]
C. P. Schnorr, "A more efficient algorithm for lattice basis reduction," manuscript, 1985.
 [21]
A. Schönhage, The Fundamental Theorem of Algebra in Terms of Computational Complexity, Preliminary report, Math. Inst. Univ. Tübingen, 1982.
 [22]
Arnold
Schönhage, Factorization of univariate integer polynomials by
Diophantine approximation and an improved basis reduction algorithm,
Automata, languages and programming (Antwerp, 1984) Lecture Notes in
Comput. Sci., vol. 172, Springer, Berlin, 1984,
pp. 436–447. MR 784270
(86i:68057), http://dx.doi.org/10.1007/3540133453_40
 [23]
A. Shamir, On the Generation of Cryptographically Strong PseudoRandom Sequences, Proc. 8th International Colloquium on Automata, Languages, and Programming, 1981.
 [24]
B. Trager, Algebraic Factoring and Rational Function Integration, Proc. SYMSAC 76, pp. 219226.
 [25]
Andrew
C. Yao, Theory and applications of trapdoor functions, 23rd
annual symposium on foundations of computer science (Chicago, Ill., 1982)
IEEE, New York, 1982, pp. 80–91. MR
780384
 [1]
 A. Baker, "Linear forms in the logarithms of algebraic numbers I, II, III, IV," Mathematika, v. 13, 1966, pp. 204216; ibid., v. 14, 1967, pp. 102107; ibid., v. 14, 1967, pp. 220228; ibid., v. 15, 1968, pp. 204216. MR 0220680 (36:3732)
 [2]
 L. Blum, M. Blum & M. Shub, A Simple Secure Pseudo Random Number Generator, Proceedings of Crypto 82.
 [3]
 M. Blum & S. Micali, How to Generate Cryptographically Strong Sequences of Pseudo Random Bits, Proc. 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 112117. MR 780388
 [4]
 É. Borel, Leçons sur la Théorie des Fonctions, 2nd ed., 1914, pp. 182216.
 [5]
 A. J. Brentjes, "Multidimensional continued fraction algorithms," in Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdeman, eds.), Math. Centre Tracts 154, 155, Mathematisch Centrum, Amsterdam, 1982. MR 702520 (85f:11096)
 [6]
 A. H. Copeland & P. Erdős, "Note on normal numbers," Bull. Amer. Math. Soc., v. 52, 1946, pp. 857860. MR 0017743 (8:194b)
 [7]
 D. G. Champernowne, "The construction of decimals normal in the scale of ten," J. London Math. Soc., v. 8, 1933, pp. 254260.
 [8]
 O. Goldreich, S. Goldwasser & S. Micali, How to Construct Random Functions, Proc. 25th Annual Symposium on Foundations of Computer Science, 1984, pp. 464479. MR 872307 (88b:68082)
 [9]
 S. Goldwasser, S. Micali & P. Tong, Why and How to Establish a Private Code on a Public Network, Proc. 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 134144. MR 780391
 [10]
 P. Henrici, Applied and Computational Complex Analysis, vol. 1, Wiley, New York, 1974. MR 0372162 (51:8378)
 [11]
 I. N. Herstein, Topics in Algebra, 2nd ed., Xerox, 1976. MR 0356988 (50:9456)
 [12]
 M.P. Van der Hulst & A. K. Lenstra, Polynomial Factorization by Transcendental Evaluation, Proceedings Eurocal 85.
 [13]
 R. Kannan, A. K. Lenstra & L. Lovász, Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers, Proc. 16th Annual ACM Symposium on Theory of Computing, 1984, pp. 191200.
 [14]
 D. E. Knuth, The Art of Computer Programming, Vol. 2, 2nd ed., AddisonWesley, Reading, Mass., 1981. MR 633878 (83i:68003)
 [15]
 S. Landau & G. Miller, Solvability by Radicals is in Polynomial Time, Proc. 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 140151.
 [16]
 A. K. Lenstra, H. W. Lenstra, Jr. &, L. Lovász, "Factoring polynomials with rational coefficients," Math. Ann., v. 261, 1982, pp. 513534. MR 682664 (84a:12002)
 [17]
 R. Loos, "Computing in algebraic extensions," Computer Algebra (B. Buchberger, G. Collins and R. Loos, eds.), SpringerVerlag, Berlin and New York, 1982, pp. 173187. MR 728972
 [18]
 M. Mignotte, "An inequality about factors of polynomials," Math. Comp., v. 28, 1974, pp. 11531157. MR 0354624 (50:7102)
 [19]
 M. O. Rabin, "Probabilistic algorithms in finite fields," SIAM J. Comput., v. 9, 1980, pp. 273280. MR 568814 (81g:12002)
 [20]
 C. P. Schnorr, "A more efficient algorithm for lattice basis reduction," manuscript, 1985.
 [21]
 A. Schönhage, The Fundamental Theorem of Algebra in Terms of Computational Complexity, Preliminary report, Math. Inst. Univ. Tübingen, 1982.
 [22]
 A. Schönhage, Factorization of Univariate Integer Polynomials by Diophantine Approximation and an Improved Basis Reduction Algorithm, Proc. 11th International Colloquium on Automata, Languages, and Programming, 1984, LNCS 172, 1984, pp. 436447. MR 784270 (86i:68057)
 [23]
 A. Shamir, On the Generation of Cryptographically Strong PseudoRandom Sequences, Proc. 8th International Colloquium on Automata, Languages, and Programming, 1981.
 [24]
 B. Trager, Algebraic Factoring and Rational Function Integration, Proc. SYMSAC 76, pp. 219226.
 [25]
 A. Yao, Theory and Applications of Trapdoor Functions, Proc. 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 8091. MR 780384
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
68Q20,
11A51,
11A63,
11J99,
11Y16,
68Q25
Retrieve articles in all journals
with MSC:
68Q20,
11A51,
11A63,
11J99,
11Y16,
68Q25
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198809178314
PII:
S 00255718(1988)09178314
Article copyright:
© Copyright 1988
American Mathematical Society
