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

стр. 4
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

это остаток от деления некоторого числа на N. Поскольку все срав­
нимые между собой по модулю N целые числа имеют один и тот
же остаток, мы можем считать, что элемент х G Z/iVZ изображает
целый класс чисел вида х + kN^ где А G Z. Таким образом, оперируя
:
с целыми числами по модулю 7V, мы будем считать все сравнимые
между собой числа равными друг другу и использовать традицион­
ный знак «= » вместо « =».
На множестве Z/iVZ есть две основных операции — сложение и
умножение. Они определяются обычным путем, например,
(11 + 13) (mod 16) = 24 (mod 16) = 8,
^Отсюда название «арифметика остатков». — Прим. перев.
Глава 1. Сравнения^ группы, конечные поля и вероятность

так как 24 = 1 • 16 + 8, и
(11 • 13) (mod 16) = 143 (mod 16) = 15,
поскольку 143 = 8-16 + 15.

1.1Л. Г р у п п ы и кольца
Сложение и умножение по модулю N работают почти так же, как
арифметические операции над вещественными и целыми числами.
В частности, они обладают следующими свойствами.
1. Замкнутость сложения:
Va, beZ/NZ: a+ beZ/NZ,
2. Ассоциативность сложения:
Va, b, се Z/NZ : {а Л-b)-\-с = а-h {b-\-с).
3. Нуль является единичным элементом (или единицей) по сло­
жению:
Va е Z/NZ : а-\-0 = 0-\-а = а,
4. Всегда существует обратный элемент по сложению {противо-
полоэюный):
Va G Z/NZ : а + (iV - а) - (TV - а) + а = 0.
5. Коммутативность сложения:
Va, be Z/NZ: a + b = b-\-a.
6. Замкнутость умножения:
\/а, be Z/NZ: a-beZ/NZ,
7. Ассоциативность умножения:
Va, b, се Z/NZ : {а - b) - с=^ а - {b - с),
8. Число 1 является единичным элементом (единицей) по умно­
жению:
MaeZ/NZ: а • 1 -= 1 • а = а.
9. Умножение и сложение связаны законом дистрибутивности:
Va, 6, с G Z/NZ : {аЛ-Ь) - с^ а-c-Vb - с,
10. Коммутативность умножения:
Va, be Z/NZ: a'b = b'a.
1.1. Арифметика остатков

Многие множества, с которыми мы будем встречаться, наделены
некоторыми из этих свойств. Введем для таких множеств специаль­
ные термины.

Определение 1.1. Группой называется множество с операцией,
которая
- замкнута,
- обладает единицей,
- ассоциативна;
- относительно нее каждый элемент обладает обратным.

Группу с коммутативной операцией называют коммутативной^
или абелевой. Почти все группы, встречающиеся в криптографии, —
абелевы, поскольку именно свойство коммутативности придает им
криптографический интерес. Итак, любое множество с операцией,
удовлетворяющее свойствам 1, 2, 3 и 4 из перечисленных выше, на­
зывается группой, а если операция удовлетворяет еще и свойству 5,
то — абелевой группой.
Стандартные примеры групп, с которыми Вы встречаетесь еще
в школе, это:
- Целые, вещественные или комплексные числа по сложению. Еди­
ницей здесь является обычный О, а обратным к х служит —ж,
т.к. X -\- {—х) = 0.
- Ненулевые рациональные, вещественные или комплексные чи­
сла. Единица в них — это 1, и обратным к х будет ж˜^, по­
скольку X • х˜^ =^\.
Группа называется мультипликативной^ если мы записываем ее
операцию как умножение, т. е. точкой:
f =9'h и 9^ =9'9'9'9-9'
Такую группу мы обозначаем (G, •) в том случае, когда возможны
сомнения относительно используемой в ней операции. Группу назы­
вают аддитивной^ если ее операция записывается как сложение:
f =g+h и 5-9 = 9 + 9 + 9 + 9 +9-
Для аддитивных групп мы используем обозначение (G, +). Абелева
группа называется циклической^ если в ней есть такой специальный
элемент (образующая)^ что любой другой элемент группы получа­
ется многократным применением к нему^ групповой операции. На-
2
И обратному к образующей. — Прим. перев.
Глава 1. Сравнения, группы, конечные поля и вероятность

