I have written a code :

In [1]:
import time
import random
#max_PrimLength = 1000000000000


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def is_prime(num):
    if num == 2:
        return True
    if num < 2 or num % 2 == 0:
        return False
    for n in range(3, int(num**0.5) 2, 2):
        if num % n == 0:
            return False
    return True

def generatenextPrime(E):
    prime_found=False
    while not prime_found:
        E= E 1
        if is_prime(E):
            prime_found=True
            return E
        
def generate_keyPairs():
    p = 331
    q = 313
    
    n = p*q
    print("n:",n)
    #'''phi(n) = phi(p)*phi(q)'''
    phi = (p-1) * (q-1) 
    print("p: %d" % p)
    print("q: %d" % q)
    
    
    e = 1579
    print("e:",e,)
    E = ((e**7) 1)
    print("Original E:",E,)
    if is_prime(E):
            g = gcd(E,phi)
            while g != 1:
                E = generatenextPrime(E)
                g = gcd(E,phi)
    else:
        E = generatenextPrime(E)
        g = gcd (E,phi)
        while g != 1:
            E = generatenextPrime(E)
            g = gcd(E,phi)
        print("Modified E:",E,)
        
    d = egcd(E, phi)[1]
    #'''make sure d is positive'''
    d = d % phi
    if(d < 0):
        d  = phi
        print("d = %d" % d)

    return ((E,n),(d,n))

start_encrypt = time.time_ns()

def encrypt(text,public_key):
    key,n = public_key
    ctext = [pow(ord(char),key,n) for char in text]
    return ctext
end_encrypt = time.time_ns()

start_decrypt = time.time_ns()

def decrypt(ctext,private_key):
    try:
        key,n = private_key
        text = [chr(pow(char,key,n)) for char in ctext]
        return "".join(text)
    except TypeError as E:
        print(E)
end_decrypt = time.time_ns()

if __name__ == '__main__':
    public_key,private_key = generate_keyPairs()
    print("Public:",public_key)
    print("Private:",private_key)
    
    input_message = input("Enter the message = ")
    ctext = encrypt(input_message,public_key)
    print("encrypted:",ctext)
    plaintext = decrypt(ctext, private_key)
    print("decrypted:",plaintext)

print(f"Encryption Time: {end_encrypt - start_encrypt}")
print(f"Decryption Time: {end_decrypt - start_decrypt}")
n: 103603
p: 331
q: 313
e: 1579
Original E: 24472306882417669706660

This code Runs until i input e^5 but doesn't run for e^7 and above . Please help me know if there is a way to increase its efficiency in order value to make it run for larger values of e. I believe the problem is my recursion part of the code.

I have attached a copy of my python notebook for better understanding

CodePudding user response：

Have you done the math on this? It's never getting into your recursion. The sqrt of 1579 ** 7 is about 160 billion, so your generatenextPrime loop will run 80 billion times. Finding prime numbers is HARD, and you are not doing it in a scalable way.

And by the way, the gcd of any prime number and any other number is always 1.