<< Предыдущая

стр. 46
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

часов от 3 часов после полудня, то получится 5 часов утра следующего дня:
3 +14 ? 5 (mod 12)
или
(3 +14) mod 12 = 5.
Это арифметика по модулю 12.
Обычная запись в модулярной арифметике
a ? b (mod n)
читается так: "a сравнимо с b по модулю n". Это соотношение справедливо для целых значений a,b
и n ? 0, если, и только если
a=b+k?n
для некоторого целого k.
Отсюда, в частности, следует
n | (a – b).
Это читается как "n делит (a – b )".
a ? b (mod n),
Если
то b называют вычетом числа a по модулю n.
Операцию нахождения вычета числа a по модулю n
a (mod n)
называют приведением числа a по модулю n или приведением по модулю.
В нашем примере
(3 +14) mod 12 =17 mod 12 = 5
или
17 ? 5 (mod 12),
число 5 является вычетом числа 17 по модулю 12.
Набор целых чисел от 0 до (n –1) называют полным набором вычетов по модулю n. Это оз-
начает, что для любого целого a (a > 0) его вычет r по модулю n есть некоторое целое число в ин-
тервале от 0 до (n –1), определяемое из соотношения
r = a – k ? n,
где k – целое число.
Например, для n =12 полный набор вычетов:
{0, 1, 2, …, 11}.
Обычно предпочитают использовать вычеты
r ? {0, 1, 2, …, n –1},
но иногда полезны вычеты в диапазоне целых:
?1 ?
1
r ? ?? (n ? 1),..., (n ? 1)? .
?2 2 ?
Заметим, что
–12 (mod 7) ? –5 (mod 7) ? 2 (mod 7) ? 9 (mod 7) и т.д.
Модулярная арифметика аналогична во многом обычной арифметике: она коммутативна, ас-
социативна и дистрибутивна. Точнее говоря, целые числа по модулю n с использованием операций
сложения и умножения образуют коммутативное кольцо при соблюдении законов ассоциативности,
коммутативности и дистрибутивности.
Фактически мы можем либо сначала приводить по модулю n, а затем выполнять операции,
либо сначала выполнять операции, а затем приводить по модулю n, поскольку приведение по модулю
n является гомоморфным отображением из кольца целых в кольцо целых по модулю n:
(a + b) mod n = [a (mod n) + b (mod n)] mod n,
(a – b) mod n = [a (mod n) – b (mod n)] mod n,
(a ? b) mod n = [a (mod n) ? b (mod n)] mod n,
[a ? (b + c)] mod n = {[a ? b (mod n)] + [a ? c (mod n)]} mod n.
Криптография использует множество вычислений по модулю n, потому что задачи типа вы-
числения дискретных логарифмов и квадратных корней очень трудны. Кроме того, с вычислениями по
модулю удобнее работать, потому что они ограничивают диапазон всех промежуточных величин и
результата.
Для модуля n длиной k бит промежуточные результаты любого сложения, вычитания или
умножения будут не длиннее
2k бит. Поэтому возведение в степень в модулярной арифметике можно выполнить без генерации
очень больших промежуточных результатов.
Вычисление степени числа a по модулю n
ax mod n
можно выполнить как ряд умножений и делений. Существуют способы сделать это быстрее. Посколь-
ку эти операции дистрибутивны, быстрее произвести возведение в степень как ряд последователь-
ных умножений, выполняя каждый раз приведение по модулю. Это особенно заметно, если работать
с длинными числами (200 бит и более).
Например, если нужно вычислить
a8 mod n,
не следует применять примитивный подход с выполнением семи перемножений и одного приведения
по модулю громадного числа:
(a ? a ? a ? a ? a ? a ? a ? a) mod n.
Вместо этого выполняют три малых умножения и три малых приведения по модулю:
((a2 mod n)2 mod n)2 mod n.
Тем же способом вычисляют
a16 mod n = (((a2 mod n)2 mod n)2 mod n)2 mod n.
Вычисление
ax mod n,
где x не является степенью 2, лишь немного сложнее. Двоичная запись числа x позволяет пред-
ставить число x как сумму сте-пеней 2:
x = 25(10) > 1 1 0 0 1(2), поэтому 25 = 24 + 23 + 20.
Тогда
a25 mod n = (a?a24) mod n = (a?a8 ?a16) mod n =
= a ? ((a2)2)2 ? (((a2)2)2)2 mod n = ((((a2 ? a)2)2)2 ? a) mod n.
При разумном накоплении промежуточных результатов потребуется только шесть умножений:
(((((((a2 mod n) ? a) mod n)2 mod n)2 mod n)2 mod n) ? a) mod n.
Этот метод уменьшает трудоемкость вычислений до 1,5хk операций в среднем, где k – длина числа в
битах [123].
Поскольку многие алгоритмы шифрования основаны на возведении в степень по модулю n,
целесообразно использовать алгоритмы быстрого возведения в степень.


