4 ms·
You're absolutely right. I just made that change in the article. Thanks for pointing it out!
by animeshk 9y ago
You're absolutely right. I just made that change in the article. Thanks for pointing it out!
- deleted 9y ago[deleted]
- graemewicksted 9y agoI thought modern RSA crypto intentionally stays away from real primes because it's less secure. They use two semi-prime co-primes of significant size and with a large enough difference between them.
- nightcracker 9y agoI think you're confused. A RSA private key uses large primes, two to be exact. Those two primes form your private key. Multiplying them together gives your public key. The idea is that undoing that operation: finding which two primes multiplied together form the public key, is an intractable problem. Those two primes multiplied together is what's called a semiprime. The one part that you're correct on is that these two primes should be sufficiently distant, otherwise just trying a couple numbers near sqrt(pq) will give you either p or q.
- akalin 9y agoYou still mention that: > There's no slick trick to check fast enough, whether or not a large number is prime. So much so that finding large prime numbers has been an obsession for mathematicians. But that's still false; in fact, the rest of your article talks about the Fermat and Miller-Rabin primality test, which are indeed slick tricks that can check fast enough whether or not a large number is prime (to whatever degree of confidence you desire)! Also, finding large prime numbers isn't really an obsession anymore -- you can use any of the fast primality test algorithms mentioned above, randomly generate numbers of a desired bit length, and stop when you hit a (probable) prime, which happens fairly quickly by the prime number theorem: https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem You may be thinking of the search for Mersenne primes, or other primes of a specific form.