我想在下面的代码中增加我的递归时间

Question

我写了一个代码:

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

此代码会运行，直到我输入 e^5 但不会运行输入 e^7 及更高版本。请帮助我知道是否有一种方法可以提高订单价值的效率，使其运行对于更大的 e 值。我认为问题出在代码的递归部分。

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

Answer 1

import sys
sys.setrecursionlimit(1500)

Answer 2

你算过这个吗？它永远不会进入你的递归。 1579**7 的平方根大约是 1600 亿，所以你的 generatenextPrime 循环会运行 800 亿次。寻找质数是困难的，而且您没有以可扩展的方式进行。

顺便说一下，任何质数和任何其他数的 gcd 总是 1。

我想在下面的代码中增加我的递归时间

I want to Increase my Recursion Time In the following Code

python

recursion

jupyter-notebook

rsa