Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. (English) Zbl 0654.12001

The authors apply the lattice basis reduction method of A. K. Lenstra, H. W. Lenstra jun. and L. Lovász [Math. Ann. 261, 515–534 (1982; Zbl 0488.12001)] to determine the minimal polynomial \(m_{\alpha}(t)\) of an algebraic number \(\alpha\), provided that they know bounds for the degree and the coefficients of \(m_{\alpha}\) and, depending on those bounds, sufficiently many digits of the real and imaginary part of \(\alpha\).
The running time of their algorithm is polynomial in the input data. The algorithm can of course be applied to the factorization of polynomials over the rationals. The authors also discuss the randomness of the bit sequence of the binary expansion of an algebraic number \(\alpha\) (and of some transcendental numbers like \(\log(\alpha)\), \(\cos^{-1}(\alpha))\) on the basis of that algorithm.
Reviewer: M.Pohst


11R09 Polynomials (irreducibility, etc.)
11Y16 Number-theoretic algorithms; complexity
11Y40 Algebraic number theory computations
68W30 Symbolic computation and algebraic computation


Zbl 0488.12001
Full Text: DOI


[1] A. Baker, Linear forms in the logarithms of algebraic numbers. I, II, III, Mathematika 13 (1966), 204-216; ibid. 14 (1967), 102-107; ibid. 14 (1967), 220 – 228. · Zbl 0161.05201
[2] L. Blum, M. Blum & M. Shub, A Simple Secure Pseudo Random Number Generator, Proceedings of Crypto 82. · Zbl 0602.65002
[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. · Zbl 0547.68046
[4] É. Borel, Leçons sur la Théorie des Fonctions, 2nd ed., 1914, pp. 182-216.
[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.
[6] Arthur H. Copeland and Paul Erdös, Note on normal numbers, Bull. Amer. Math. Soc. 52 (1946), 857 – 860. · Zbl 0063.00962
[7] D. G. Champernowne, ”The construction of decimals normal in the scale of ten,” J. London Math. Soc., v. 8, 1933, pp. 254-260. · Zbl 0007.33701
[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, North-Holland, Amsterdam, 1985, pp. 161 – 189. · Zbl 0596.65002
[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.
[10] Peter Henrici, Applied and computational complex analysis, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Volume 1: Power series — integration — conformal mapping — location of zeros; Pure and Applied Mathematics. · Zbl 0313.30001
[11] I. N. Herstein, Topics in algebra, 2nd ed., Xerox College Publishing, Lexington, Mass.-Toronto, Ont., 1975. · Zbl 1230.00004
[12] M.-P. Van der Hulst & A. K. Lenstra, Polynomial Factorization by Transcendental Evaluation, Proceedings Eurocal 85. · Zbl 0577.68057
[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. 191-200. · Zbl 0654.12001
[14] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0477.65002
[15] S. Landau & G. Miller, Solvability by Radicals is in Polynomial Time, Proc. 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 140-151.
[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. · Zbl 0488.12001
[17] R. Loos, Computing in algebraic extensions, Computer algebra, Springer, Vienna, 1983, pp. 173 – 187.
[18] M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), 1153 – 1157. · Zbl 0299.12101
[19] Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273 – 280. · Zbl 0461.12012
[20] C. P. Schnorr, ”A more efficient algorithm for lattice basis reduction,” manuscript, 1985. · Zbl 0825.11015
[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. · Zbl 0569.68030
[23] A. Shamir, On the Generation of Cryptographically Strong Pseudo-Random Sequences, Proc. 8th International Colloquium on Automata, Languages, and Programming, 1981. · Zbl 0462.94017
[24] B. Trager, Algebraic Factoring and Rational Function Integration, Proc. SYMSAC 76, pp. 219-226. · Zbl 0498.12005
[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.