0

巡回群 Z*p で LOGa(x) を見つけるのに役立つ Java の短くて単純なアルゴリズムを探しています。私の方法

log(prime_number, a, x) になります

これは巡回群 Z*p で LOGaX を計算します。

徹底的な検索でこれを行うにはどうすればよいですか、または簡単な方法はありますか、

そのため、個別のログを理解するのに役立つように、徹底的な検索を行いました。

    //log(p,a,x) will return logaX in the cyclic group Z*p where p is 
//prime and a is a generator

public static BigInteger log(BigInteger p,BigInteger a,BigInteger x){
    boolean logFound = false;
    Random r = new Random();
    BigInteger k = new BigInteger(p.bitCount(),r);
    while(!logFound){

        if(a.modPow(k, p).equals(x)){

            logFound = true;
        }else{
            k = new BigInteger(p.bitCount(),r);
        }
    }
            //i dont think this is right
    return a
}

巡回群 Z*p の LOGaX を返したいのですが、ここでこれを行っていますか、それとも何が欠けていますか?

だから私は今kを返し、徹底的な検索を行っています@pauloEbermann私は何をすべきか理解していませんk=k.multiply(a).mod(p)

私の新しいコードは次のようになります

//log(p,a,x) will return LOGaX in the cyclic group Z*p where p is 
//prime and a is a generator

public static BigInteger log(BigInteger p,BigInteger a,BigInteger x){
    boolean logFound = false;
    Random r = new Random();
    BigInteger k = BigInteger.ONE;

    while(!logFound){
        if(a.modPow(k, p).equals(x)){
            logFound = true;
        }else{
            k = k.add(BigInteger.ONE);

        }
    }
    return k;
}

このテストデータで

public static void main(String[] args) {

    BigInteger p = new BigInteger("101");
    BigInteger a = new BigInteger("3");
    BigInteger x = new BigInteger("34");

    System.out.println(log(p,a,x));
}

したがって、これは k = 99 を返します

これは、log3(34) mod 101 が 99 に等しいことを意味します。これを言うのは正しいでしょうか?

4

1 に答える 1

3

http://en.wikipedia.org/wiki/Discrete_logarithmには、離散対数を計算するための 7 つのアルゴリズムがリストされています。

離散対数自体を理解するには、紙とペンを使って、小さな巡回群の生成元のすべてのべき乗の表を作成します。対数は逆数であるため、列を反転すると、対数の表が既に作成されています。

単純なアルゴリズムはこのように機能しますが、テーブルを保存せずにループして、現在のべき乗が x に一致するまで a を乗算し、x を底とする a の対数として、乗算の回数に加えて完了した値に 1 を加えた値を出力するだけです。

于 2011-04-26T20:24:59.323 に答える