Мультипликативная группа кольца вычетов

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Мультипликативная группа кольца вычетов по модулю 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) — функция Эйлера) чисел, взаимно простых с 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 — нечётное простое число и l — целое положительное, то существуют примитивные корни по модулю , то есть  — циклическая группа.

Из китайской теоремы об остатках следует, что при имеет место изоморфизм .

Группа  — циклическая. Её порядок равен .

Группа  — также циклическая порядка a при a=1 или a=2. При эта группа циклической не является и представляет собой прямое произведение двух циклических групп, порядков и .

Группа циклична тогда и только тогда, когда или или n = 2 или n = 4, где p — нечётное простое число. В общем случае как абелева группа представляется прямым произведением циклических примарных групп, изоморфных .[5]

Подгруппа свидетелей простоты[править | править код]

Пусть  — нечётное число большее 1. Число однозначно представляется в виде , где нечётно. Целое число , , называется свидетелем простоты числа , если выполняется одно из условий:

или

  • существует целое число , , такое, что

Если число  — составное, существует подгруппа мультипликативной группы кольца вычетов, называемая подгруппой свидетелей простоты. Её элементы, возведённые в степень , совпадают с по модулю .

Пример: . Есть остатков, взаимно простых с , это и . эквивалентно по модулю , значит эквивалентно по модулю . Значит, и  — свидетели простоты числа . В данном случае {1, 8} — подгруппа свидетелей простоты.[6]

Свойства[править | править код]

Экспонента группы[править | править код]

Экспонента группы равна функции Кармайкла .

Порядок группы[править | править код]

Порядок группы равен функции Эйлера: . Отсюда и из изоморфизма можно получить ещё один способ доказательства равенства при [5]

Порождающее множество[править | править код]

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

Пример[править | править код]

Приведённая система вычетов по модулю состоит из классов вычетов: . Относительно определённого для классов вычетов умножения они образуют группу, причём и взаимно обратны (то есть ), а и обратны сами себе.

Структура группы[править | править код]

Запись означает «циклическая группа порядка n».

Структура группы (Z/nZ)×
Генератор группы   Генератор группы   Генератор группы   Генератор группы
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. 1 2 И. М. Виноградов Основы теории чисел. изд. 9-е, перераб., М. : Наука. 1981
  2. Сагалович Ю. Л. Введение в алгебраические коды. 2011.
  3. Бухштаб, 1966.
  4. 1 2 3 4 В. Босс Лекции по математике. Том 14. Теория чисел. 2014.
  5. 1 2 3 4 5 Айерлэнд, Роузен, 1987.
  6. Erdős, Paul (англ.); Pomerance, Carl. On the number of false witnesses for a composite number (англ.) // Math. Comput. (англ.) : journal. — 1986. — Vol. 46. — P. 259—279.
  7. Алферов и др., 2002.

Литература[править | править код]

  • Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — М.: Мир, 1987.
  • Алферов А.П., Зубов А.Ю., Кузьмин А.С. Черемушкин А.В. Основы криптографии. — Москва: «Гелиос АРВ», 2002.
  • Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. — Санкт-Петербург: НПО «Профессионал», 2004.

Ссылки[править | править код]

  • Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966.
  • Weisstein, Eric W. Modulo Multiplication Group (англ.) на сайте Wolfram MathWorld.