https://en.wikipedia.org/wiki/Probable_prime

The "openssl prime" command implements a probabilistic primality test that is used inside OpenSSL itself when generating cryptographic keys. You can use that same test to generate probable primes.

https://www.madboa.com/geek/openssl/#prime

Cryptographic keys that you use every day were generated in this way. For instance, the RSA modulus used for the Hacker News web site's HTTPS connection, over which you're reading this post right now, is

222509016795827497794083812831165961379247188961631875655725 097731134045330167937771236763198018821568432886298645744801 658852523304856266339353987508075113064105224649582744138410 510146575813098669176961919590643797014537786653110907775848 477867599116878297173259789693988510658470208808013230939561 018388391347262551003631143383727180887481292553673932217061 748044722300591830836145085835960246785127848933591684137542 631145040567308149003134261726643696478658524574120987942443 039450801995433458255131154946204465423021984216778361565845 434891950126041285345326571981150902538433621893316105896120 78998701064492853

This was generated by someone (probably using "openssl genrsa" or something that indirectly invoked it) using probabilistic primality tests to generate two numbers p and q which were multiplied together to create that modulus.

You might worry that some of the p and q values used for some crypto keys are actually composite (perhaps semiprimes, which actually have two prime factors of their own). That's theoretically possible, but it's incredibly unlikely if you believe that the probability estimates provided by the probabilistic tests are correct, since you could set the probability to be below 1/2⁵⁰⁰ or whatever. The idea is that it's reasonable to use things that are merely probably correct if you can set the probability that they're wrong to be well below the probability that something else in the system has already failed in a worse way (such as a cosmic ray causing a bit flip in the private key parameters that caused them to be composite).

So to summarize, we can already find large primes very quickly (and quickly enough to generate the crpyto keys we want), we're just not sure that those primes are prime, but we're sure enough to use them!

Now there is also the EFF Cooperative Computing Awards (which I run), where if you can find and prove really large primes, like world-record size, you can win cash prizes.

https://www.eff.org/awards/coop

There is a reference in The Curious Incident of the Dog in the Night-Time that may be intended to allude to this and seems to be based on the idea that these large primes would be useful for cryptography. (The protagonist says that you're supposed to send your huge primes to the CIA for a cash reward. Whereas our prize does require that you publish your primes first...)

A lot of people who contact us are a bit confused about the relative sizes of the primes involved. To generate a 2048-bit RSA modulus (the main component of a 2048-bit RSA public key), you need two 1024-bit primes. I just generated such a prime, which was

153177856694500434587513500139248340308937876686459991440575 509272451197058639489829675301493324370461576756305322222646 365872282776312608964726803114536076295854994471249141723824 310821111109394983308072557413772787885400112845231154620813 572050991182667139586732160443583213692240495599715288955030 782261199

This prime is 309 digits long (it is a probable prime, not a proven prime). It's perfectly serviceable for industry-standard cryptographic applications (though not really for use in a private key anymore now that I've published it on Hacker News -- you shouldn't publish your private key parameters on discussion forums).

The primes needed to win our awards are 1000000 digits (already awarded), 10000000 digits (already awarded), 100000000 digits (still available), and 1000000000 digits (still available). It's incredibly hard to do calculations with numbers of these sizes -- for example the last one would occupy 3.32 billion bits of RAM, or over 415 megabytes -- and there's no known cryptographic algorithm that could usefully use them for anything. Of course, primes this big are found with special techniques that are only applicable to numbers of special forms. Those techniques couldn't be used to test the primality of arbitrary numbers, only certain specially-chosen numbers. The current special-form primality testing champion is

https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality...

Edit: Added spaces to break up the large integers above to avoid messing up the formatting of the page. Edit 2: corrected "pseudoprime" to "semiprime".

  n^2+n+41

That doesn't really matter, checking if a number is prime can be done in sublinear time complexity. The real problem is factoring large numbers.