Deterministic factorization of sums and differences of powers

Abstract: Let

a, b i n m a t h b b N

be fixed and coprime such that

a > b

, and let

N

be any number of the form

a^{n} p m b^{n}

,

n i n m a t h b b 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}( ext{M}_{ ext{int}}(N^{1/4}sqrt{log N})), ]

e x t M_{e x t i n t} (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.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Deterministic factorization of sums and differences of powers