0

我正在为 java 寻找一个简短的算法，这将有助于在循环组 Z*p 中找到 LOGa(x)。我的方法

将是 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 种计算离散对数的算法。

为了理解离散对数本身，我将使用笔和纸，并构建一个小循环群生成器的所有幂的表格。对数是相反的，所以如果你翻转列，你已经有了对数表。

朴素算法的工作原理是这样的，只是您不存储表，而是简单地循环并乘以 a，直到当前幂与 x 匹配，并输出乘法数加上 done 加上 1 作为 x 以 a 为底的对数。

于 2011-04-26T20:24:59.323 回答