Deterministic factorization of sums and differences of powers

Abstract

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.

8 pages

References in corpus (1)

• Digit Polynomials and their application to integer factorization

Cited by in corpus (1)

• A babystep-giantstep method for faster deterministic integer factorization