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
MathSciNet review: 3667032
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?)

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