java - 如何在java中生成离散对数

Question

我正在寻找一种简短的 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 我这样说对吗？

Answer 1

http://en.wikipedia.org/wiki/Discrete_logarithm列出了 7 种计算离散对数的算法。

为了理解离散对数本身，我会使用笔和纸构建一个小循环群生成元的所有幂的表。对数是倒数，因此如果翻转列，您就已经有了对数表。

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