Алгоритм Евклида для нахождения наибольшего общего делителя
Целое число a делит без остатка другое целое число b, если, и только если
b=k?a
для некоторого целого числа k. В этом случае a называют делителем числа b или множителем в
разложении числа b на множители.
Пусть a – целое число, большее 1. Тогда a является простым числом, если его единствен-
ными положительными делителями будут 1 и само a, в противном случае a называется состав-
ным.
Любое целое n >1 может быть представлено единственным образом с точностью до порядка
сомножителей как произведение простых [45].
Существенный с точки зрения криптографии факт состоит в том, что не известно никакого
эффективного алгоритма разложения чисел на множители; не было получено и никакой нетривиаль-
ной нижней оценки временной сложности разложения. Никаких эффективных методов не известно
даже в таком простом случае, когда необходимо восстановить два простых числа p и q из их произ-
ведения:
n = p ? q.
Наибольший общий делитель чисел a и b, обозначаемый как НОД (a,b) или просто (a,b), –
это наибольшее целое, делящее одновременно числа a и b. В эквивалентной форме (a,b) – это то
единственное натуральное число, которое делит a и b и делится на любое целое, делящее и a и
b. Если НОД (a,b)=1, то целые a и b – взаимно простые.
Наибольший общий делитель может быть вычислен с помощью алгоритма Евклида. Евклид
описал этот алгоритм в своей книге "Начала", написанной около 300 лет до н.э. Он не изобрел его.
Историки полагают, что этот алгоритм, возможно, старше еще на 200 лет. Это древнейший нетриви-
альный алгоритм, который просуществовал до настоящего времени и все еще хорош и сего-
дня.
Опишем алгоритм Евклида для нахождения НОД (a,b). Введем обозначения: qi – частное; ri –
остаток. Тогда алгоритм можно представить в виде следующей цепочки равенств:
a = b ? q1 + r1, 0 < r1< b,
b = r1 ? q2 + r2, 0 < r2< r1,
r1 = r2 ? q3 + r3, 0 < r3< r2,
M M
rk–2 = rk–1 ? qk + rk, 0 < rk< rk–1,
rk–1 = rk ? qk+1.
Остановка гарантируется, поскольку остатки ri от делений образуют строго убывающую по-
следовательность натуральных чисел. Из этой цепочки немедленно получаем, что rk есть общий де-
литель чисел a и b и, более того, что любой общий делитель чисел a и b делит и rk. Таким
образом, rk = НОД (a, b) или rk = (a, b).
Алгоритм Евклида для вычисления наибольшего общего делителя
begin
g0: = b;
g1: = a;
i : =1.
while gi! = 0 do
begin
gi+1 : = gi–1 mod gi;
i : = i +1
end
gcd : = gi–1 {gcd – результат}
end


Вычисление обратных величин
В арифметике действительных чисел нетрудно вычислить мультипликативную обратную ве-
личину a–1 для ненулевого a:
a–1 =1/a или a ? a–1 =1.
Например, мультипликативная обратная величина от числа 4 равна 1/4, поскольку
1
4 ? =1.
4
В модулярной арифметике вычисление обратной величины является более сложной задачей.
Например, решение сравнения
4 ? x ?1 (mod 7)
эквивалентно нахождению таких значений x и k, что
4 ? x ? 7 ? k +1,
где x и k – целые числа.
Общая формулировка этой задачи – нахождение такого целого числа x, что
a ? x (mod n) =1.
Можно также записать
a–1 ? x (mod n).
Решение этой задачи иногда существует, а иногда его нет. Например, обратная величина для
числа 5 по модулю 14 равна 3, поскольку
5 ? 3 =15 ? 1 (mod 14).
С другой стороны, число 2 не имеет обратной величины по модулю 14.
Вообще сравнение
a–1 ? x (mod n)
имеет единственное решение, если a и n – взаимно прос-тые числа.
Если числа a и n не являются взаимно простыми, тогда сравнение
a–1 ? x (mod n)
не имеет решения [45].
Сформулируем основные способы нахождения обратных величин. Пусть целое число a ? {0,
1, 2, …, n – 1}.
Если НОД (a, n) =1, то a ? i (mod n) при i = 0, 1, 2, …, n –1 является перестановкой множества {0, 1,
2, …, n – 1}.
Например, если a = 3 и n = 7 (НОД (3,7) =1), то
3 ? i (mod 7) при i = 0, 1, 2, …, 6
является последовательностью 0, 3, 6, 2, 5, 1, 4, т.е. перестановкой множества {0, 1, 2, …, 6}.
Это становится неверным, когда НОД (a, n) ? 1. Например, если a = 2 и n = 6, то
2 ? i (mod 6) ? 0, 2, 4, 0, 2, 4 при i = 0, 1, 2, …, 5.
Если НОД (a,n) =1, тогда существует обратное число a–1, 0 < a–1 < n, такое, что
a ? a–1 ?1 (mod n).
Действительно, a ? i (mod n) является перестановкой 0, 1, ..., n –1, поэтому существует i, такое, что
a ? i ?1 (mod n).
Как уже отмечалось, набор целых чисел от 0 до n –1 называют полным набором вычетов
по модулю n. Это означает, что для любого целого числа a (a > 0) его вычет r = a (mod n) – это
некоторое целое число в интервале от 0 до n –1.
Выделим из полного набора вычетов подмножество вычетов, взаимно простых с n. Такое
подмножество называют приведенным набором вычетов.
Пример. Пусть модуль n =11 – простое число. Полный набор вычетов по модулю 11
{0, 1, 2, …, 10}.
При формировании приведенного набора вычетов из них удаляется только один элемент – 0. Приведенный набор вычетов по
модулю 11 имеет 11 – 1 = 10 элементов.

