A probabilistic factorization algorithm with quadratic forms of negative discriminant
HTML articles powered by AMS MathViewer
- by Martin Seysen PDF
- Math. Comp. 48 (1987), 757-780 Request permission
Abstract:
We propose a probabilistic algorithm for factorization of an integer N with run time ${(\exp \sqrt {\log N\log \log N} )^{\sqrt {5/4} + o(1)}}$. Asymptotically, our algorithm will be as fast as the well-known factorization algorithm of Morrison and Brillhart. The latter algorithm will fail in several cases and heuristic assumptions are needed for its run time analysis. Our new algorithm will be analyzed under the assumption of the Extended Riemann Hypothesis and it will be of Las Vegas type. On input N, the new algorithm will factor N with probability $\geqslant \frac {1}{2}$. In case of prime N the algorithm will prove the primality of N with probability $\geqslant \frac {1}{2}$.References
- Eric Bach, Analytic methods in the analysis and design of number-theoretic algorithms, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1985. MR 807772 Z. I. Borevič & I. R. Šafarevič, Teorija Čisel, Izdat. "Nauka", Moscow, 1964; English transl., Academic Press, New York and London, 1966. N. G. de Bruijn, "On the number of positive integers $\leqslant x$ free of prime factors $> y$. II," Nederl. Akad. Wetensch. Proc. Ser. A, v. 69, 1966, pp. 239-247.
- E. R. Canfield, Paul Erdős, and Carl Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17 (1983), no. 1, 1–28. MR 712964, DOI 10.1016/0022-314X(83)90002-1
- J. W. S. Cassels, Rational quadratic forms, London Mathematical Society Monographs, vol. 13, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 522835
- D. Coppersmith, Rapid multiplication of rectangular matrices, SIAM J. Comput. 11 (1982), no. 3, 467–471. MR 664714, DOI 10.1137/0211037 L. E. Dickson, History of the Theory of Numbers, Vol. 1, Carnegie Institution, Washington, D. C., 1919.
- John D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), no. 153, 255–260. MR 595059, DOI 10.1090/S0025-5718-1981-0595059-1 C. F. Gauss, Disquisitiones Arithmeticae, Leipzig, 1801.
- Richard K. Guy, How to factor a number, Proceedings of the Fifth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1975) Congressus Numerantium, No. XVI, Utilitas Math. Publ., Winnipeg, Man., 1976, pp. 49–89. MR 0404120
- G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- J. C. Lagarias, Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, J. Algorithms 1 (1980), no. 2, 142–186. MR 604862, DOI 10.1016/0196-6774(80)90021-8
- J. C. Lagarias, H. L. Montgomery, and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979), no. 3, 271–296. MR 553223, DOI 10.1007/BF01390234
- J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191 E. Landau, Vorlesungen über Zahlentheorie, Band 1: Elementare und additive Zahlentheorie, Hirzel, Leipzig, 1927; reprinted, Chelsea, New York, 1982. S. Lang, Algebraic Number Theory, Addison-Wesley, Reading, Mass., 1968. A. M. Legendre, Théorie des Nombres, Paris, 1798, pp. 313-320.
- D. H. Lehmer and R. E. Powers, On factoring large numbers, Bull. Amer. Math. Soc. 37 (1931), no. 10, 770–776. MR 1562254, DOI 10.1090/S0002-9904-1931-05271-X
- P. G. Lejeune Dirichlet, Vorlesungen über Zahlentheorie, Chelsea Publishing Co., New York, 1968 (German). Herausgegeben und mit Zusätzen versehen von R. Dedekind; Vierte, umgearbeitete und vermehrte Auflage. MR 0237283
- H. W. Lenstra Jr., On the calculation of regulators and class numbers of quadratic fields, Number theory days, 1980 (Exeter, 1980) London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123–150. MR 697260
- C.-P. Schnorr and H. W. Lenstra Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), no. 167, 289–311. MR 744939, DOI 10.1090/S0025-5718-1984-0744939-5 H. W. Lenstra, Jr., Factoring Integers with Elliptic Curves, preprint, Amsterdam, 1986. G. B. Mathews, Theory of Numbers, reprinted, Chelsea, New York, 1982. L. Monier, Algorithmes de Factorisation d’Entiers, Thèse d’Informatique, Université Paris Sud, 1980.
- Michael A. Morrison and John Brillhart, A method of factoring and the factorization of $F_{7}$, Math. Comp. 29 (1975), 183–205. MR 371800, DOI 10.1090/S0025-5718-1975-0371800-5 J. Oesterle, "Versions effectives du théorème de Chebotarev sous l’hypothèse de Riemann généralisé," in Astérisque 61 (1979), Journées Arithmétiques de Luminy, Soc. Math. de France, 1979, pp. 165-167.
- J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI 10.1017/s0305004100049252
- C. Pomerance, Analysis and comparison of some integer factoring algorithms, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 89–139. MR 700260
- Karl Prachar, Primzahlverteilung, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957 (German). MR 0087685 R. A. Rankin, "The difference between two consecutive prime numbers," J. London Math. Soc., v. 13, 1938, pp. 242-297.
- R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120–126. MR 700103, DOI 10.1145/359340.359342
- J. Sattler and C.-P. Schnorr, Ein Effizienzvergleich der Faktorisierungsverfahren von Morrison-Brillhart und Schroeppel, Computing 30 (1983), no. 2, 91–110 (German, with English summary). MR 698122, DOI 10.1007/BF02280781
- C.-P. Schnorr, Refined analysis and improvements on some factoring algorithms, J. Algorithms 3 (1982), no. 2, 101–127. MR 657269, DOI 10.1016/0196-6774(82)90012-8 C. P. Schnorr & M. Seysen, An Improved Composition Algorithm, preprint, Universität Frankfurt, 1984.
- H. Zantema, Class numbers and units, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 213–234. MR 702518 I. Schur, "Einige Bemerkungen zu der vorstehenden Arbeit des Herrn G. Pólya: Über die Verteilung der quadratischen Reste und Nichtreste," Nachr. Kön. Ges. Wiss. Göttingen, Math.-Phys. Kl., 1918, pp. 30-36. In: Gesammelte Abhandlungen, Bd. II, Springer, Berlin, 1973, pp. 239-245.
- Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
- Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354–356. MR 248973, DOI 10.1007/BF02165411
- Volker Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), no. 1, 1–8. MR 438807
- Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR 0158502 B. L. van der Waerden, Algebra, Zweiter Teil, Fünfte Auflage, Springer-Verlag, Berlin, 1967.
- Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), no. 1, 54–62. MR 831560, DOI 10.1109/TIT.1986.1057137
Additional Information
- © Copyright 1987 American Mathematical Society
- Journal: Math. Comp. 48 (1987), 757-780
- MSC: Primary 11Y05; Secondary 11E32, 68Q25
- DOI: https://doi.org/10.1090/S0025-5718-1987-0878705-X
- MathSciNet review: 878705