2

大きな剰余指数を計算する関数を作成しました。この関数が Python 言語に組み込まれていることは承知しています。関数が 17 桁を超える数値に対して正しくないため、理由がわかりません。どんな助けでも大歓迎です。

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
...

これを数回実行しましたが、常に i = 17 で失敗し始めます。その理由はよくわかりません。

4

1 に答える 1

0

私の推測では、Pythonはボンネットの下で s にpow()取り組んでいます。double失敗する最初の値 (38508450670424585) の対数底 2 は約 55 ですが、adoubleの精度は 53 ビットしかないため、2^53 より大きい整数は必ずしも正確に表すことができません。私の推測では、成功した最後の数 (x=16 の場合) の底 2 の対数を確認すると、53 未満になると思います。

于 2014-04-05T23:18:16.343 に答える