CODEWITHSUNDEEP
javacryptographydiscrete-mathematicslogarithm
molleman
molleman

Reputation: 2946

How to generate the discrete logarithm within java

I am looking for a short and simple algorithm for java that will help with finding the LOGa(x) in a cyclic group Z*p. my method

would be log(prime_number, a, x)

this would compute the LOGaX in a cyclic group Z*p.

How would i go about doing this in an exhaustive search, or is there any simple way,

so I have gone with the exhaustive search, just to help me understand the discrete log.

    //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
}

So i want to return the LOGaX of the cyclic group Z*p, am i doing this here or what am i missing?

so i now return k and i am now doing a exhaustive search @pauloEbermann i dont understand what i should do with k=k.multiply(a).mod(p)

my new code looks like this

//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;
}

with this test data

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));
}

So this returns k = 99

this means that the log3(34) mod 101 is equal to 99 would i be right in saying this?

Upvotes: 0

Views: 3264

Answers (1)

Peter G.
Peter G.

Reputation: 15114

http://en.wikipedia.org/wiki/Discrete_logarithm lists 7 algorithms for computing the discrete logarithm.

For understanding the discrete logarithm itself, I would use pen and paper and construct a table of all powers of a generator of a small cyclic group. The logarithm is the inverse, so you already have your table for logarithms if you flip the columns.

The naive algorithm works like this, only that you do not store the table but simply loop and multiply by a until the current power matches x and output the number of multiplications plus done plus one as the logarithm of x base a.

Upvotes: 3

Related Questions