Deterministic factorization of sums and differences of powers

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.