Мультипликативная группа кольца вычетов
Мультипликативная группа кольца вычетов по модулю m — мультипликативная группа обратимых элементов кольца вычетов по модулю m. При этом в качестве множества элементов может рассматриваться любая приведенная система вычетов по модулю m.
Приведённая система вычетов
Приведённая система вычетов по модулю m — множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. В качестве приведённой системы вычетов по модулю m обычно берутся взаимно простые с m числа от 1 до m — 1[1].
Пример: приведенной системой вычетов по модулю 42 будет: { 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41 }.
Свойства
- Набор любых (функция Эйлера) попарно несравнимых по модулю m и взаимно простых с m чисел образует приведённую систему вычетов по модулю [1].
- Если НОД(a,m) = 1, то множество значений ax, где x пробегает приведенную систему вычетов по модулю m, также является приведенной системой вычетов по модулю m[2].
- Если НОД(k,m) = 1, то множество значений kx + my, где x пробегает приведенную систему вычетов по модулю m и y пробегает приведенную систему вычетов по модулю k, является приведенной системой вычетов по модулю km[3].
- В случае, когда число m простое, приведенная система вычетов по модулю m отличается от полной системы вычетов отсутствием нуля[4].
- Если a — элемент приведенной системы вычетов по модулю m, то, для любого b сравнение разрешимо относительно x[4].
Приведённая система вычетов с умножением по модулю m образует группу, называемую мультипликативной группой или мультипликативной группой обратимых элементов кольца вычетов по модулю m, которая обозначается или [4].
Если m простое, то, как отмечалось выше, элементы 1, 2, …,m-1 входят в . В этом случае кольцо вычетов является полем[4].
Формы записи
Кольцо вычетов по модулю n обозначают или . Его мультипликативную группу, как и в общем случае групп обратимых элементов колец, обозначают .
Простейший случай
Чтобы понять структуру группы , можно рассмотреть частный случай , где — простое число, и обобщить его. Рассмотрим простейший случай, когда , то есть .
Теорема: — циклическая группа. [5]
Пример: Рассмотрим группу
- = {1,2,4,5,7,8}
- Генератором группы является число 2.
- Как видим, любой элемент группы может быть представлен в виде , где . То есть группа — циклическая.
Общий случай
Для рассмотрения общего случая необходимо определение примитивного корня. Примитивный корень по простому модулю — это число, которое вместе со своим классом вычетов порождает группу .[5]
- Примеры: 2 — примитивный корень по модулю 11; 8 — примитивный корень по модулю 11; 3 не является примитивным корнем по модулю 11.
В случае целого модуля определение такое же.
Структуру группы определяет следующая теорема: Если p — нечётное простое число и — целое положительное, то существуют примитивные корни по модулю , то есть — циклическая группа.
Из китайской теоремы об остатках следует, что при имеет место изоморфизм ≈ .
Группа — циклическая. Её порядок равен .
Группа — также циклическая порядка a при a = 1 или a = 2. При эта группа циклической не является и представляет собой прямое произведение двух циклических групп, порядков и .
Группа циклична тогда и только тогда, когда или или n = 2 или n = 4, где p — простое число. В общем случае как абелева группа представляется прямым произведением циклических примарных групп, изоморфных .[5]
Подгруппа свидетелей простоты
Пусть — нечётное число большее 1. Число однозначно представляется в виде , где нечётно. Целое число , , называется свидетелем простоты числа , если выполняется одно из условий:
или
- существует целое число , , такое, что
Если число — составное, существует подгруппа мультипликативной группы кольца вычетов, называемая подгруппой свидетелей простоты. Её элементы, возведённые в степень , совпадают с по модулю .
Пример: . Есть остатков, взаимно простых с , это и . эквивалентно по модулю , значит эквивалентно по модулю . Значит, и — свидетели простоты числа . В данном случае {1, 8} — подгруппа свидетелей простоты.[6]
Свойства
Экспонента группы
Экспонента группы равна функции Кармайкла .
Порядок группы
Порядок группы равен функции Эйлера: . Отсюда и из изоморфизма ≈ можно получить ещё один способ доказательства равенства при [5]
Порождающее множество
— циклическая группа тогда и только тогда, когда В случае циклической группы генератор называется первообразным корнем.
Пример
Приведённая система вычетов по модулю состоит из классов вычетов: . Относительно определённого для классов вычетов умножения они образуют группу, причём и взаимно обратны (то есть ), а и обратны сами себе.
Структура группы
Запись означает «циклическая группа порядка n».
Генератор группы | Генератор группы | Генератор группы | Генератор группы | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | C1 | 1 | 1 | 0 | 33 | C2×C10 | 20 | 10 | 2, 10 | 65 | C4×C12 | 48 | 12 | 2, 12 | 97 | C96 | 96 | 96 | 5 | |||
2 | C1 | 1 | 1 | 1 | 34 | C16 | 16 | 16 | 3 | 66 | C2×C10 | 20 | 10 | 5, 7 | 98 | C42 | 42 | 42 | 3 | |||
3 | C2 | 2 | 2 | 2 | 35 | C2×C12 | 24 | 12 | 2, 6 | 67 | C66 | 66 | 66 | 2 | 99 | C2×C30 | 60 | 30 | 2, 5 | |||
4 | C2 | 2 | 2 | 3 | 36 | C2×C6 | 12 | 6 | 5, 19 | 68 | C2×C16 | 32 | 16 | 3, 67 | 100 | C2×C20 | 40 | 20 | 3, 99 | |||
5 | C4 | 4 | 4 | 2 | 37 | C36 | 36 | 36 | 2 | 69 | C2×C22 | 44 | 22 | 2, 68 | 101 | C100 | 100 | 100 | 2 | |||
6 | C2 | 2 | 2 | 5 | 38 | C18 | 18 | 18 | 3 | 70 | C2×C12 | 24 | 12 | 3, 69 | 102 | C2×C16 | 32 | 16 | 5, 101 | |||
7 | C6 | 6 | 6 | 3 | 39 | C2×C12 | 24 | 12 | 2, 38 | 71 | C70 | 70 | 70 | 7 | 103 | C102 | 102 | 102 | 5 | |||
8 | C2×C2 | 4 | 2 | 3, 5 | 40 | C2×C2×C4 | 16 | 4 | 3, 11, 39 | 72 | C2×C2×C6 | 24 | 6 | 5, 17, 19 | 104 | C2×C2×C12 | 48 | 12 | 3, 5, 103 | |||
9 | C6 | 6 | 6 | 2 | 41 | C40 | 40 | 40 | 6 | 73 | C72 | 72 | 72 | 5 | 105 | C2×C2×C12 | 48 | 12 | 2, 29, 41 | |||
10 | C4 | 4 | 4 | 3 | 42 | C2×C6 | 12 | 6 | 5, 13 | 74 | C36 | 36 | 36 | 5 | 106 | C52 | 52 | 52 | 3 | |||
11 | C10 | 10 | 10 | 2 | 43 | C42 | 42 | 42 | 3 | 75 | C2×C20 | 40 | 20 | 2, 74 | 107 | C106 | 106 | 106 | 2 | |||
12 | C2×C2 | 4 | 2 | 5, 7 | 44 | C2×C10 | 20 | 10 | 3, 43 | 76 | C2×C18 | 36 | 18 | 3, 37 | 108 | C2×C18 | 36 | 18 | 5, 107 | |||
13 | C12 | 12 | 12 | 2 | 45 | C2×C12 | 24 | 12 | 2, 44 | 77 | C2×C30 | 60 | 30 | 2, 76 | 109 | C108 | 108 | 108 | 6 | |||
14 | C6 | 6 | 6 | 3 | 46 | C22 | 22 | 22 | 5 | 78 | C2×C12 | 24 | 12 | 5, 7 | 110 | C2×C20 | 40 | 20 | 3, 109 | |||
15 | C2×C4 | 8 | 4 | 2, 14 | 47 | C46 | 46 | 46 | 5 | 79 | C78 | 78 | 78 | 3 | 111 | C2×C36 | 72 | 36 | 2, 110 | |||
16 | C2×C4 | 8 | 4 | 3, 15 | 48 | C2×C2×C4 | 16 | 4 | 5, 7, 47 | 80 | C2×C4×C4 | 32 | 4 | 3, 7, 79 | 112 | C2×C2×C12 | 48 | 12 | 3, 5, 111 | |||
17 | C16 | 16 | 16 | 3 | 49 | C42 | 42 | 42 | 3 | 81 | C54 | 54 | 54 | 2 | 113 | C112 | 112 | 112 | 3 | |||
18 | C6 | 6 | 6 | 5 | 50 | C20 | 20 | 20 | 3 | 82 | C40 | 40 | 40 | 7 | 114 | C2×C18 | 36 | 18 | 5, 37 | |||
19 | C18 | 18 | 18 | 2 | 51 | C2×C16 | 32 | 16 | 5, 50 | 83 | C82 | 82 | 82 | 2 | 115 | C2×C44 | 88 | 44 | 2, 114 | |||
20 | C2×C4 | 8 | 4 | 3, 19 | 52 | C2×C12 | 24 | 12 | 7, 51 | 84 | C2×C2×C6 | 24 | 6 | 5, 11, 13 | 116 | C2×C28 | 56 | 28 | 3, 115 | |||
21 | C2×C6 | 12 | 6 | 2, 20 | 53 | C52 | 52 | 52 | 2 | 85 | C4×C16 | 64 | 16 | 2, 3 | 117 | C6×C12 | 72 | 12 | 2, 17 | |||
22 | C10 | 10 | 10 | 7 | 54 | C18 | 18 | 18 | 5 | 86 | C42 | 42 | 42 | 3 | 118 | C58 | 58 | 58 | 11 | |||
23 | C22 | 22 | 22 | 5 | 55 | C2×C20 | 40 | 20 | 2, 21 | 87 | C2×C28 | 56 | 28 | 2, 86 | 119 | C2×C48 | 96 | 48 | 3, 118 | |||
24 | C2×C2×C2 | 8 | 2 | 5, 7, 13 | 56 | C2×C2×C6 | 24 | 6 | 3, 13, 29 | 88 | C2×C2×C10 | 40 | 10 | 3, 5, 7 | 120 | C2×C2×C2×C4 | 32 | 4 | 7, 11, 19, 29 | |||
25 | C20 | 20 | 20 | 2 | 57 | C2×C18 | 36 | 18 | 2, 20 | 89 | C88 | 88 | 88 | 3 | 121 | C110 | 110 | 110 | 2 | |||
26 | C12 | 12 | 12 | 7 | 58 | C28 | 28 | 28 | 3 | 90 | C2×C12 | 24 | 12 | 7, 11 | 122 | C60 | 60 | 60 | 7 | |||
27 | C18 | 18 | 18 | 2 | 59 | C58 | 58 | 58 | 2 | 91 | C6×C12 | 72 | 12 | 2, 3 | 123 | C2×C40 | 80 | 40 | 7, 83 | |||
28 | C2×C6 | 12 | 6 | 3, 13 | 60 | C2×C2×C4 | 16 | 4 | 7, 11, 19 | 92 | C2×C22 | 44 | 22 | 3, 91 | 124 | C2×C30 | 60 | 30 | 3, 61 | |||
29 | C28 | 28 | 28 | 2 | 61 | C60 | 60 | 60 | 2 | 93 | C2×C30 | 60 | 30 | 11, 61 | 125 | C100 | 100 | 100 | 2 | |||
30 | C2×C4 | 8 | 4 | 7, 11 | 62 | C30 | 30 | 30 | 3 | 94 | C46 | 46 | 46 | 5 | 126 | C6×C6 | 36 | 6 | 5, 13 | |||
31 | C30 | 30 | 30 | 3 | 63 | C6×C6 | 36 | 6 | 2, 5 | 95 | C2×C36 | 72 | 36 | 2, 94 | 127 | C126 | 126 | 126 | 3 | |||
32 | C2×C8 | 16 | 8 | 3, 31 | 64 | C2×C16 | 32 | 16 | 3, 63 | 96 | C2×C2×C8 | 32 | 8 | 5, 17, 31 | 128 | C2×C32 | 64 | 32 | 3, 127 |
Применение
На сложности дискретного логарифмирования в мультипликативной группе кольца вычетов основана криптографическая стойкость шифрсистемы Эль-Гамаля.[7]
История
Вклад в исследование структуры мультипликативной группы кольца вычетов внесли Артин, Билхарц, Брауэр, Вильсон, Гаусс, Лагранж, Лемер, Варинг, Ферма, Хули, Эйлер. Лагранж доказал лемму о том, что если , и k — поле, то f имеет не более n различных корней, где n — степень f. Он же доказал важное следствие этой леммы, заключающееся в сравнении ≡ . Эйлер доказал малую теорему Ферма. Варинг сформулировал теорему Вильсона, а Лагранж её доказал. Эйлер предположил существование примитивных корней по модулю простого числа. Гаусс это доказал. Артин выдвинул свою гипотезу о существовании и количественной оценке простых чисел, по модулю которых заданное целое число является первообразным корнем. Брауэр внес вклад в исследование проблемы существования наборов последовательных целых чисел, каждое из которых — k-ая степень по модулю p. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезу Артина с предположением справедливости расширенной гипотезы Римана в полях алгебраических чисел.[5]
Примечания
- ↑ 1 2 И. М. Виноградов Основы теории чисел. изд. 9-е, перераб., М. : Наука. 1981
- ↑ Сагалович Ю. Л. Введение в алгебраические коды. 2011.
- ↑ Бухштаб, 1966.
- ↑ 1 2 3 4 В. Босс Лекции по математике. Том 14. Теория чисел. 2014.
- ↑ 1 2 3 4 5 Айерлэнд, Роузен, 1987.
- ↑ Erdős, Paul; Pomerance, Carl. On the number of false witnesses for a composite number (англ.) // Math. Comput.[англ.] : journal. — 1986. — Vol. 46. — P. 259—279.
- ↑ Алферов и др., 2002.
Литература
- Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — М.: Мир, 1987.
- Алферов А.П., Зубов А.Ю., Кузьмин А.С. Черемушкин А.В. Основы криптографии. — Москва: «Гелиос АРВ», 2002.
- Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. — Санкт-Петербург: НПО «Профессионал», 2004.
Ссылки
- Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966.
- Weisstein, Eric W. Modulo Multiplication Group (англ.) на сайте Wolfram MathWorld.