Rational Base Descent: A Deterministic Algorithm for Factoring Structured Semiprimes

Sam Blake

We present a special-purpose algorithm for factoring semiprimes $N=pq$ in which one prime factor satisfies $p\approx c(a/b{)}^n$ for positive integers $a,b,c,n$ with $a>b$…