@se271196

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

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

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

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

Для проверки корректности использую эти значения(см картинку, в заголовке cipher text, пример вычисления c)
Кто сталкивался с подобной проблемой и как решил, каким алгоритмов , пример кода.
606ae20ce9372546628539.png
  • Вопрос задан
  • 180 просмотров
Решения вопроса 1
wataru
@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);
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@cicatrix
было бы большой ошибкой думать
Никто в реальных реализациях такой фигнёй не занимается. Ты постигаешь основы криптографии, но забыл изучить раздел "модульная арифметика".
https://ru.wikipedia.org/wiki/Возведение_в_степень...
Само число ведь не нужно. Нужен остаток от деления по модулю.
В противном случае тебе нужно будет реализовать класс, куда будут упаковываться числа нужной битности для 1024 бит тебе потребуется 16 long-ов. Ну и дальше - реализовать арифметику.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы