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?
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.May 25, 2022 at 6:06
-
1$\begingroup$ Does this answer your question? How can I generate large prime numbers for RSA? $\endgroup$– AleksanderCHMay 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$– juanmfMay 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$– ponchoMay 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$– juanmfJun 6, 2022 at 21:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
