Функция Python зависает для больших чисел

Question

Я пытаюсь сделать функцию, которая вычисляет модульную экспоненту MODEXP(a,e,p).

Эта функция принимает m и n в качестве параметров, где p простое число, самое большее 2^m и e является 2^n и a это случайное число меньше, чем p.

Вот мой код:

import random 
def question_3(m,n): 
    list = [] 
    i = 1 
    for i in range(2,2**m): 
     flag=True 
     for num in list: 
      if(i%num==0): 
       flag=False 
     if flag: 
      list.append(i) 
      p = choice(list) 
      a = randint(1,int(p)-1) 
      e = pow(2,n) 
    return pow(a, e, p) 

question_3(5,5) 

Для m и n более 20, код начинает зависать. Как я могу это предотвратить?

Answer 1

Если вы просто хотите, чтобы вычислить
(модуля a, возведенного в степень e) моды p
или что-то подобное, то

Я очень рекомендую вам эти вика article

В этом случае максимальное число итераций будет равно числу бит в двоичном представлении переменной e.