Python函數掛起大數

-1

我正在嘗試做一個函數來計算模塊指數MODEXP(a,e,p)。Python函數掛起大數

這個函數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，代碼開始掛起。我如何防止這種情況發生？

來源

2013-11-20 noazet abdo

您有一個需要運行超過一百萬次的for循環。你想要多快？ – geoffspear

我希望當輸入例如m和n等於500它會工作，我也希望它只需要幾個毫秒 –

那麼，你需要提出一個算法，不涉及建立一個2^500列表整數，然後迭代它來做到這一點。 – geoffspear

-1

如果你只是想計算
MOD（冪e的a模量）p
或類似的東西，然後

我會強烈建議您在此維基article

在這種情況下，最大迭代次數將等於變量e的二進制表示中的位數。

來源

2013-11-20 19:30:15 adil

不需要閱讀文章，在Python中它只是'pow（a，e，p）'。但OP已經在使用它，所以我不知道他們實際上正在做什麼。 – interjay

我之所以這樣說，是因爲OP有點不清楚所以他可以閱讀文章並在自己的實現中使用它（這可能有所幫助）然後閱讀並使用它比使用'pow（a，e ，p）'一味地。 – adil

不，重新發明輪子並不比使用現有的內置解決方案更好。無論如何，這似乎不是OP所需要的 - 問題的第一句似乎是誤導性的。 – interjay

Python函數掛起大數

回答

相關問題