Разложение на множители при шифровании

[nnosipov]

Mikle1990 в сообщении #631409 писал(а):

В курсовой сделаю так, как я изначально писал ...

Ну, в таком случае напишите заодно и про функцию Кармайкла (на ней основан тот второй способ вычисления, что здесь обсуждался). Путь Ваш преподаватель порадуется.

[Joker_vD]

О, методы экспоненцирования в $\mathbb Z_m$? Их полным-полно, у нас в спецкурсе "Алгоритмы и методы ЗИ" им было посвящено несколько лекций. Есть, как уже сказали, двоичное экспоненцирование (слева направа и справа налево); есть лестница Монтгомери, метод Брауэра, скользящего окна, с использованием аддитивных и аддитивно-разностных цепочек... до черта их. Они делятся на три большие группы: общие методы, методы с фиксированным основанием и методы с фиксированным показателем. Хорошая подборка есть в Menezes, van Oorschot, Vanstone, "Handbook of Applied Cryptography". Еще, если хотите, могу скинуть конспект спецкурса — качество не очень, но все читаемо.

[Mikle1990]

Покопался в Интете, но про бинарный алгоритм ничего нормального не нашёл - даже примеров не видел.
Нашёл только "Метод повторного возведения в квадрат".
А это не одно и тоже? Вроде как, нет.

[Joker_vD]

Двоичное экспоненцирование справа налево:

Вход: $a$, $e\geqslant 1$.
Выход: $a^e$.
Алгоритм:
1. $A:=1,\, S:=a$
2. Пока $e\ne0$:
2.1. Если $e$ нечетно, то $A:=AS$
2.2. $e=\lfloor e/2\rfloor$
2.3. Если $e\ne0$, то $S:=S^2$
3. Вернуть $A$

Двоичное экспоненцирование слева направо:

Вход: $a$, $e\geqslant 1$, $e=(e_t e_{t-1}\dots e_1 e_0)_2$ — его двоичная запись.
Выход: $a^e$.
Алгоритм:
1. $A:=1$
2. Для $i$ от $t$ до $0$:
2.1. $A:=A^2$
2.2. Если $e_i=1$, то $A:=aA$
3. Вернуть $A$

[Mikle1990]

Joker_vD, спасибо, попытаюсь понять.