paper

Deterministic factorization of sums and differences of powers

arXiv:1512.06401 · doi:10.1090/mcom/3197

Abstract

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

arXiv comment8 pages

References in corpus (1)

Cited by in corpus (1)