Модульное экспонирование в Java

Question

Мне нужен способ для расчета:

(g^u * y^v) mod p

на Java.

Я нашел этот алгоритм для вычисления (g ^ u) mod p:

int modulo(int a,int b,int c) {
    long x=1
    long y=a;
    while(b > 0){
        if(b%2 == 1){
            x=(x*y)%c;
        }
        y = (y*y)%c; // squaring the base
        b /= 2;
    }
    return (int) x%c;
}

и это прекрасно работает, но я не могу найти способ сделать это для

(g^u * y^v) mod p

, так как мои математические навыки тусклые.

Чтобы поместить это в контекст, это для реализации Java "сокращенного" DSA - проверяющая часть требует, чтобы это было решено.

Answer 1

Предполагая, что два фактора не будут переполнены, я полагаю, что вы можете упростить такое выражение следующим образом:

(x * y) mod p = ( (x mod p)*(y mod p) ) mod p.Я уверен, что вы можете понять это оттуда.

Answer 2

Этот фрагмент кода реализует хорошо известный алгоритм «быстрого возведения в степень», также известный как Возведение в степень путем возведения в квадрат .

Также используется тот факт, что (a * b) mod p = ((a mod p) * (b mod p)) mod p. (Как сложение, так и умножение являются сохраняющимися структурами при взятии простого модуля - это гомоморфизм). Таким образом, в каждой точке алгоритма он сводится к числам, меньшим, чем p.

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

Имейте в виду, что вы получите переполнение, если p ^ 2 больше, чем наибольшее представимое целое число, и что это приведет к неправильному ответу. Для Java переключение на большое целое число может быть разумным, или, по крайней мере, выполнить проверку во время выполнения размера p и выдать исключение.

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

Answer 3

Попробуйте

(Math.pow (q, u) * Math.pow (y, v))% p