Вообще приведенный набор вычетов по модулю простого числа n имеет n –1 элементов.
Пример. Пусть модуль n =10. Полный набор вычетов по модулю n =10
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Из них только 1, 3, 7, 9 не имеют общего сомножителя с числом 10. Поэтому приведенный набор вычетов по модулю 10 равен
{1, 3, 7, 9}. При формировании этого приведенного набора были исключены элементы:
0 (1 элемент),
кратные 2 (4 элемента),
кратные 5 (1 элемент),
т.е. всего шесть элементов. Вычитая их из 10, получаем 10 – 1 – 4 – 1 = 4, т.е. четыре элемента в приведенном наборе.

Для произведения простых чисел p ? q = n приведенный набор вычетов имеет (p –1)(q –1)
элементов. При n=p ? q=2 ? 5=10 число элементов в приведенном наборе
(p – 1)(q – 1) = (2 – 1) (5 –1) = 4.
3
Пример. Приведенный набор вычетов по модулю 27=3 имеет 18 элементов:
{1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26}.
Из полного набора вычетов исключены элементы, кратные 3 (всего девять элементов).
r r–1
Для модуля в виде простой степени n приведенный набор вычетов имеет n (n –1) элементов.
3–1 2
При n = 3, r = 3 получаем 3 (3 –1) = 3 ? 2 =18.

Функция Эйлера ?(n) характеризует число элементов в приведенном наборе вычетов (табл.
П.1).
Таблица П.1
Функция ?(n)
Модуль n

n – простое n –1
2
n n (n –1)
… …
r r–1
n n (n – 1)
p ? q (p, q – простые) (p – 1) (q – 1)


t
t
? pi ei?1 (pi ? 1)
? pi ei (pi – простые)
i=1
i=1

Иначе говоря, функция ?(n) – это количество положительных целых, меньших n, которые вза-
имно просты с n [123].
Малая теорема Ферма: если n– простое и НОД (a,n)=1, то
an–1 ?1 (mod n).
Согласно обобщению Эйлером малой теоремы Ферма имеем: если НОД (a,n) =1, то
a?(n) ?1 (mod n).
Если n – простое число, то предыдущий результат, учитывая, что ?(n) = n –1, приводится к виду (ма-
лой теоремы Ферма)
an–1 ?1 (mod n).
Основные способы нахождения обратных величин
a–1 ? 1 (mod n).
1. Проверить поочередно значения 1, 2, ..., n – 1, пока не будет найден a–1 ?1 (mod n), такой,
что a?a–1 (mod n) ? 1.
2. Если известна функция Эйлера ?(n), то можно вы-числить
a–1 (mod n) ? a?(n)–1 (mod n),
используя алгоритм быстрого возведения в степень.
3. Если функция Эйлера ?(n) не известна, можно использовать расширенный алгоритм Евк-
лида.
Проиллюстрируем эти способы на числовых примерах.
1. Поочередная проверка значений 1, 2, ..., n – 1, пока не будет найден x = a–1 (mod n), такой
что a ? x ? 1 (mod n).
Пусть n = 7, a = 5. Требуется найти x = a–1 (mod n).
a ? x ? 1 (mod n) или 5 ? x ? 1 (mod 7).
n – 1 = 7 – 1 = 6.
–1
Получаем x = 5 (mod 7) = 3.
Результаты проверки сведены в табл. П.2.
Таблица П.2
5?x 5 ? x (mod 7)
x

1 5 5
2 10 3

<< Предыдущая

стр. 46
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>