[hannob]

"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 is one of the most challenging aspects of mathematics and computing.

This very fact, that large prime numbers are hard to find, is the basis of cryptography which is fundamental to cyber security."

That is simply flat out wrong.

What they probably are referring to is RSA. However the basis of RSA is not that it's hard to find a large prime number. (Actually if that would be hard then RSA would be impossible, as it needs large primes for key generation.) The basis is that it's hard to factorize a composite number.

[animeshk]

You're absolutely right. I just made that change in the article. Thanks for pointing it out!

[akalin]

You 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

You may be thinking of the search for Mersenne primes, or other primes of a specific form.

[graemewicksted]

I 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]

I 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.