The RSA cryptosystem makes use of $n=pq$ where $p, q$ are large prime numbers.

With quantum computing, factorization might become easier, so it will probably be useful to use much much bigger $p$, $q$ in the future.

If I remember correctly, the source of large prime numbers $p$, $q$ in today's most commons RSA implementations is: probabilistic primalty tests.

In a concrete manner, what could be a possible source of much much larger primer numbers (several order of magnitudes bigger than the $p$, $q$ used today)?

  • 2
    $\begingroup$ RSA has died years ago. Long live ECC. Several magnitude order, no one is going to use that power consumer and slow operation. $\endgroup$
    – kelalaka
    Oct 5, 2020 at 10:26
  • 4
    $\begingroup$ You mean pqRSA? $\endgroup$
    – DannyNiu
    Oct 5, 2020 at 10:47
  • 1
    $\begingroup$ the numbers we use right now are chosen at random and then incremented till prime, I see no reason why we cannot still do that, it will just be slower $\endgroup$ Oct 5, 2020 at 10:51
  • 1
    $\begingroup$ however, the actual use of such large primes would be... undesirable from a performance standpoint $\endgroup$ Oct 5, 2020 at 10:52
  • 1
    $\begingroup$ @kelalaka: if the threat we're worried about are Quantum Computers, ECC (except for isogeny) isn't the answer - it's just as vulnerable... $\endgroup$
    – poncho
    Oct 5, 2020 at 13:42


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.