×

Faster deterministic integer factorization. (English) Zbl 1285.11148

Summary: The best known unconditional deterministic complexity bound for computing the prime factorization of an integer \( N\) is \( O(\mathsf M_{\mathrm{int}}(N^{1/4} \log N))\), where \( \mathsf M_{\mathrm{int}}(k)\) denotes the cost of multiplying \( k\)-bit integers. This result is due to A. Bostan, P. Gaudry and É. Schost [SIAM J. Comput. 36, No. 6, 1777–1806 (2007; Zbl 1210.11126)], following the Pollard-Strassen approach. We show that this bound can be improved by a factor of \(\sqrt {\log \log N}\).

MSC:

11Y05 Factorization
11Y16 Number-theoretic algorithms; complexity

Citations:

Zbl 1210.11126
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alin Bostan, Pierrick Gaudry, and Éric Schost, Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator, SIAM J. Comput. 36 (2007), no. 6, 1777 – 1806. · Zbl 1210.11126
[2] Richard Crandall, Karl Dilcher, and Carl Pomerance, A search for Wieferich and Wilson primes, Math. Comp. 66 (1997), no. 217, 433 – 449. · Zbl 0854.11002
[3] Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. · Zbl 1088.11001
[4] Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), no. 3, 979 – 1005. · Zbl 1192.68926
[5] Niels Möller, On Schönhage’s algorithm and subquadratic integer GCD computation, Math. Comp. 77 (2008), no. 261, 589 – 607. · Zbl 1165.11003
[6] Hugh L. Montgomery and Robert C. Vaughan, Multiplicative number theory. I. Classical theory, Cambridge Studies in Advanced Mathematics, vol. 97, Cambridge University Press, Cambridge, 2007. · Zbl 1142.11001
[7] Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. · Zbl 0833.68049
[8] J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521 – 528. · Zbl 0294.10005
[9] Arnold Schönhage, Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients, Computer algebra (Marseille, 1982) Lecture Notes in Comput. Sci., vol. 144, Springer, Berlin-New York, 1982, pp. 3 – 15. · Zbl 0538.68035
[10] Volker Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), no. 1, 1 – 8. · Zbl 0361.68070
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.