How to stop loop running out of memory?

I’ve come back to programming after a long haitus so please forgive any stupid errors/inefficient code.

I am creating an encryption program that uses the RSA method of encryption which involves finding the coprimes of numbers to generate a key. I am using the Euclidean algorithm to generate highest common factors and then add the coprime to the list if HCF == 1. I generate two lists of coprimes for different numbers then compare to find coprimes in both sets. The basic code is below:

def gcd(a, b):
    while b:
        a,b=b,a%b
    return a


def coprimes(n):
    cp = []
    for i in range(1,n):
        if gcd(i, n) == 1:
            cp.append(i)
    print(cp)

def compare(n,m):
    a = coprimes(n)
    b = coprimes(m)
    c = []
    for i in a:
        if i in b:
            c.append(i)
    print(c)

This code works perfectly for small numbers and gives me what I want but execution takes forever and is finally Killed when comupting for extremely large numbers in the billions range, which is necessary for even a moderate level of security. I assume this is a memory issue but I cant work out how to do this in a non memory intensive way. I tried multiprocessing but that just made my computer unusable due to the amount of processes running.

How can I calculate the coprimes of large numbers and then compare two sets of coprimes in an efficent and workable way?

Answer

If the only thing you’re worried about is running out of memory here you could use generators.

def coprimes(n):
    for i in range(1,n):
        if gcd(i, n) == 1:
            yield i

This way you can use the coprime value then discard it once you don’t need it. However, nothing is going to change the fact your code is O(N^2) and will always perform slow for large primes. And this assumes Euclid’s algorithm is constant time, which it is not.