4

ポーリヒヘルマンアルゴリズムのコーディングに取り組んでいますが、アルゴリズムの定義に基づいてアルゴリズムの手順を理解するのに問題があります。

アルゴリズムのウィキで行く：

最初の部分1）は、p-1の素因数を計算することです。これは問題ありません。

ただし、係数を計算する手順2）で何をする必要があるかわかりません。

Let x2 = c0 + c1(2). 
125(180/2) = 12590 1 mod (181) so c0 = 0.
125(180/4) = 12545 1 mod (181) so c1 = 0.
Thus, x2 = 0 + 0 = 0.

3）係数をまとめて、中国の剰余定理で解きます。

誰かがこれを平易な英語（i）または擬似コードで説明するのを手伝ってもらえますか？明らかに自分でソリューションをコーディングしたいのですが、アルゴリズムを理解しない限り、これ以上進歩することはできません。

注：私はこれについて多くの検索を行い、S。Pohlig and M. Hellman（1978）を読みました。「GF（p）とその暗号化の重要性を超える対数を計算するための改善されたアルゴリズムですが、それでも私にはあまり意味がありません。

前もって感謝します

更新：この例では、なぜq（125）が一定のままであるのですか。

この例のように、彼は毎回新しいqを計算しているように見えます。

具体的には、次の計算方法がわかりません。7531をa ^ c0で割って、を取得します 7531(a^-2) = 6735 mod p。

4

2 に答える 2

7

ポーリヒヘルマンの背後にある主なアイデアから始めましょう。y、g、pが与えられ、xを見つけたいと仮定します。

y == g x（mod p）。

（私は==を使用して同値関係を示しています）。簡単にするために、gの次数がp-1であると仮定します。つまり、1 == g k（mod p）の最小の正のkはk=p-1です。

xを見つける非効率的な方法は、1..p-1の範囲のすべての値を単純に試すことです。O（p 0.5）算術演算を必要とする「ベイビーステップジャイアントステップ」メソッドの方がやや優れています。どちらの方法も、pが大きい場合は非常に遅くなります。ポーリヒヘルマンは、p-1に多くの要因がある場合に大幅に改善されます。つまり、

p-1 = nr

次に、PohligとHellmanが提案するのは、方程式を解くことです。

y n ==（g n）z （mod p）。

両側のgを底とする対数を取ると、これは次のようになります。

n log g（y）== log g（y n）== nz（mod p-1）。

nを分割して、

log g（y）== z（mod r）。

したがって、x == z（mod r）です。

zの解を探すために範囲0..r-1を検索するだけでよいので、これは改善です。また、「ベイビーステップジャイアントステップ」を使用して、zの検索を改善できます。明らかに、これを一度行うことはまだ完全な解決策ではありません。つまり、p-1のすべての素因数rに対して上記のアルゴリズムを繰り返し、次に中国の剰余定理を使用して部分解からxを見つける必要があります。これは、p-1が平方フリーの場合にうまく機能します。

p-1が素数冪で割り切れる場合は、同様のアイデアを使用できます。たとえば、p-1 =mqkであると仮定します。最初のステップでは、上記のようにx == z（mod q）となるようにzを計算します。次に、これを解x == z'（mod q 2）に拡張します。たとえば、p-1 = mq 2の場合、これは、次のようなz'を見つける必要があることを意味します。

y m ==（g m）z'（mod p）。

z'== z（mod q）であることはすでにわかっているので、z'は集合{z、z + q、z + 2q、...、z +（q-1）q}に含まれている必要があります。ここでも、z'を徹底的に検索するか、「baby-stepgiant-step」で検索を改善することができます。このステップは、qのすべての指数に対して繰り返されます。これは、x mod q iを知ることから得られ、x mod q i+1を繰り返し導出します。

于 2010-04-04T20:05:10.427 に答える
1

私は今それを自分でコーディングしています（JAVA）。私はポラードローを使用して、p-1の小さな素因数を見つけています。次に、Pohlig-Hellmanを使用してDSA秘密鍵を解決します。y = g^x。私は同じ問題を抱えています。

更新：「より具体的には、次の計算方法がわかりません。7531をa ^ c0で除算して、7531（a ^ -2）= 6735modpを取得します。」

a ^ c0のmodInverseを見つけた場合、それは理にかなっています

よろしく

于 2010-04-03T19:48:49.037 に答える