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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.