пример, в группе целых чисел по сложению любой элемент можно
получить в результате многократного сложения 1 (или —1) с собой.
Действительно,
7 = 1 + 1 + 1 + 1 + 1 + 1 + 1, - 2 - (-1) + (-1).
Таким образом, число 1 — образующая группы целых чисел по сло­
жению.
Если д — образующая циклической группы G, мы пишем G = {д),
В мультипликативном случае каждый элемент h группы G можно
записать в виде


а в аддитивном
h=^X'g,
где X в обоих случаях — некоторое целое число, называемое дис­
кретным логарифмом элемента h по основанию д.
Введем понятие кольца.

Определение 1.2. Кольцо — это множество R с двумя операци­
ями, сложением и умножением, традиционно обозначаемыми «+» и
«•», которые обладают свойствами 1-9 со стр. 24. Мы можем обозна­
чать кольцо вместе с его операциями тройкой (Д, •, +).
Если окажется, что умножение в данном кольце коммутативно,
то мы будем называть его коммутативным кольцом.
Такое определение на первый взгляд может показаться сложным,
но оно просто суммирует многообразные свойства множеств, с ко­
торыми мы постоянно имеем дело. Например, Вы знакомы с беско­
нечными коммутативными кольцами целых, вещественных и ком­
плексных чисел. Множество остатков Z/NZ с операциями сложения
и умножения тоже является коммутативным кольцом, которое ча­
сто называют кольцом вычетов по модулю N, Кольцо вычетов —
один из центральных объектов криптографии, на свойствах кото­
рого основаны многие методы шифрования.

1.1.2. Ф у н к ц и я Э й л е р а
Одна из центральных задач арифметики остатков — это решение
уравнения
а • X = b (modiV),
т. е. поиск элемента х G Z/A/'Z, удовлетворяющего этому равенству.
Линейное уравнение ах = b с вещественными коэффициентами при
1.1. Арифметика остатков

а 7^ О всегда разрешимо. Если же рассматривать его над кольцом
целых чисел, то ответ найдется не всегда. Например, не суш;ествует
целого числа ж, обраш;ающего уравнение 2гг = 5 в верное равенство.
Случай же кольца вычетов еш;е более сложный, а потому и интерес­
ный с любой точки зрения. Действительно, суш;ествует ровно одно
решение уравнения
7-д: = 3 (mod 143),
уравнение
11-ж = 3 (mod 143)
решений не имеет, в то время как множество решений уравнения
1 1 . ^ = 22 (mod 143)
насчитывает 11 элементов. Таким образом, встает вопрос: при ка­
ких условиях на а, 6 и ЛГ уравнение ах = b (mod N) имеет решения
и как их все найти?
К счастью, существует очень простой критерий, позволяюш;ий
определить, имеет ли данное уравнение ни одного, одно или много
решений. Мы просто вычисляем наибольший общий делитель чисел
аиМ: Н0Д(а,7У).
- Если НОД (а, 7V) = 1, то существует ровно одно решение. Оно
может быть найдено с помощью промежуточного числа с, удо­
влетворяющего уравнению а-с = 1 (modiV), после чего искомое
неизвестное х вычисляется по формуле х = b - с (modiV).
- Если НОД {а^ N) ^ 1 и д = НОД (а, N) делит 6, то уравнение
будет иметь д решений. Чтобы их найти, нужно разделить
исходное уравнение на д:
а' -х' = Ь' (modiV'),
где а' = | , 6' = I и ЛГ' = ^ . Если ж' — решение полученного
уравнения, то решение исходного — любое число вида
x' + i- N'
X

