What is the fastest algorithm for finding large prime numbers?

[KingGambit]

TL;DR

Public Key, Private Key, Prime Numbers, RSA, Encryption

Dear PF Forum,
Can someone help me with the algorithm for finding a very large prime number?
In RSA Encryption (1024 bit? 2048?, I forget, should look it up at wiki for that), Private Keys is a - two prime number packet.
Now, what I wonder is, what algorithm that the computer use to find those large prime number very fast?

Supposed one prime number is half of 1024, it's a 512 bit number, it's about 10^(512/10 *3) somewhere around 10^171.

And let's say we find some 10^171 number by random process, and if I were to check if it's prime or not, I would do a loop of 10 ^ 86, which is its square root.
Looping 10^86 is a very, very long time, and I see that Windows or Bitcoin node, give me a Private Key, relatively fast.

Even if we use array, which is very impossible, it would take computer with DDR 4 RAM as big as Milky Way I think.

I know, that I'm asking too much for an explanation here. But, I've tried to google the algorithm to find a very large number. I have found any luck so far.
So if someone perhaps know such link for that algorithm, I'd be really grateful.
Thank you.

 

[f95toli]

Have you tried Googling this?
One of the first hits led me to


i tried the Python script on the page (copy 'n' paste into Jupyter) and it takes a couple of seconds to generate a 1024 bit number, 2048 only takes a bit longer

 

[Baluncore]

Now, what I wonder is, what algorithm that the computer use to find those large prime number very fast?

There are many algorithms that will quickly reject a large random number if it is composite. It is more difficult to prove that a large number is prime.

The security of encryption systems is often based on the difficulty of factorising the product of two large primes.
Certifying that big numbers are prime must be very much faster than factorisation of their products, or the system would be more of a handicap to the user than to the enemy.

 

[pbuk]

There are many algorithms that will quickly reject a large random number if it is composite. It is more difficult to prove that a large number is prime.

The security of encryption systems is often based on the difficulty of factorising the product of two large primes.
Certifying that big numbers are prime must be very much faster than factorisation of their products, or the system would be more of a handicap to the user than to the enemy.

I think you need to add a few 'probably's in there

 

[anorlunda]

Have you read this? It includes links to several references.

https://en.wikipedia.org/wiki/Prime_number#Computational_methods

 

[Baluncore]

Get a copy of; Prime Numbers a Computational Perspective.
By; Richard Crandall, Carl B. Pomerance; 2005.
See; Chapter 4. Primality Proving.

 

[Baluncore]

i tried the Python script on the page (copy 'n' paste into Jupyter) and it takes a couple of seconds to generate a 1024 bit number, 2048 only takes a bit longer

The application of the Miller-Rabin probabilistic algorithm is good way of quickly rejecting composite numbers.
The survivors produced are strong prime candidates. They are NOT certified prime.

 

[KingGambit]

Have you tried Googling this?
One of the first hits led me to


i tried the Python script on the page (copy 'n' paste into Jupyter) and it takes a couple of seconds to generate a 1024 bit number, 2048 only takes a bit longer

Wow, thank you. I'll check it.

 

[KingGambit]

The security ... is based on the difficulty of factorising the product of two large primes.
Certifying that big numbers are prime must be very much faster...

Thanks Baluncore, it's the certifying that I'm trying to find out.

 

[KingGambit]

Thank you very much every body.

 

[f95toli]

Thanks Baluncore, it's the certifying that I'm trying to find out.

But you don't need certified numbers for most practical cryptography; there is a trade-off between certainty ( likelihood that a number is prime) and speed; and for something like RSA you can probably live with a very, very small risk if it means you can generate large numbers on the fly whenever needed. It is still safer than e.g using a lookup table.

 

[Baluncore]

There are many algorithms that will quickly reject a large random number if it is composite. It is more difficult to prove that a large number is prime.

Miller-Rabin is only one of the many tests that are available. More algorithms should be employed, more trials must be run. For real encryption, it will take longer than a few seconds to get the confidence and security required of an “industrial-grade prime”.

 

[Vanadium 50]

I am not a number theorist, and it's been a while since I looked seriously at RSA, but...

I believe the only requirement for p and q is that they are relatively prime. However, if you pick a number that is composite, the brute-force attack time goes as the smallest factor of pq. As mentioned, there are many tests for "probable" primality, many of which give a quantitative measure of the likelihood the number is actually composite.

So, as a practical matter, does someone care if there is a 0.001% chance that a brute force attack takes 100 years rather than 100,000 years? Maybe, maybe not. I will say that in general making the most cryptographically secure section even stronger doesn't always help. When it becomes easier to bribe your way to get the key, that's what will happen.

 

[The Bill]

Once one has a candidate from Miller-Rabin, one can then certify (or reject) it with the AKS Test.

This video describes the jist of the test, and has good reference links in its description:

 

[Baluncore]

Once one has a candidate from Miller-Rabin, one can then certify (or reject) it with the AKS Test.

https://en.wikipedia.org/wiki/AKS_primality_test#Importance
"While the algorithm is of immense theoretical importance, it is not used in practice, rendering it a galactic algorithm.

For 64-bit inputs, the Baillie–PSW primality test is deterministic and runs many orders of magnitude faster.

For larger inputs, the performance of the (also unconditionally correct) ECPP and APR tests is far superior to AKS. Additionally, ECPP can output a primality certificate that allows independent and rapid verification of the results, which is not possible with the AKS algorithm. "