  Let $a,b\in \mathbb{N}$ be fixed and coprime such that $a>b$, and let $N$ be
any number of the form $a^n\pm b^n$, $n\in\mathbb{N}$. We will generalize a
result of Bostan, Gaudry and Schost and prove that we may compute the prime
factorization of $N$ in \[ \mathcal{O}(\text{M}_{\text{int}}(N^{1/4}\sqrt{\log
N})), \] $\text{M}_{\text{int}}(k)$ denoting the cost for multiplying two
$k$-bit integers. This result is better than the currently best known general
bound for the runtime complexity for deterministic integer factorization.
