Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

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

Из Википедии — свободной энциклопедии

Мультипликативная группа кольца вычетов по модулю 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.[en] : journal. — 1986. — Vol. 46. — P. 259—279.
  7. Алферов и др., 2002.

Литература

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

Ссылки

Эта страница в последний раз была отредактирована 31 июля 2021 в 08:15.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).