Как возвести в степень значение biginteger на biginteger?

Question

[se271196]

Добрый день есть g^m * r^n mod n^2, основная проблема возведения в степень так как нужно будет использовать числа от 512, 1024 бит.

попробовал сделать костыль BigInteger.ModPow(r, n, bigmod()), где bigmod()- это число фиксированное число 1000000.... Но это не всегда срабатывает, потому что если r^n>bigmod() получаем ошибку вычисления, что бы ее решить нужно подсчитать примерную длину r^n , пока не знаю как это сделать не засоряя память.

Если использовать алгоритм быстрое возведение в степень -> засоряет память и выполняется очень долго.

Для проверки корректности использую эти значения(см картинку, в заголовке cipher text, пример вычисления c)
Кто сталкивался с подобной проблемой и как решил, каким алгоритмов , пример кода.

Answer 1

[Wataru]

Отличное свойство модуля в том, что можно при вычислениях брать модуль на каждом этапе (если нет делений - в этом случае надо искать обратное по модулю). Поэтому исходное выражение можно переписать так: (g^m mod n^2) * (r^n mod n^2) mod n^2

И код вычисления этого такой:

nn = n.multiply(n);
res = g.modPow(m, nn).multiply(r.modPow(n, nn)).mod(nn);

Comments

[se271196]

не совпало с большими числами. проходит только для очень маленьких чисел

[Wataru]

se271196, Если вы пытались ввести числа из статьи, то вы неверно ввели g.

[se271196]

956651757 все верно

[Wataru]

se271196, В статье у вас там g=1624691728. Где вы это 956651757 взяли вообще?

[se271196]

g это случайное число взаимно простое c n^2 + еще условие, извини за качество другого нет

[Wataru]

se271196, Выведите еще nn (убедитесь, что оно 7960076758133918401)

[se271196]

Wataru, все совпадает .

если сомневаешься
BigInteger p = new BigInteger("49727");
BigInteger q =new BigInteger("56737");
BigInteger n=new BigInteger("2821360799");
BigInteger g=new BigInteger("956651757");
BigInteger u=new BigInteger("1779031213");
BigInteger r=new BigInteger("1489472025");
BigInteger m=new BigInteger("1468689009");

BigInteger nn=n.multiply(n);
BigInteger enc=g.modPow(m, nn).multiply(r.modPow(n, nn)).mod(nn);
System.out.println(nn);
System.out.println(enc);

[Wataru]

se271196, Ну, тогда возможно ошибка в статье. Не может эта формула работать для маленьких чисел и не работать для больших.

[Samuel_Leonardo]

Опечатка в статье,
подставьте 1624691728 для g и получите искомые 2015851325878209300

Answer 2

[cicatrix]

Никто в реальных реализациях такой фигнёй не занимается. Ты постигаешь основы криптографии, но забыл изучить раздел "модульная арифметика".
https://ru.wikipedia.org/wiki/Возведение_в_степень...
Само число ведь не нужно. Нужен остаток от деления по модулю.
В противном случае тебе нужно будет реализовать класс, куда будут упаковываться числа нужной битности для 1024 бит тебе потребуется 16 long-ов. Ну и дальше - реализовать арифметику.