What is the fastest algorithm for finding large prime numbers?

In summary: 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 longerIn summary, the script takes a few seconds to generate a 1024 bit number, 2048 takes a bit longer but is still faster than brute-force.
  • #1
KingGambit
37
27
TL;DR Summary
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.
 
Technology news on Phys.org
  • #2
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
 
  • Like
Likes KingGambit
  • #3
KingGambit said:
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.
 
  • Like
Likes KingGambit
  • #4
Baluncore said:
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 :wink:
 
  • #6
Get a copy of; Prime Numbers a Computational Perspective.
By; Richard Crandall, Carl B. Pomerance; 2005.
See; Chapter 4. Primality Proving.
 
  • Like
Likes KingGambit
  • #7
f95toli said:
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.
 
  • Informative
Likes Keith_McClary
  • #8
f95toli said:
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.
 
  • #9
Baluncore said:
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.
 
  • #10
Thank you very much every body.
 
  • #11
KingGambit said:
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.
 
  • #12
Baluncore said:
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”.
 
  • #13
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.
 
  • Like
Likes KingGambit
  • #14
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:

 
  • #15
The Bill said:
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. "
 
  • Like
Likes KingGambit

Related to What is the fastest algorithm for finding large prime numbers?

1. How do scientists find large prime numbers?

Scientists use various mathematical algorithms and computer programs to search for large prime numbers. These algorithms often involve extensive calculations and can take a significant amount of time.

2. Why is finding large prime numbers important?

Finding large prime numbers is important in the field of cryptography, as they are used to create secure encryption codes. They are also important in number theory and have applications in various other areas of mathematics.

3. Is there a limit to how large a prime number can be?

As of now, there is no known limit to how large a prime number can be. However, as the numbers get larger, it becomes increasingly difficult and time-consuming to find them.

4. How long does it take to find a large prime number?

The time it takes to find a large prime number can vary greatly depending on the method and technology used. Some prime numbers have been found in a matter of seconds, while others have taken years to discover.

5. Can anyone find a large prime number, or do you need specialized skills?

Anyone with a basic understanding of mathematics and access to the necessary tools and resources can potentially find a large prime number. However, it does require a certain level of expertise and knowledge in number theory and computer programming to effectively search for and verify large prime numbers.

Similar threads

  • Programming and Computer Science
Replies
22
Views
1K
  • Programming and Computer Science
Replies
4
Views
1K
Replies
5
Views
539
  • Programming and Computer Science
Replies
2
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
32
Views
3K
  • Programming and Computer Science
Replies
30
Views
4K
  • Programming and Computer Science
Replies
13
Views
3K
Replies
9
Views
1K
  • General Math
Replies
24
Views
2K
  • Programming and Computer Science
Replies
11
Views
282
Back
Top