Я пытаюсь реализовать алгоритм подписи Шнорра на Java. Я столкнулся с проблемой расчета мощности с большим показателем (например, хеш-числом MD5).
Есть ли способ получить BigInteger в силе BigInteger?
Мне нужно вычислить (a^x*b^y)% z, где y — чрезвычайно большое число. Есть ли способ вычисления таких выражений?
Спасибо
Для алгоритма подписи Шнорра вам действительно нужна комбинированная операция мощности и модуля. Простое выполнение силовой операции само по себе не имеет смысла из-за потенциально огромного размера задействованных чисел.
Вам нужно использовать метод modPow класса BigInteger.
Наконец-то я нашел решение. Я могу очень быстро вычислить свое выражение, используя эту технику:
(a * b) % p = ((a % p) * (b % p)) % p
Итак, мой пример будет выглядеть так:
(a^x * b^y) % z = ( ((a^x) % z) * ((b^y) % z) ) % z;
или, используя BigInteger в Java:
BigInteger result = a.modPow(x, z).multiply( b.modPow(y, z) ).mod(z);
Нет. Максимальное значение, поддерживаемое BigInteger, равно 2Integer.MAX_VALUE-1. Это уточняющее предложение было добавлено в BigInteger javadoc в Java. 8, но реализация остается неизменной уже довольно давно.
BigInteger должен поддерживать значения в диапазоне от -2Integer.MAX_VALUE (исключительно) до +2Integer.MAX_VALUE (исключительно) и может поддерживать значения за пределами этого диапазона.
Как указывали другие, вы можете использовать modPow вместо вычисления промежуточных значений.
Для сравнения: примерно 10 80 (или 2265) атомов во Вселенной.
