1

私は群論のどん底に投げ込まれ、私が持っている暗号学のクラスに少し迷っています。基本的に私がJavaで実装しなければならない実用的なものは、

order(素数, p-1 の因数のリスト, 任意の a)

これは、グループ Z*p 内の a の順序を返す必要があります。ここで、f は p-1 の素因数のリストです。f に重複が含まれる場合にメソッドが機能することを確認します。たとえば、p=17 の場合を考えてみましょう

これが私がこれまでに持っているものです（メモ内の手順から取得）

public static BigInteger order(BigInteger p, List<BigInteger> f, BigInteger a){
    //Algorithm starts like this
    //Start by setting t equal to p-1 i.e t= p1 p2...pn
    BigInteger t = p.subtract(BigInteger.ONE);
    for(BigInteger pi : f){
        //test if a^t1 = 1 mod p where t1 = t/pi
        BigInteger t1 = t.divide(pi);

        if(Practical5ExponentiationModMSquareAndMultiply.expm(p, a, t1).equals(BigInteger.ONE)){
            t = t1;
            System.out.println("t after mod = "+t);
            System.out.println("pi after mod = "+pi);
        }
    }       
    return t;

}

素因数 f のリストは別のメソッドによって生成され、次に渡されます

私が持っているメモは理解するのが非常に難しく、実際に何を返すべきか教えてくれる人がいるかどうか疑問に思っていました. また、この群論のスニペットを理解できるように教えてください。それは私のさらなる実践に役立ちます。

4

1 に答える 1

3

oのような最小の数a^o == 1 (mod p)、つまり oをp割る最小の数を探していa^o - 1ます。

必要な群論の結果は、p を法とする整数の乗法群が次数 p-1 の巡回であるということです。この意味は：

  • 秩序oは分裂p-1し、満足するa^o == 1 (mod p)
  • 次数oは、上記の条件を満たす最小の数です。

したがって、 の素因数を取り、 の割り算が真でなくなるまでそれらp-1で繰り返し割り算することで、次数を見つけることができます。p-1pa^n - 1

例 1 : p = 13、p-1 = 2*2*3、a = 5。

p = 2 の場合、5^(12/2) == 12 (mod 13) であるため、順序で 2 を失うことはありません。

p = 3 の場合、5^(12/3) == 1 (mod 13) であるため、順序で 3 を失う可能性があります。

したがって、次数は 2*2 = 4 です。

あなたに与えられた例 (p = 17) は、別の例です。

例 2 : p = 17、p-1 = 2*2*2*2、a = 9

9^(16/2) == 1 (mod 17) なので、最初の 2 を失う可能性があります。

9^(16/4) == 16 (mod 17) なので、2 番目の 2 を失うことはなく、検索を停止できます。

したがって、次数は 2*2*2 = 8 です。

うまくいけば、アルゴリズムを理解するにはこれで十分でしょう。

于 2011-04-26T16:42:05.943 に答える