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

  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Apr 24 '17 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.