Python中的模冪運算算法

我創建了一個計算大模指數的函數。我知道這個函數是內置在python語言中的。我的功能對於大於17位的數字不正確，我無法弄清楚原因。任何幫助是極大的讚賞。Python中的模冪運算算法

from random import randint 

def modpow(x,n,m): 
    if n == 0: 
    return 1 
    elif n == 1: 
    return x 
    elif n%2 == 0: 
    return modpow(x*(x%m),n/2,m)%m 
    elif n%2 == 1: 
    return (x * modpow(x*(x%m),(n-1)/2,m)%m)%m 

for i in range(5,32): 
    x = '' 
    n = '' 
    m = '' 
    for j in range(i): 
    x += str(randint(0,9)) 
    n += str(randint(0,9)) 
    m += str(randint(0,9)) 
    x = int(x) 
    n = int(n) 
    m = int(m) 
    if pow(x,n,m) != modpow(x,n,m): 
    print(i,x,n,m)

輸出示例：

17 38508450670424585 67111951647554134 59005802612594983 
18 24027200512104766 205942669690724726 816654795945860553 
...

我已經跑了幾次，它總是開始於我失敗= 17，我不明白爲什麼。

來源

2014-04-05 Matt Pennington

如果您使用Python 3，那麼'/'運算符會返回一個浮點點值。您可能希望使用'//'來返回Python 2和3的整數結果。 – casevh

只需使用'from random import *'和'm = int（m）'運行代碼，它似乎表現良好。編輯：Python 2.7 – etna

@etna在py2或py3上？ – Hyperboreus

-1

我的猜測是Python的pow()適用於double。失敗的第一個值（38508450670424585）的第一個值的日誌庫2大約爲55，但double只有53位的精度，因此大於2^53的整數不一定能精確表示。我的猜測是，如果你檢查成功的最後一個數字（例如，對於x = 16）的日誌庫2，它將小於53.

來源

2014-04-05 23:18:16 Emmet

Python中的模冪運算算法

回答

相關問題