Глава 13

13.1 (Шифрование в себя в системе RSA)

Нам необходимо вычислить по модулю 3127 значения 530¹⁷ и 531¹⁷. Это просто, поскольку 17 = 16 + 1. Следовательно, нам необходимо вычислить 16-ю степень каждого из этих чисел путем четырехкратного возведения их в квадрат.

530² = 280900 = 893127+2597  2597(mod 3127),

поэтому

530⁴ = 2597² = 6744409 = 21563127+2597  2597(mod 3127);

откуда следует, что 530¹⁶  2597⁸  2597(mod 3127), и отсюда получаем

530¹⁷  5302597 = 1376410 = 4403127+530  530(mod 3127).

Итак, число 530 при зашифровании по системе RSA переходит в себя.

В случае числа 531 получаем

531² = 281961 = 903127+531  531(mod 3127),

и следовательно,

531¹⁷  531(531)¹⁶  531531  531(mod 3127).

Итак, число 531 также переходит в себя при зашифровании по системе RSA.