где г = 0, 1, . . . , ^ - 1.
- В других случаях решений нет.
Ситуация, когда НОД(а,Л^) = 1, настолько важна, что А^ЛЯ нее
вводится специальное название. Говорят, что числа а и N взаимно
просты.
Число элементов кольца Z/7VZ, взаимно простых с 7V, дается
функцией Эйлера (р и равно ^{N). Значение (p{N) можно найти по
28 Глава 1. Сравнения, группы, конечные поля и вероятность

разложению числа N на простые множители. Если



где Pi — различные простые числа, то

v'W = ПРГЧР» -1).

Заметим, что последнее утверждение очень важно с точки зре­
ния криптографии: по разлоэюению числа N на простые множите­
ли легко вычислить значение (f{N). Особый интерес представляют
следующие частные случаи:
1. Если р простое, то
ip{p) =р-1.

2. Если р и q — простые числа и р ^ q^ то
(p{p'q) = {p-l){q-l).

1.1.3. М у л ь т и п л и к а т и в н ы е о б р а т н ы е п о м о д у л ю Л^
Решая уравнение вида
ах — Ь (modiV),
мы приходим к вопросу о существовании мультипликативного обрат­
ного у числа а по модулю N. Иначе говоря, необходимо выяснить,
существует ли число с, удовлетворяющее равенству
ас = са^\ (mod iV)?
Такое число с естественно обозначить через а˜^, Как уже было от­
мечено, обратный к а существует только тогда, когда ai/iN взаимно
просты, т.е. НОД(а,Л/^) = 1. Особенно интересен случай простого
модуля N = р^ поскольку при этом А^ля любого ненулевого элемента
а G Z/NZ найдется единственное решение уравнения
ах = 1 (modp).
Итак, если р — простое число, то любой ненулевой элемент в Z/pZ
обладает мультипликативным обратным^. Кольца с таким свойст­
вом называются полями.

^То есть обратим. — Прим. перев.
1.1. Арифметика остатков

Определение 1.3. Полем называется множество (F, •,+) с двумя
операциями, обладающее дополнительными свойствами:
- (F, +) — абелева группа с единичным элементом О,
- {F \ {0}, •) — абелева группа с единичным элементом 1,
- (F, •, +) удовлетворяет закону дистрибутивности^.

Следовательно, поле — это коммутативное кольцо, в котором
каждый ненулевой элемент обратим. С полями Вы уже тоже встре­
чались. Например, таковыми являются множества рациональных,
вещественных и комплексных чисел.
Определим множество обратимых элементов в Z/NZ как
(Z/iVZ)* = {хе Z/NZ\ ЯОД{х,М) = 1}.
Для общего кольца А обозначение А* закреплено А,ЛЯ наибольшего
его подмножества элементов, которые образуют группу по умноже­
нию. В нашей ситуации легко проверить, что множество (Z/NZ)* —
группа по умножению с числом элементов (p{N).
В специальном случае, когда N = р — простое число, получаем:
(Z/pZ)* = {l, . . . , р - 1 } ,
поскольку каждый ненулевой элемент кольца Z/pZ взаимно прост
ери поэтому обратим. Иными словами, Z/pZ является конечным
полем, которое обычно называется полем вычетов по модулю р и
обозначается символом ?р. Как следует из определения, мультипли­
кативная группа F* поля F совпадает с множеством F \ { 0 } . В част­
ном случае поля вычетов получаем
Fp = z/pz = {о,...,р-1} и F; = {z/pzy = {1,...,р-1}.
Далее мы обсудим конечные поля более общего типа, а сейчас от­
метим лишь тот существенный момент, что целые числа по модулю
N образуют поле тогда и только тогда, когда N — простое число.
Этот параграф заканчивается самой важной теоремой из эле­
ментарной теории конечных групп.

Теорема 1.4. (Теорема Лагранжа.) Если (G, •) — группа по­
рядка (с числом элементов) п = #G^ то каждый ее элемент а Е G
удовлетворяет соотношению а^ = 1.
Таким образом, для х G (Z/iVZ)* выполнено равенство
а;^(^) = 1 (modTV),
Нужно также потребовать, чтобы Q ф 1. — Прим. перев.
Глава 1. Сравнения, группы, конечные поля и вероятность

поскольку #(Z/iVZ)* = ^{Ю- Это следствие теоремы Лагранжа
подводит нас к малой теореме Ферма (не путать с великой теоремой
Ферма, в корне отличной от малой).

Теорема 1.5. (Малая теорема Ферма.) Предположим, что число
р простое и а G F*; тогда
а^ = 1 (modp).

Малая теорема Ферма является частным случаем теоремы Ла­
гранжа и служит основой одного из тестов на простоту, который
будет рассматриваться в следующих главах.


1.2. Конечные поля
Целые числа по простому модулю — не единственный пример ко­
нечных полей. Здесь мы разберем еще один, более общий, тип конеч­
ных полей, представляющий интерес А^ЛЯ криптографии. Упомяну­
тый общий тип полей будет использоваться лишь при обсуждении
блочного шифра Rijndael^ поточного шифра, основывающегося на
регистре сдвига с обратными связями, и при изучении криптоси­
стем, связанных с эллиптической кривой. Поэтому при первом чте­
нии этот параграф можно пропустить.
Закрепим букву р за простым числом и рассмотрим множество
многочленов от переменной х с коэффициентами из F^. Это мно­

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

стр. 4
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>