找到素數的概率（使用miller-rabin測試）

我已經實現了Miller-Rabin素數測試，並且每個函數似乎都在孤立地正常工作。然而，當我試圖通過生成70位隨機數來找到素數時，我的程序在找到一個通過米勒 - 拉賓測試（10步）的數字之前平均產生了超過100000個數字。這很奇怪，根據Hadamard-de laValléePoussin定理，隨機奇數少於70位的素數的概率應該很高（超過1/50）。我的代碼有什麼問題？隨機數發生器可能會以極低的概率拋出素數？我想不是......任何幫助都是非常受歡迎的。找到素數的概率（使用miller-rabin測試）

import random 


def miller_rabin_rounds(n, t): 
    '''Runs miller-rabin primallity test t times for n''' 

    # First find the values r and s such that 2^s * r = n - 1 
    r = (n - 1)/2 
    s = 1 
    while r % 2 == 0: 
     s += 1 
     r /= 2 

    # Run the test t times 
    for i in range(t): 
     a = random.randint(2, n - 1) 
     y = power_remainder(a, r, n) 

     if y != 1 and y != n - 1: 
      # check there is no j for which (a^r)^(2^j) = -1 (mod n) 
      j = 0 
      while j < s - 1 and y != n - 1: 
       y = (y * y) % n 
       if y == 1: 
        return False 
       j += 1 
      if y != n - 1: 
       return False 

    return True 


def power_remainder(a, k, n): 
    '''Computes (a^k) mod n efficiently by decomposing k into binary''' 
    r = 1 
    while k > 0: 
     if k % 2 != 0: 
      r = (r * a) % n 
     a = (a * a) % n 
     k //= 2 
    return r 


def random_odd(n): 
    '''Generates a random odd number of max n bits''' 
    a = random.getrandbits(n) 
    if a % 2 == 0: 
     a -= 1 
    return a 

if __name__ == '__main__': 
    t = 10 # Number of Miller-Rabin tests per number 
    bits = 70 # Number of bits of the random number 
    a = random_odd(bits) 
    count = 0 
    while not miller_rabin_rounds(a, t): 
     count += 1 
     if count % 10000 == 0: 
      print(count) 
     a = random_odd(bits) 
    print(a)

來源

2016-05-03 thelastone

Python在'pow（base，exponent，modulus）'方法本身實現'power_remainder'函數。我已經多次運行你的程序，並且在找到素數之前從未超過50次試驗。我生成了10000個隨機70位整數，並將您的miller_rabin_rounds的結果與我自己的isPrime函數進行比較，注意到沒有差異。我不明白爲什麼你需要100000次迭代才能找到素數。 – user448810

是的，我知道，只是想從頭開始實現它（而'power_remainder'並不是什麼大不了的事）。我發現這個問題只存在於python 3中，正如你所說的，它在python 2下以預期的概率運行。如果我找到它，我會發布確切的問題。 – thelastone

嘿thelastone，如果下面的答案固定爲你的東西，你可以標記爲答案？ – nbryans

在python 2而不是python 3中工作的原因是這兩個句柄的處理方式不同。在python 2中，3/2 = 1，而在python 3中，3/2=1.5。

看起來你應該在python 3中強制整數除法（而不是浮點除法）。如果你改變了代碼，迫使整數除法（//）這樣：

# First find the values r and s such that 2^s * r = n - 1 
r = (n - 1) // 2 
s = 1 
while r % 2 == 0: 
    s += 1 
    r //= 2

你應該可以看到正確的行爲，不管你用什麼Python版本。

來源

2016-05-18 00:12:38 nbryans

找到素數的概率（使用miller-rabin測試）

回答

相關問題