（（a^x）^ 1/x）== aはZp？ （Jablonのプロトコル用）

Question

Jablonのプロトコル（paper）を実装する必要がありますが、私は2時間バグを抱えていました。

私はそれが私のせいであるかどうかわからないので、それはできません。可能ならば、（（gP^x）^ yi）^（1/x）== gP^yiという事実に依存しているので、Jablonのプロトコルをどのように実装できるかわかりません。

次のコードを使用してください。それは動作しません。

BigInteger p = new BigInteger("101"); 
    BigInteger a = new BigInteger("83"); 
    BigInteger x = new BigInteger("13"); 
    BigInteger ax = a.modPow(x, p); 
    BigInteger xinv = x.modInverse(p); 
    BigInteger axxinv = ax.modPow(xinv, p); 

    if (a.equals(axxinv)) 
     System.out.println("Yay!"); 
    else 
     System.out.println("How is this possible?"); 

Answer 1

あなたの問題は、あなたが正しくK ^（1/x）のを計算していないということです。 k ^{（1/x））k}がxである必要があります。 Fermat's Little Theoremは、k ^p-1が1 mod pであることを示しています。したがって、x * yがmod pではなく1 mod p-1であるようなyを見つけたい。

だからあなたはBigInteger xinv = x.modInverse(p-1);が必要です。

xがp-1と共通の要素を共有する場合、これは機能しません。 （あなたの場合はそれを避けます）。そのためには、追加の理論が必要です。

pが素数ならば、r、r^2、r^3、...、r ^（p-2）のいずれもが1 mod pに一致しない場合、rは原始根です。プリミティブなルートを生成する単純なアルゴリズムはありませんが、一般的なので、通常はいくつかチェックするだけです。 （p = 101、私が試した最初の数、2は原始根であることが分かりました。83も同じです。）テストは難しいようですが、それは分かりません理論の集まり）p-1の除数だけをチェックする必要がある。たとえば101の場合、1,2,4,5,10,20,25,50の累乗を確認する必要があります。

ここで、rが原始根である場合、すべて数字のpはある程度のパワーですr。どんな力？これはdiscrete logarithm problemと呼ばれ、単純ではありません。 （難しかったのは、よく知られている暗号システムであるRSAの基礎です。）試用部門で行うことができます。だから1、2、3、...しようとすると、例えば、83は2^89（mod 101）です。

しかし、1から100までのすべての数値が2からいくつかのべき乗であることがわかったら、私たちは根を計算する方法で武装しています。数をxのべき乗にすることは指数にxを乗算するだけなので、 2^100は1です。したがって、べき乗はx（mod 100）を掛けています。

y^13を83にしたいと仮定します。次に、yが2^kでk * 13が89となるようにします。Chinese Remainder Theoremで遊んでいると、k = 53の作品が実現します。したがって、2^53（mod 101）= 93は89の13番目のルートです。

これは以前よりも困難です。しかし、例えば、44 mod 101の5番目の根を取ることを考えたとしましょう。5には、乗法逆モジュレーション100がないため、単純な手続きは使用できません。しかし、44は2^15です。したがって、2^3 = 8は5番目の根です。しかし、他の4つ、すなわち2^23,2^43,2^63そして2^83があります。