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

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

Приведённая система вычетов по модулю m — множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(·) — функция Эйлера.

В качестве приведённой системы вычетов по модулю m обычно берутся взаимно простые с m числа от 1 до m-1.

Приведённая система вычетов с умножением по модулю m образует группу, называемую мультипликативной группой или группой обратимых элементов кольца вычетов по модулю m, которая обозначается \mathbb{Z}_m^{\times} или U(\mathbb{Z}_m).

Содержание

Аксиоматика группы

Легко показать, что группа классов взаимнопростых с n вычетов по умножению удовлетворяет аксиоматике абелевой группы. Т.к. сравнение a ≡ b (mod n) предполагает равенство НОД(a,n)=НОД(b,n), то понятие эквивалентных классов вычетов по модулю n, взаимно простых с n, четко определено. Т.к. равенства НОД(a,n)=1 и НОД(b,n)=1 предполагают равенство НОД(ab,n)=1, то множество классов вычетов по модулю n, взаимно простых с n, замкнуто относительно умножения. При a, удовлетворяющем равенству НОД(a,n)=1, нахождение x, удовлетворяющего сравнению ax ≡ 1 (mod n), равносильно решению уравнения ax + ny = 1, которое может быть решено путем соотношения Безу. Найденное x будет обладать свойством НОД(x,n)=1.

Простейший случай

Чтобы понять структуру группы \mathbb{Z}_n^{\times}, можно рассмотреть частный случай n=p^a, где p - простое число, и обобщить его. Рассмотрим простейший случай, когда a=1, т.е. n=p.

Теорема: \mathbb{Z}_p^{\times} — циклическая группа. [1]

Общий случай

Для рассмотрения общего случая необходимо определение примитивного корня. Примитивный корень по простому модулю p – это число, которое вместе со своим классом вычетов порождает группу U(\mathbb{Z}/p\mathbb{Z}). Примеры: 2 — примитивный корень по модулю 11; 8 — примитивный корень по модулю 11; 3 не является примитивным корнем по модулю 11. В случае целого модуля n определение такое же.

Теорема: Если p – нечетное простое число и l – целое положительное, то существуют примитивные корни по модулю p^{l} т.е. U(\mathbb{Z}/p^{l}\mathbb{Z}) - циклическая группа. Из китайской теоремы об остатках следует, что при n=p_1^{a_1}p_2^{a_2}...p_l^{a_l}  имеет место изоморфизм U(\mathbb{Z}/n\mathbb{Z})U(\mathbb{Z}/p_1^{a_1}\mathbb{Z})\times U(\mathbb{Z}/p_2^{a_2}\mathbb{Z})\times ... U(\mathbb{Z}/p_l^{a_l}\mathbb{Z}). Группа U(\mathbb{Z}/p_i^{a_i}\mathbb{Z}) - циклическая. Ее порядок равен p_i^{a_i-1}(p_i-1). Группа U(\mathbb{Z}/2^{a}\mathbb{Z}) - также циклическая. Ее порядок равен a при a=1 или a=2. При a \geqslant 3 эта группа есть прямое произведение двух циклических групп, порядков 2 и 2^{a-2}. Группа U(\mathbb{Z}/n\mathbb{Z}) циклична тогда и только тогда, когда n=p^a или n=2p^a или n = 2 или n = 4, где p — нечётное простое число. В общем случае U(\mathbb{Z}/n\mathbb{Z}) как абелева группа представляется прямым произведением циклических примарных групп, изоморфных \mathbb{Z}_{u_i}^{+}. [1]

Формы записи

Кольцо вычетов по модулю n обозначают \mathbb{Z}/n\mathbb{Z}  или \mathbb{Z}_n. Мультипликативную группу кольца вычетов обозначают (\mathbb{Z}/n\mathbb{Z})^*,   (\mathbb{Z}/n\mathbb{Z})^\times,   U(\mathbb{Z}/n\mathbb{Z}),   E(\mathbb{Z}/n\mathbb{Z})  , \mathbb{Z}_n^{\times},  U(\mathbb{Z}_n).

Подгруппа свидетелей простоты

Пусть ~m — нечётное число большее 1. Число ~m-1 однозначно представляется в виде m-1 = 2^s \cdot t, где ~t нечётно. Целое число ~a, ~1 < a < m, называется свидетелем простоты числа ~m, если выполняется одно из условий:

  • ~a^t\equiv 1\pmod m

