Generate two random primes and find their totient

Question

I am supposed to make a basic RSA encryption/decryption code, where I am only given e.

I wrote this code to randomly generate two primes and then find their totient. But the totient is supposed to not be co-prime with e which is given as 65537. So this code would technically return a good value eventually, but in reality it would take ages. Please help me speed it up and/or make suggestions on how it can be improved in general.

def primeGen(lim):
 """Generates all primes up to a certain limit (lim)"""
 fnl=[]
 primes=[2]
 p=0
 for n in range(2,lim+1):
 fnl.append(n)
 for v in fnl:
 p=0
 for i in range(2,v):
 if (v%i==0):
 p=1
 break
 if p==0 and i==(v-1):
 primes.append(v) 
 return primes
import random
def randomPrimeGen(lim):
 """Generates a single random prime number using primeGen(lim)"""
 M=(len(primeGen(lim))-1)
 randomPrime=(primeGen(lim)[random.randint(int(M/10),M)])
 return randomPrime
def modtot():
 e=65537
 totient=1
 GCD=gcd(e,totient)
 while GCD==1:
 p=randomPrimeGen(30000)
 q=randomPrimeGen(30000)
 n=p*q
 totient=((p-1)*(q-1))
 GCD=gcd(e,totient)
 print(GCD, totient)
 return n, totient

• chepner: Why are you regenerating the list of primes every time you need a random one? Compute primeGen(30000) once.

Answer 1

One problem, pointed out in comment by @chepner is that you are recomputing the primes twice. Save the primes, so you don't have to recompute.

Also, in your inner loop, you are unnecessarily dividing by every number up to v. Instead, you should skip all non-primes and only test divisibility by the primes, up to your largest known prime (because all other numbers up to there can be factorized into these primes). Only after that do you need to test divisibility for each integer max(primes) < i < v. Skipping all non-primes up to max(primes) saves a lot of looping/divisions/comparisons for large lim (especially given that the distance between consecutive primes tends to increase as lim increases). Something like this will give you a big speedup:

def primeGenFast(lim):
 fnl=[]
 primes=[2]
 fnl = list(range(2,lim+1))
 for v in fnl:
 p=1
 for n in primes:
 if v%n == 0:
 p = 0
 break
 if p==1:
 for i in range(primes[-1],v):
 if (v%i==0):
 break
 if i==(v-1):
 primes.append(v)
 return primes

This gives a speedup of nearly 10-20x on my machine, increasing as the size of lim increases:

In [3]: timeit(primeGenSlow(10000))
1 loop, best of 5: 465 ms per loop
In [6]: timeit(primeGenSlow(25000))
1 loop, best of 5: 3.98 s per loop
In [8]: timeit(primeGenSlow(100000))
1 loop, best of 5: 38.1 s per loop
----
In [2]: timeit(primeGenFast(10000))
10 loops, best of 5: 29.6 ms per loop
In [5]: timeit(primeGenFast(25000))
1 loop, best of 5: 307 ms per loop
In [7]: timeit(primeGenFast(100000))
1 loop, best of 5: 1.91 s per loop