Как сгенерировать дискретный логарифм в Java - PullRequest
Новая
       53

Как сгенерировать дискретный логарифм в Java

0 голосов
/ 27 апреля 2011

Я ищу короткий и простой алгоритм для Java, который поможет найти LOGa (x) в циклической группе Z * p. мой метод

будет log (prime_number, a, x)

это вычислит LOGaX в циклической группе Z * 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 = 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
}

Итак, я хочу вернуть LOGaX циклической группы Z * p, я делаю это здесь или чего мне не хватает?

так что теперь я возвращаю 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, я был бы прав, говоря это?

1 Ответ

3 голосов
/ 27 апреля 2011

http://en.wikipedia.org/wiki/Discrete_logarithm перечисляет 7 алгоритмов для вычисления дискретного логарифма.

Для понимания самого дискретного логарифма я бы использовал ручку и бумагу и создал бы таблицу всех степеней генератора малогоциклическая группа.Логарифм обратный, поэтому у вас уже есть таблица для логарифмов, если вы перевернете столбцы.

Наивный алгоритм работает так, только если вы не сохраняете таблицу, а просто зацикливаете и умножаете на a до тех пор, пока текущая мощность не совпадет с x, и выведите число умножений плюс выполненное, плюс единицу в качестве логарифма основания xа.

...