3.8Пример 3 rsa.

Если же решить, что мы выбрали большое число N и можем работать с таким числом, представленным только в виде строки символов заданного алфавита, то выбор фрагмента и расчет выглядят по-другому.

Начнем с N. N=33, то есть в нашей системе счисления 33/3=11(0 остаток) 11/3=3(2) 3/3=1(0), то есть получает 1020 =БАВА.

E =3, то есть в нашей системе счисления 10 = БА.

D =7, то есть в нашей системе счисления 21 = ВБ.

Исходное сообщение ААБВВАААААА.

Очевидно, что длина фрагмента не превышает длину строки, представляющей число N, но может быть на 1 меньше. Определить это можно, реализовав строковое сравнение следующим образом: сравнить t-ые символы, начиная с символа с номером t=1 (слева). Если они равны, то перейти к символам с номером t=t+1. Та строка больше, чей очередной символ больше очередного символа из другой строки.

ААБВ < БАВА, что становится очевидным после сравнения левых символов (Б>А).

Таким образом, нам надо вычислить ААБВ^БА mod БАВА. Здесь нам надо воспользоваться символьной арифметикой (нами реализуемой в лабораторных работах).

3.9Немного об арифметических операциях по модулю n.

Операция «остаток от деления на n» любому положительному числу сопоставляет число из интервала [0,n-1]. Если взять за исходный некоторый интервал длины n (количество чисел в интервале), то сопоставление будет взаимно однозначным.

Сдвиг этого интервала вправо по числовой оси на n или любое число кратное n приведет нас к интервалу, числа из которого сопоставляется с интервалом [0,n-1] точно таким же образом, что и исходный интервал. То есть операция «остаток от деления» инвариантна относительно смещения вправо на шаг, кратный длине интервала.

При выполнении всех операций по модулю n результат должен оставаться в области неотрицательных чисел, не превышающих n. Будем считать, что исходные числа правильные, то есть из интервала [0,n-1]. При выполнении арифметических операций промежуточный или конечный результат могут получиться в диапазоне [–(n-1),(n-1)²]. В этом случае применяется операция вычисления остатка от деления на n, возможно дополненная сдвигом вправо по числовой оси на число, кратное n.

3.10Сложение.

При обычном сложении двух чисел из интервала [0,n-1] имеем результирующий интервал [0, 2*(n-1)]. Применение к результату операции «остаток от деления» вернет результат в интервал [0, n-1].

3.11Вычитание.

При обычном вычитании двух чисел из интервала [0, n-1] имеем результирующий интервал [-(n-1), n-1]. Применение к результату операции «остаток от деления» не даст верного результата, так как отрицательные числа перейдут в отрицательные, а положительные – в положительные. Поэтому сначала необходимо к результату добавить n (длину интервала), при этом произойдет сдвиг в положительную область: [1, 2*n-1]. А затем применить операцию «остаток от деления», которая вернет результат в интервал [0, n-1].

3.12Умножение.

При обычном умножении двух чисел из интервала [0, n-1] имеем результирующий интервал [0, (n-1)²]. Применение к результату операции «остаток от деления» вернет результат в интервал [0, n-1]. Если используются алгоритмы быстрого умножения, то к промежуточным результатам можно применять операцию «остаток от деления», снижая порядок чисел.