Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Deterministic factorization of sums and differences of powers

Author: Markus Hittmeir
Journal: Math. Comp. 86 (2017), 2947-2954
MSC (2010): Primary 11A51
Published electronically: April 7, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

$\displaystyle \mathcal {O}\Big {(}\textsf {M}_{\textup {int}}\Big {(}N^{1/4}\sqrt {\log N}\Big {)}\Big {)},$

$ \textsf {M}_{\textup {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 [Enhancements On Off] (What's this?)

  • [BGS07] 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,
  • [CH14] Edgar Costa and David Harvey, Faster deterministic integer factorization, Math. Comp. 83 (2014), no. 285, 339-345. MR 3120593,
  • [CP05] Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer, New York, 2005. MR 2156291
  • [F09] Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), no. 3, 979-1005. MR 2538847,
  • [P94] Christos H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
  • [S77] Volker Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), no. 1, 1-8. MR 0438807

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11A51

Retrieve articles in all journals with MSC (2010): 11A51

Additional Information

Markus Hittmeir
Affiliation: Hellbrunnerstraße 34, A-5020 Salzburg, Austria

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”.
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society