0
$\begingroup$

Is the random picking of big n-bits random numbers for primality test a time sensitive operation?

If so, would an heuristic for limiting the search space (about 5-10x) without missing out on any prime be an interesting addition?

$\endgroup$
5
  • 2
    $\begingroup$ Did you see the answers to the questions How can I generate large prime numbers for RSA? and How are primes generated for RSA?? $\endgroup$
    – j.p.
    Commented May 25, 2022 at 6:06
  • 1
    $\begingroup$ Does this answer your question? How can I generate large prime numbers for RSA? $\endgroup$ Commented May 25, 2022 at 11:53
  • $\begingroup$ @j.p. Not really. I knew there is a random odd number picking and then testing. My doubt is if that part of the process is time sensitive, i.e. if it’s pre-calculated or if the user if any, has to wait in real time for RSA to come up with a key pair. The follow up is, if it’s time sensitive then a better method for prime picking candidates would be appreciated? $\endgroup$
    – juanmf
    Commented May 25, 2022 at 13:05
  • 2
    $\begingroup$ Is your method essentially "quickly reject candidate numbers with small factors?" Yes, that'd give you circa 5-10x speed-up over running Miller-Rabin directly over random odd numbers, and yes, we already know about it. $\endgroup$
    – poncho
    Commented May 25, 2022 at 13:22
  • $\begingroup$ @poncho "... yes, we already know about it." How then? All I found is random odd numbers, then deterministic test with few hundred low primes, then miller-Rabin. But nothing about anything to improve the random picking in the 1st place. $\endgroup$
    – juanmf
    Commented Jun 6, 2022 at 21:55

1 Answer 1

0
$\begingroup$

RSA keys are most often used for long-term 30 days or more) identification & authentication. The few hundred milliseconds it takes to generate an RSA key are inconsequential.

For short-term use Elliptic-Curve schemes like ECDH and EdDSA are common. Their keys take only a few microseconds to generate, thousands of times faster than RSA. They can also be used for long-term use. So speeding up RSA key generation isn't a particularly useful task, particularly if only small (10-1000x) speedups are achieved.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.