Deterministic factorization of sums and differences of powers
HTML articles powered by AMS MathViewer
- by Markus Hittmeir PDF
- Math. Comp. 86 (2017), 2947-2954 Request permission
Abstract:
Choose $a,b \in \mathbb {N}$ and let $N$ be a number of the form $a^n\pm b^n$, $n\in \mathbb {N}$. We will generalize a result of Bostan, Gaudry and Schost (2007) and prove that we may compute deterministically the prime factorization of $N$ in \[ \mathcal {O}\Big {(}\textsf {M}_{\mathrm {int}}\Big {(}N^{1/4}\sqrt {\log N}\Big {)}\Big {)},\] $\textsf {M}_{\mathrm {int}}(k)$ denoting the cost for multiplying two $\lceil k\rceil$-bit integers. This result is better than the currently best known general bound for the runtime complexity for deterministic integer factorization.References
- 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. MR 2299425, DOI 10.1137/S0097539704443793
- Edgar Costa and David Harvey, Faster deterministic integer factorization, Math. Comp. 83 (2014), no. 285, 339–345. MR 3120593, DOI 10.1090/S0025-5718-2013-02707-X
- Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
- Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), no. 3, 979–1005. MR 2538847, DOI 10.1137/070711761
- Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
- Volker Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), no. 1, 1–8. MR 438807
Additional Information
- Markus Hittmeir
- Affiliation: Hellbrunnerstraße 34, A-5020 Salzburg, Austria
- MR Author ID: 1220564
- ORCID: 0000-0002-3363-6270
- Email: markus.hittmeir@sbg.ac.at
- Received by editor(s): December 22, 2015
- Received by editor(s) in revised form: July 2, 2016, and July 21, 2016
- Published electronically: April 7, 2017
- Additional Notes: The author was supported by the Austrian Science Fund (FWF): Project F5504-N26, which is a part of the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”.
- © Copyright 2017 American Mathematical Society
- Journal: Math. Comp. 86 (2017), 2947-2954
- MSC (2010): Primary 11A51
- DOI: https://doi.org/10.1090/mcom/3197
- MathSciNet review: 3667032