1

少し前に、この Python 実装の Pollard-Brent アルゴリズムを Clojure に移植しました。それは機能し、高速にも機能します。それは問題ではありません。また、同一の非ランダム シード値とステッピング関数を指定すると、Python コードのウサギとカメの位置が正確に再現されます。

しかし、私がそれに取り組んでいる間、カメとウサギが、ブレントの論文 (またはウィキペディア、またはその他の参照) のアルゴリズムの説明に基づいて期待したのとまったく同じように動かないことに気が付かずにはいられませんでした。の選択)。

具体的には、カメがウサギの位置にテレポートした後、ウサギdistanceはステップ数だけ前に進み、さらにステップdistance数だけ進みます。また、Brent-Pollard アルゴリズムでは、中間値も重要です。ただし、このコードは 2 番目の「パス」のステップのみを保存します。

Python コードの 6 行目から 18 行目と私のコメントは次のとおりです。

    while g==1:    

        # Tortoise (x) moves to hare (y)         
        x = y 

        # Hare (y) moves ahead by r steps
        for i in range(r):
            y = ((y*y)%N+c)%N

        k = 0

        # Hare (y) moves ahead by another r steps, 
        # with checkpoints at every m steps (the checkpoints are 
        # for the factorization; not part of Brent's cycle-finding algo proper)
        while (k<r and g==1):
            ys = y
            for i in range(min(m,r-k)):
                y = ((y*y)%N+c)%N
                q = q*(abs(x-y))%N
            g = gcd(q,N)
            k = k + m

私は今日、自分のコードに戻って、単純化されたバージョンをモックアップしてインデックスを表示することで、確実にテストすることにしました。これらは現在のコードによって与えられたインデックスです:

現在のバージョン:

Distance: 1
Tortoise at: 1
Hare starts at: 2
Hare path: [3]
Distance: 2
Tortoise at: 3
Hare starts at: 5
Hare path: [6 7]
Distance: 4
Tortoise at: 7
Hare starts at: 11
Hare path: [12 13 14 15]
Distance: 8
Tortoise at: 15
Hare starts at: 23
Hare path: [24 25 26 27 28 29 30 31]
Distance: 16
Tortoise at: 31
Hare starts at: 47
Hare path: [48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63]
Distance: 32
Tortoise at: 63
Hare starts at: 95
Hare path: [96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127]

その間、これは私がアルゴリズムに期待することです：

期待される出力:

Distance: 1
Tortoise at: 1
Hare path: [2]
Distance: 2
Tortoise at: 2
Hare path: [3 4]
Distance: 4
Tortoise at: 4
Hare path: [5 6 7 8]
Distance: 8
Tortoise at: 8
Hare path: [9 10 11 12 13 14 15 16]
Distance: 16
Tortoise at: 16
Hare path: [17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32]
Distance: 32
Tortoise at: 32
Hare path: [33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64]

「予想される」バージョンは、アルゴリズムに組み込まれた場合、Clojure で読みやすくなりますが、平均で 2 倍の時間がかかります (これは、インデックスを見ると理にかなっています)。

私の質問:

  1. 期待される出力は、ブレントのアルゴリズムの「正規」バージョンですか?
  2. 現在のバージョンはまだブレントのアルゴリズムの正しい実装ですか?
  3. うさぎのパスに完全に連続したインデックスが含まれていないにもかかわらず、現在のバージョンが機能するのはなぜですか?
4

0 に答える 0