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
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

Teorija Čisel

Nederl. Akad. Wetensch. Proc. Ser. A

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

History of the Theory of Numbers

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

Disquisitiones Arithmeticae

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

Vorlesungen über Zahlentheorie, Band 1: Elementare und additive Zahlentheorie

Algebraic Number Theory

Théorie des Nombres

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

Factoring Integers with Elliptic Curves

Theory of Numbers

Algorithmes de Factorisation d’Entiers

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

Astérisque

Journées Arithmétiques de Luminy

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

J. London Math. Soc.

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

An Improved Composition Algorithm

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

Nachr. Kön. Ges. Wiss. Göttingen, Math.-Phys. Kl.

Gesammelte Abhandlungen

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

Algebra

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