# Factorizing semiprime $n=pq$ with $p \mid q-1$

Could we find a fast integer factorization algorithm for any large semiprime $n=pq$, if we know that $p \mid q-1$?

• If $(q-1)/p$ is not too large, there are efficient algorithms by a small extension of Pollard's p-1 factoring method: we basically consider $b=a^{nt} \bmod n$ where $t$ is a product of all primes below some bound, and $a$ is random, and compute $\gcd(b-1,n)$. This won't work in general, though. – D.W. Apr 24 '17 at 12:18