или

  • существует целое число ~k, ~0\leq k<s, такое, что ~ a^{2^kt}\equiv m-1\pmod m.

Если число n – составное, существует подгруппа мультипликативной группы кольца вычетов, называемая подгруппой свидетелей простоты. Ее элементы, возведенные в степень n-1, совпадают с 1 по модулю n. Пример: n=9 Есть 6 остатков, взаимно простых с 9, это 1,2,4,5,7 и 8. 8 эквивалентно -1 по модулю 9, значит 8^{8} эквивалентно 1 по модулю 9. Значит, 1 и 8 — свидетели простоты числа 9. В данном случае {1, 8} — подгруппа свидетелей простоты.

Свойства

Экспонента группы

Экспонента группы равна функции Кармайкла (англ.): для нечетных m она равна \textstyle \operatorname{lcm}(p_1^{a_1-1}(p_1-1),\cdots, p_s^{a_s-1}(p_s-1)), а для чётных — в 2 раза меньше.

Порядок группы

Порядок группы равен функции Эйлера: |U(\mathbb{Z}/p^{l}\mathbb{Z})|=\varphi(n).

Порождающее множество

U(\mathbb{Z}/n\mathbb{Z}) - циклическая группа тогда и только тогда, когда \varphi(n)=\lambda(n). В случае циклической группы генератор называется первообразным корнем.

Пример

Приведённая система вычетов по модулю 10 состоит из 4 классов вычетов: [1]_{10}, [3]_{10}, [7]_{10}, [9]_{10}. Относительно определённого для классов вычетов умножения они образуют группу, причём [3]_{10} и [7]_{10} взаимно обратны (то есть [3]_{10}{\cdot}[7]_{10} = [1]_{10}), а [1]_{10} и [9]_{10} обратны сами себе.

Структура группы

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

Структура группы U(\mathbb{Z}/n\mathbb{Z})
n\; U(\mathbb{Z}/n\mathbb{Z}) \varphi(n) \lambda(n)\; генератор   n\; U(\mathbb{Z}/n\mathbb{Z}) \varphi(n) \lambda(n)\; генератор
2 C1 1 1 1 33 C2×C10 20 10 10, 2
3 C2 2 2 2 34 C16 16 16 3
4 C2 2 2 3 35 C2×C12 24 12 6, 2
5 C4 4 4 2 36 C2×C6 12 6 19, 5
6 C2 2 2 5 37 C36 36 36 2
7 C6 6 6 3 38 C18 18 18 3
8 C2×C2 4 2 7, 3 39 C2×C12 24 12 38, 2
9 C6 6 6 2 40 C2×C2×C4 16 4 39, 11, 3
10 C4 4 4 3 41 C40 40 40 6
11 C10 10 10 2 42 C2×C6 12 6 13, 5
12 C2×C2 4 2 5, 7 43 C42 42 42 3
13 C12 12 12 2 44 C2×C10 20 10 43, 3
14 C6 6 6 3 45 C2×C12 24 12 44, 2
15 C2×C4 8 4 14, 2 46 C22 22 22 5
16 C2×C4 8 4 15, 3 47 C46 46 46 5
17 C16 16 16 3 48 C2×C2×C4 16 4 47, 7, 5
18 C6 6 6 5 49 C42 42 42 3
19 C18 18 18 2 50 C20 20 20 3
20 C2×C4 8 4 19, 3 51 C2×C16 32 16 50, 5
21 C2×C6 12 6 20, 2 52 C2×C12 24 12 51, 7
22 C10 10 10 7 53 C52 52 52 2
23 C22 22 22 5 54 C18 18 18 5
24 C2×C2×C2 8 2 5, 7, 13 55 C2×C20 40 20 21, 2
25 C20 20 20 2 56 C2×C2×C6 24 6 13, 29, 3
26 C12 12 12 7 57 C2×C18 36 18 20, 2
27 C18 18 18 2 58 C28 28 28 3
28 C2×C6 12 6 13, 3 59 C58 58 58 2
29 C28 28 28 2 60 C2×C2×C4 16 4 11, 19, 7
30 C2×C4 8 4 11, 7 61 C60 60 60 2
31 C30 30 30 3 62 C30 30 30 3
32 C2×C8 16 8 31, 3 63 C6×C6 36 6 2, 5

