0

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?

juanmf
  • 103
  • 2
  • 2
    Did you see the answers to the questions [How can I generate large prime numbers for RSA?](https://crypto.stackexchange.com/q/71/142) and [How are primes generated for RSA?](https://crypto.stackexchange.com/q/1970/142)? – j.p. May 25 '22 at 06:06
  • 1
    Does this answer your question? [How can I generate large prime numbers for RSA?](https://crypto.stackexchange.com/questions/71/how-can-i-generate-large-prime-numbers-for-rsa) – AleksanderCH May 25 '22 at 11:53
  • @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? – juanmf May 25 '22 at 13:05
  • 2
    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. – poncho May 25 '22 at 13:22
  • @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. – juanmf Jun 06 '22 at 21:55

1 Answers1

0

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.

SAI Peregrinus
  • 5,361
  • 17
  • 25