Алиса поссорилась с Бобом и решила использовать при переписке с ним ненадежный ключ шифрования.
Она отправила ему свой открытый ключ: e = 5, n = 275361343.
Боб, конечно, зашифровал его открытый текст и получил следующее: 42666716.
Но он решил не отправлять ничего Алисе, так как понял, что она ненадежный собеседник.
Какой же все-таки был открытый текст Боба?
shurshur, я его нашел: d = 165195677. Но если подставить это число в формулу для расшифровки, то есть будет 42666716 в степени 165195677 mod 275361343. Как такую степень посчитать я не знаю даже
danil_ka51, это как раз несложно. Раскладываем 165195677 в бинарное представление: 1001110110001010111110011101, затем начинаем возводить 42666716 в квадрат по модулю 275361343 и если у нас в бинарном представлении есть единица на нужной позиции то умножаем это текущее число по модулю. Тут в 64-битные int всё прекрасно уложится, поскольку любую операцию мы берём по модулю. Пояснение алгоритма на примере возведения в степень 19: https://www.HostMath.com/Show.aspx?Code=p%3D19%3D1...
В конце концов, можно у wolframalpha спросить ответ.
Простой