Применение

На сложности дискретного логарифмирования в мультипликативной группе кольца вычетов основана криптографическая стойкость шифрсистемы Эль-Гамаля.

История

Вклад в исследование структуры мультипликативной группы кольца вычетов внесли Артин, Билхарц, Брауэр, Варинг, Вильсон, Гаусс, Лагранж, Лемер, Ферма, Хули, Эйлер. Лагранж доказал лемму о том, что если f(x) \in k[x], и k – поле, то f имеет не более n различных корней, где n – степень f. Он же доказал важное следствие этой леммы, заключающееся в сравнении x^{p-1}-1 ≡ (x-1)(x-2)...(x-p+1)mod(p). Эйлер доказал малую теорему Ферма. Варинг сформулировал теорему Вильсона, а Лагранж ее доказал. Эйлер предположил существование примитивных корней по модулю простого числа. Гаусс это доказал. Артин выдвинул свою гипотезу о существовании и количественной оценке простых чисел, по модулю которых заданное целое число является первообразным корнем. Брауэр внес вклад в исследование проблемы существования наборов последовательных целых чисел, каждое из которых — k-ая степень по модулю p. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезу Артина с предположением справедливости расширенной гипотезы Римана в полях алгебраических чисел.[1]

Примечания

Литература

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

Ссылки

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



Wikimedia Foundation. 2010.

Поможем написать курсовую

Полезное


Смотреть что такое "Мультипликативная группа кольца вычетов" в других словарях:

  • Функция Эйлера — Не следует путать с функцией распределения простых чисел. Первая тысяча значений Функция Эйлера φ(n) мультипликативная …   Википедия

  • Сравнение по модулю натурального числа — В теории чисел сравнение[уточнить] по модулю натурального числа n задаваемое означенным числом отношение эквивалентности на множестве целых чисел, связанное с делимостью на него. Факторпространство по этому отношению называется «кольцом… …   Википедия

  • Теорема Вильсона — теорема теории чисел, которая утверждает, что Натуральное число является простым тогда и только тогда, когда делится на p. Практическое использование теоремы Вильсона для определения простоты числа нецелесообразно из за сложности вычисления… …   Википедия

  • Первообразный корень (теория чисел) — У этого термина существуют и другие значения, см. Первообразный корень. Первообразный корень по модулю m ― целое число g такое, что и при где ― функция Эйлера. Другими словами, первообразный корень  это образующий элемент мультипликативной …   Википедия

  • КРУГОВОЕ ПОЛЕ — поле деления круг а, поле получающееся присоединением к полю рациональных чисел первообразного корня из единицы степени га, где п некоторое натуральное число. Иногда (локальным) круговым полем наз. также поле вида где поле рациональных р… …   Математическая энциклопедия

  • НОРМИРОВАНИЕ — логарифмическое нормирование, оценка поля, отображение поля Кв где Г линейно упорядоченная абелева группа, а присоединяемый элемент считается больше любого элемента из группы и для любого . При этом Н. должно удовлетворять следующим условиям:… …   Математическая энциклопедия

  • Таблица обозначений абстрактной алгебры — В абстрактной алгебре повсеместно используются символы для упрощения и сокращения текста, а также стандартные обозначения для некоторых групп. Ниже приведён список наиболее часто встречающихся алгебраических обозначений, соответствующие команды в …   Википедия

  • Конечное поле — или поле Галуа поле, состоящее из конечного числа элементов. Конечное поле обычно обозначается или , где число элементов поля. Простейшим примером конечного поля является кольцо вычетов по модулю простого числа p. Содержание …   Википедия

  • Поле Галуа — Конечное поле или поле Галуа поле, состоящее из конечного числа элементов. Конечное поле обычно обозначается или GF(q), где q число элементов поля. Простейшим примером конечного поля является кольцо вычетов по модулю простого числа. Содержание …   Википедия

  • Поля Галуа — Конечное поле или поле Галуа поле, состоящее из конечного числа элементов. Конечное поле обычно обозначается или GF(q), где q число элементов поля. Простейшим примером конечного поля является кольцо вычетов по модулю простого числа. Содержание …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»