離散的なログの赤ちゃんステップ巨大ステップアルゴリズム：不正な巨大ステップ

Question

私は離散的なログを計算するために赤ちゃんステップ巨大ステップアルゴリズムを実装しようとしています。以下は私のコードです：

# trying to solve 8576 = 3^x (mod 53047) 
p = 53047 
a = 3 
B = 8576 

m = int(math.ceil(math.sqrt(p-1))) 

baby = [] 
giant = [] 
for j in range(0,m-1): 
    baby.append((a**j)%p) 

for k in range(0,m-1): 
    val = a**(-1)%p 
    val2 = val**(k*m)%p 
    giant.append((B*val2)%p) 
    for i in xrange(len(baby)): 
     if giant[k] == baby[k]: 
      x = j + m*k 

私は出力なし試合のような非常に小さな値を取得していますので、私の大きな一歩と間違って何かがあると思います。正解はx = 1234です。誰かが私が間違っていることを教えてもらえますか？

Answer 1

実数逆数をとり、結果のモジュラスをとることによって、モジュラ逆数は計算されません。 aの乗法逆数を求めるにはp - の整数bとab = 1 (mod p)を見つける必要があります。これは、フェルマーの小定理を使用して（ショートカットなど）の拡張ユークリッドアルゴリズムまたはどちらかを使用して行うことができます。

a**(p-1) = 1 (mod p) 

これはa**(p-2) (mod p)がaの逆であることを意味します。

Answer 2

# trying to solve 8576 = 3^x (mod 53047) 
p = 53047 
a = 3 
B = 8576 

Pは常に> Bか（^ XモッズP = BとB> P）あなたは*を使用する必要があり、本当に*見て、再びその上に

最高の幸運