0

I'm trying to make a code to find two prime numbers, that I can calculate the multiplication of p and q.

I wanted to use thereby the Algorism of eratosthenes (the Algorism to find Primnumber) so my code would look like this:

find_primenumber=2**1024

# Algorism of eratosthenes (Primzahlen finden )
a = [False,False] + [True]*(find_primenumber-1)
primes=[]

for i in range(2,find_primenumber+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, find_primenumber+1, i):
        a[j] = False

# according to the p,q, the decrypted messages can be different.
p= primes[-1]
q= primes[-2]

# öffentliche Schlüssel public key (n,g)
n = p*q

This Code works very well, if I set the range of numbers (find_primenumber in the code), very small like 1000000. But I have to find in the longer range such as at least 2^1024. but when I set the length 2**1024 (2^1024). The Error comes out like this: enter image description here

Do you have any idea, how I can fix this problem?

Thank you!

Chiwan Park
  • 53
  • 5
  • 5
    This will take forever. Mathematicians don't use exhaustive search to test the primality of very large numbers, they have heuristic tests that tell if a number is probably prime. – Barmar Apr 20 '22 at 14:54
  • 1
    https://stackoverflow.com/a/4754427/5861582 a similar question was answered here. – João Marcos Gris Apr 20 '22 at 14:56
  • But I do agree with the comment by @Barmar, the solution you are trying to apply is conceptually flawed. – João Marcos Gris Apr 20 '22 at 14:57
  • For very large primes pick a random number in the size range you are looking at. Test it with prime divisors up to, say, 2,000. If it isn't prime pick another number and repeat. If there are no small prime divisors then use something like the [Miller-Rabin test](https://en.wikipedia.org/wiki/Miller–Rabin_primality_test) multiple times. For cryptographic security, apply the test at least 64 times. Again, repeat if the M-R test shows your number is composite. – rossum Apr 21 '22 at 10:41

0 Answers0