Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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

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


References [Enhancements On Off] (What's this?)

  • [1] E. Bach, Analytic Methods in the Analysis and Design of Number-Theoretic Algorithms, MIT Press, Cambridge, Mass., 1985. MR 807772 (87i:11185)
  • [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 $ > y$. II," Nederl. Akad. Wetensch. Proc. Ser. A, v. 69, 1966, pp. 239-247.
  • [4] E. R. Canfield, P. Erdös & C. Pomerance, "On a problem of Oppenheimer concerning "factorisatio numerorum"," J. Number Theory, v. 17, 1983, pp. 1-28. MR 712964 (85j:11012)
  • [5] J. W. S. Cassels, Rational Quadratic Forms, Academic Press, London and New York, 1978. MR 522835 (80m:10019)
  • [6] D. Coppersmith & S. Winograd, "On the asymptotic complexity of matrix multiplication," SIAM J. Comput., v. 11, 1982, pp. 472-492. MR 664715 (83j:68047b)
  • [7] L. E. Dickson, History of the Theory of Numbers, Vol. 1, Carnegie Institution, Washington, D. C., 1919.
  • [8] J. D. Dixon, "Asymptotically fast factorization of integers," Math. Comp., v. 36, 1981, pp. 255-260. MR 595059 (82a:10010)
  • [9] C. F. Gauss, Disquisitiones Arithmeticae, Leipzig, 1801.
  • [10] R. K. Guy, "How to factor a number," Proc. Fifth Manitoba Conf. Numer. Math., Utilitas, Winnipeg, 1975, pp. 49-89. MR 0404120 (53:7924)
  • [11] G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, Oxford, 1979. MR 568909 (81i:10002)
  • [12] D. E. Knuth, The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [13] J. C. Lagarias, "Worst case complexity bounds for algorithms in the theory of integral quadratic forms," J. Algorithms, v. 1, 1980, pp. 142-186. MR 604862 (83e:90112)
  • [14] J. C. Lagarias, H. L. Montgomery & A. M. Odlyzko, "A bound for the last prime ideal in the Chebotarev density theorem," Invent. Math., v. 54, 1975, pp. 137-144. MR 553223 (81b:12013)
  • [15] J. C. Lagarias & A. M. Odlyzko, "Effective versions of the Chebotarev density theorem," in Algebraic Number Fields, L-Functions and Galois Properties (A. Fröhlich, ed.), Academic Press, London and New York, 1977, pp. 409-464. MR 0447191 (56:5506)
  • [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 & R. E. Powers, "On factoring large numbers," Bull. Amer. Math. Soc., v. 37, 1931, pp. 770-776. MR 1562254
  • [20] P. G. L. Dirichlet & R. Dedekind, On Factoring Large Numbers, Braunschweig, 1893; reprinted, New York, 1968. MR 0237283 (38:5573)
  • [21] H. W. Lenstra, Jr., "On the calculation of regulators and class numbers of quadratic fields," Journées Arithmétiques 1980 (J. V. Armitage, ed.), Cambridge Univ. Press, New York, 1982, pp. 123-150. MR 697260 (86g:11080)
  • [22] H. W. Lenstra, Jr. & C. P. Schnorr, "A Monte-Carlo factoring algorithm with linear storage," Math. Comp., v. 43, 1984, pp. 289-311. MR 744939 (85d:11106)
  • [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] M. A. Morrison & J. Brillhart, "A method of factorization and the factorization of $ {F_7}$," Math. Comp., v. 29, 1975, pp. 331-334. MR 0371800 (51:8017)
  • [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 factorisation and primality testing," Proc. Cambridge Philos. Soc., v. 76, 1974, pp. 521-528. MR 0354514 (50:6992)
  • [29] C. Pomerance, "Analysis and comparison of some integer factoring algorithms," Computational Methods in Number Theory (R. Tijdeman & H. Lenstra, eds.), Mathematisch Centrum, Amsterdam, Tract 154, 1982, pp. 89-139. MR 700260 (84i:10005)
  • [30] K. Prachar, Primzahlverteilung, Springer-Verlag, Berlin, 1957. MR 0087685 (19:393b)
  • [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 & L. Adleman, "A method for obtaining digital signatures and public key cryptosystems," Comm. ACM, v. 21, 1978, pp. 120-126. MR 700103 (83m:94003)
  • [33] J. Sattler & C. P. Schnorr, "Ein Effizienzvergleich der Faktorisierungsverfahren von Morrison-Brillhart und Schroeppel," Computing, v. 30, 1983, pp. 91-110. MR 698122 (84g:10004)
  • [34] C. P. Schnorr, "Refined analysis and improvements on some factoring algorithms," J. Algorithms, v. 2, 1982, pp. 101-127. MR 657269 (83g:10003)
  • [35] C. P. Schnorr & M. Seysen, An Improved Composition Algorithm, preprint, Universität Frankfurt, 1984.
  • [36] R. J. Schoof, "Quadratic fields and factorisation," Computational Methods in Number Theory (R. Tijdeman & H. Lenstra, eds.), Mathematisch Centrum, Amsterdam, Tract 154, 1982, pp. 235-286. MR 702519 (85g:11118b)
  • [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] D. Shanks, Class Number, A Theory of Factorization and Genera, Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc., Providence, R. I., 1971, pp. 415-440. MR 0316385 (47:4932)
  • [39] V. Strassen, "Gaussian elimination is not optimal," Numer. Math., v. 13, 1969, pp. 354-356. MR 0248973 (40:2223)
  • [40] V. Strassen, "Einige Resultate über Berechnungskomplexität," Jber. Deutsch. Math.-Verein., v. 78, 1976, pp. 1-8. MR 0438807 (55:11713)
  • [41] R. S. Varga, Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, N. J., 1962. MR 0158502 (28:1725)
  • [42] B. L. van der Waerden, Algebra, Zweiter Teil, Fünfte Auflage, Springer-Verlag, Berlin, 1967.
  • [43] D. Wiedemann, "Solving sparse linear equations over finite fields," IEEE Trans. Inform. Theory, v. 32, 1986, pp. 54-62. MR 831560 (87g:11166)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y05, 11E32, 68Q25

Retrieve articles in all journals with MSC: 11Y05, 11E32, 68Q25


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1987-0878705-X
Article copyright: © Copyright 1987 American Mathematical Society

American Mathematical Society