Let it be $p, q \in \mathbb{P}$ with $p,q \in [2^{b-1}, 2^b]$ for some $b \in \mathbb{N}$ and $p \cdot q = n \in \mathbb{N}$. What would be the distance between $p$ and $q$ (as a function of b) so that the factorization of $n$ is hardest or be considered difficult?

  • $\begingroup$ Related question. I still think the present question is interesting when it asks for a minimum $\lvert p-q\rvert$ so that the factorization of $n$ can be considered difficult. I don't know if/how the FIPS 186-4 bound $\lvert p–q\rvert>2^{b–100}$ is justifiable (note: it's stated for $p,q\in[2^{b-1/2},2^b]$ ) $\endgroup$
    – fgrieu
    Aug 24, 2021 at 7:58


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.