A probabilistic factorization algorithm with quadratic forms of negative discriminant

Seysen, Martin

doi:10.1090/S0025-5718-1987-0878705-X

A probabilistic factorization algorithm with quadratic forms of negative discriminant

Author: Martin Seysen
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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}$ .

[1] Eric Bach, Analytic methods in the analysis and design of number-theoretic algorithms, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1985. MR 807772
[2] Z. I. Borevič & I. R. Šafarevič, Teorija Čisel, Izdat. "Nauka", Moscow, 1964; English transl., Academic Press, New York and London, 1966.
[3] N. G. de Bruijn, "On the number of positive integers $\leqslant x$ free of prime factors . II," Nederl. Akad. Wetensch. Proc. Ser. A, v. 69, 1966, pp. 239-247.
[4] 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, https://doi.org/10.1016/0022-314X(83)90002-1
[5] 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
[6] D. Coppersmith, Rapid multiplication of rectangular matrices, SIAM J. Comput. 11 (1982), no. 3, 467–471. MR 664714, https://doi.org/10.1137/0211037
[7] L. E. Dickson, History of the Theory of Numbers, Vol. 1, Carnegie Institution, Washington, D. C., 1919.
[8] John D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), no. 153, 255–260. MR 595059, https://doi.org/10.1090/S0025-5718-1981-0595059-1
[9] C. F. Gauss, Disquisitiones Arithmeticae, Leipzig, 1801.
[10] Richard K. Guy, How to factor a number, Proceedings of the Fifth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1975) Utilitas Math. Publ., Winnipeg, Man., 1976, pp. 49–89. Congressus Numerantium, No. XVI. MR 0404120
[11] 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
[12] 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. MR 633878
[13] 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, https://doi.org/10.1016/0196-6774(80)90021-8
[14] 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, https://doi.org/10.1007/BF01390234
[15] J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: 𝐿-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191
[16] E. Landau, Vorlesungen über Zahlentheorie, Band 1: Elementare und additive Zahlentheorie, Hirzel, Leipzig, 1927; reprinted, Chelsea, New York, 1982.
[17] S. Lang, Algebraic Number Theory, Addison-Wesley, Reading, Mass., 1968.
[18] A. M. Legendre, Théorie des Nombres, Paris, 1798, pp. 313-320.
[19] D. H. Lehmer and R. E. Powers, On factoring large numbers, Bull. Amer. Math. Soc. 37 (1931), no. 10, 770–776. MR 1562254, https://doi.org/10.1090/S0002-9904-1931-05271-X
[20] P. G. Lejeune Dirichlet, Vorlesungen über Zahlentheorie, Herausgegeben und mit Zusätzen versehen von R. Dedekind. Vierte, umgearbeitete und vermehrte Auflage, Chelsea Publishing Co., New York, 1968 (German). MR 0237283
[21] 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
[22] 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, https://doi.org/10.1090/S0025-5718-1984-0744939-5
[23] H. W. Lenstra, Jr., Factoring Integers with Elliptic Curves, preprint, Amsterdam, 1986.
[24] G. B. Mathews, Theory of Numbers, reprinted, Chelsea, New York, 1982.
[25] L. Monier, Algorithmes de Factorisation d'Entiers, Thèse d'Informatique, Université Paris Sud, 1980.
[26] Michael A. Morrison and John Brillhart, A method of factoring and the factorization of 𝐹₇, Math. Comp. 29 (1975), 183–205. MR 371800, https://doi.org/10.1090/S0025-5718-1975-0371800-5
[27] 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.
[28] J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, https://doi.org/10.1017/s0305004100049252
[29] 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
[30] Karl Prachar, Primzahlverteilung, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957 (German). MR 0087685
[31] R. A. Rankin, "The difference between two consecutive prime numbers," J. London Math. Soc., v. 13, 1938, pp. 242-297.
[32] 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, https://doi.org/10.1145/359340.359342
[33] 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, https://doi.org/10.1007/BF02280781
[34] C.-P. Schnorr, Refined analysis and improvements on some factoring algorithms, J. Algorithms 3 (1982), no. 2, 101–127. MR 657269, https://doi.org/10.1016/0196-6774(82)90012-8
[35] C. P. Schnorr & M. Seysen, An Improved Composition Algorithm, preprint, Universität Frankfurt, 1984.
[36] 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
[37] 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.
[38] 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
[39] Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354–356. MR 248973, https://doi.org/10.1007/BF02165411
[40] Volker Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), no. 1, 1–8. MR 438807
[41] Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR 0158502
[42] B. L. van der Waerden, Algebra, Zweiter Teil, Fünfte Auflage, Springer-Verlag, Berlin, 1967.
[43] Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), no. 1, 54–62. MR 831560, https://doi.org/10.1109/TIT.1986.1057137