Я пытаюсь реализовать алгоритм подписи Schnorr в Java. Я столкнулся с проблемой рассчитать мощность с большим показателем (например, хэш-номер MD5).BigIntegers к силе BigInteger (подпись Schnorr)
Есть ли способ получить BigInteger во власти BigInteger?
Мне нужно вычислить (a^x * b^y)% z, где y - очень большое число. Есть ли способ вычисления таких выражений?
Благодаря
Я, наконец, нашел решение. Я могу рассчитать свое выражение очень быстро, используя эту технику:
(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);
+1 для решения вашей собственной проблемы и для описания решения.Честно говоря, я никогда бы не понял, что проблема была чем-то таким основным - это было слишком долго, так как я впервые изучил модульную арифметику. –
No. Максимальное значение по BigInteger поддерживает 2 Integer.MAX_VALUE -1. Это разъясняющее предложение было добавлено к BigInteger javadoc в Java 8, но реализация была довольно продолжительной.
BigInteger должен поддерживать значения в диапазоне от -2 Integer.MAX_VALUE (эксклюзивного) до +2 Integer.MAX_VALUE (эксклюзивного) и может поддерживать значения вне этого диапазона.
Как указывалось другими, вы можете использовать modPow вместо вычисления промежуточных значений.
Для сравнения, есть 1080 (или 2) атомов во Вселенной.
Мне нужно вычислить (a^x * b^y)% z, где y - очень большое число. Есть ли способ вычисления таких выражений? –
Для алгоритма подписи Schnorr вы действительно хотите использовать объединенную мощность и модуль. Просто выполнение силовой операции само по себе не имеет смысла, из-за потенциально огромного размера задействованных чисел.
Вам необходимо использовать метод modPow для BigInteger class.
Связанные: HTTP: //math.stackexchange.com/q/176252 –
Существует одна очевидная причина, по которой у вас возникла проблема. Даже число, такое маленькое, как, скажем, 42, будет занимать больше памяти, чем существует на планете, если вы должны поднять его до уровня (2^127). – cHao
@cHao Поскольку $ z $ относительно невелик, вам нужно всего несколько сотен байт. – CodesInChaos