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

Мультипликативная группа кольца вычетов по модулю 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 сравнение [math]\displaystyle{ ax \equiv b \pmod{m} }[/math] разрешимо относительно x^[4].

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

Если m простое, то, как отмечалось выше, элементы 1, 2, …,m-1 входят в [math]\displaystyle{ \mathbb{Z}_m^{\times} }[/math]. В этом случае [math]\displaystyle{ \mathbb{Z}_m^{\times} }[/math] является полем^[4].

Формы записи

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

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

Чтобы понять структуру группы [math]\displaystyle{ U(\mathbb{Z}/n\mathbb{Z}) }[/math], можно рассмотреть частный случай [math]\displaystyle{ n=p^a }[/math], где [math]\displaystyle{ p }[/math] — простое число, и обобщить его. Рассмотрим простейший случай, когда [math]\displaystyle{ a=1 }[/math], то есть [math]\displaystyle{ n=p }[/math].

Теорема: [math]\displaystyle{ U(\mathbb{Z}/p\mathbb{Z}) }[/math] — циклическая группа. ^[5]

Пример: Рассмотрим группу [math]\displaystyle{ U(\mathbb{Z}/9\mathbb{Z}) }[/math]

[math]\displaystyle{ U(\mathbb{Z}/9\mathbb{Z}) }[/math] = {1,2,4,5,7,8}

Генератором группы является число 2.

[math]\displaystyle{ 2^1 \equiv 2\ \pmod 9 }[/math]

[math]\displaystyle{ 2^2 \equiv 4\ \pmod 9 }[/math]

[math]\displaystyle{ 2^3 \equiv 8\ \pmod 9 }[/math]

[math]\displaystyle{ 2^4 \equiv 7\ \pmod 9 }[/math]

[math]\displaystyle{ 2^5 \equiv 5\ \pmod 9 }[/math]

[math]\displaystyle{ 2^6 \equiv 1\ \pmod 9 }[/math]

Как видим, любой элемент группы [math]\displaystyle{ U(\mathbb{Z}/9\mathbb{Z}) }[/math] может быть представлен в виде [math]\displaystyle{ 2^l }[/math], где [math]\displaystyle{ 1\le\ell \lt \varphi(m) }[/math]. То есть группа [math]\displaystyle{ U(\mathbb{Z}/9\mathbb{Z}) }[/math] — циклическая.

Общий случай

В общем случае необходимо определение первообразного корня. Первообразный корень по простому модулю [math]\displaystyle{ p }[/math] — это число, которое вместе со своим классом вычетов порождает группу [math]\displaystyle{ \mathbb{Z}/p\mathbb{Z} }[/math].^[5]

Примеры: 2 — первообразный корень по модулю 11; 8 — первообразный корень по модулю 11; 3 не является первообразным корнем по модулю 11.

В случае целого модуля [math]\displaystyle{ n }[/math] определение такое же.

Структуру группы определяет следующая теорема: Если p — нечётное простое число и k — целое положительное, то существуют первообразные корни по модулю [math]\displaystyle{ p^{k} }[/math], то есть [math]\displaystyle{ \mathbb{Z}/p^{k}\mathbb{Z} }[/math] — циклическая группа.

Из китайской теоремы об остатках следует, что при [math]\displaystyle{ n=p_1^{a_1}p_2^{a_2}...p_l^{a_l} }[/math] имеет место изоморфизм [math]\displaystyle{ U(\mathbb{Z}/n\mathbb{Z}) }[/math] ≈ [math]\displaystyle{ U(\mathbb{Z}/p_1^{a_1}\mathbb{Z})\times U(\mathbb{Z}/p_2^{a_2}\mathbb{Z})\times \dots U(\mathbb{Z}/p_l^{a_l}\mathbb{Z}) }[/math].

Группа [math]\displaystyle{ U(\mathbb{Z}/p_i^{a_i}\mathbb{Z}) }[/math] — циклическая. Её порядок равен [math]\displaystyle{ p_i^{a_i-1}(p_i-1) }[/math].

Группа [math]\displaystyle{ U(\mathbb{Z}/2^{a}\mathbb{Z}) }[/math] — также циклическая порядка a при a=1 или a=2. При [math]\displaystyle{ a \geqslant 3 }[/math] эта группа циклической не является и представляет собой прямое произведение двух циклических групп, порядков [math]\displaystyle{ 2 }[/math] и [math]\displaystyle{ 2^{a-2} }[/math].

Группа [math]\displaystyle{ U(\mathbb{Z}/n\mathbb{Z}) }[/math] циклична тогда и только тогда, когда [math]\displaystyle{ n=p^a }[/math] или [math]\displaystyle{ n=2p^a }[/math] или n = 2 или n = 4, где p — нечётное простое число. В общем случае [math]\displaystyle{ U(\mathbb{Z}/n\mathbb{Z}) }[/math] как абелева группа представляется прямым произведением циклических примарных групп, изоморфных [math]\displaystyle{ \mathbb{Z}_{u_i}^{+} }[/math].^[5]

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

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

[math]\displaystyle{ a^t\equiv 1\pmod m }[/math]

или

существует целое число [math]\displaystyle{ k }[/math], [math]\displaystyle{ 0\leq k\lt s }[/math], такое, что [math]\displaystyle{ a^{2^kt}\equiv m-1\pmod m. }[/math]

Если число [math]\displaystyle{ m }[/math] — составное, существует подгруппа мультипликативной группы кольца вычетов, называемая подгруппой свидетелей простоты. Её элементы, возведённые в степень [math]\displaystyle{ m-1 }[/math], совпадают с [math]\displaystyle{ 1 }[/math] по модулю [math]\displaystyle{ m }[/math].

Пример: [math]\displaystyle{ m=9 }[/math]. Есть [math]\displaystyle{ 6 }[/math] остатков, взаимно простых с [math]\displaystyle{ 9 }[/math], это [math]\displaystyle{ 1,2,4,5,7 }[/math] и [math]\displaystyle{ 8 }[/math]. [math]\displaystyle{ 8 }[/math] эквивалентно [math]\displaystyle{ -1 }[/math] по модулю [math]\displaystyle{ 9 }[/math], значит [math]\displaystyle{ 8^{8} }[/math] эквивалентно [math]\displaystyle{ 1 }[/math] по модулю [math]\displaystyle{ 9 }[/math]. Значит, [math]\displaystyle{ 1 }[/math] и [math]\displaystyle{ 8 }[/math] — свидетели простоты числа [math]\displaystyle{ 9 }[/math]. В данном случае {1, 8} — подгруппа свидетелей простоты.^[6]

Свойства

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

Экспонента группы равна функции Кармайкла [math]\displaystyle{ \lambda(n)= }[/math][math]\displaystyle{ \textstyle \operatorname{lcm} }[/math][math]\displaystyle{ (p_1^{a_1-1}(p_1-1),\cdots, p_s^{a_s-1}(p_s-1)) }[/math].

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

Порядок группы равен функции Эйлера: [math]\displaystyle{ |U(\mathbb{Z}/m\mathbb{Z})|=\varphi(m) }[/math]. Отсюда и из изоморфизма [math]\displaystyle{ U(\mathbb{Z}/m\mathbb{Z}) }[/math] ≈ [math]\displaystyle{ 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}) }[/math] можно получить ещё один способ доказательства равенства [math]\displaystyle{ \varphi(m) = \varphi(m_1)\varphi(m_2)...\varphi(m_t) }[/math] при [math]\displaystyle{ m = m_1m_2...m_t }[/math] ^[5]

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

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

Пример

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

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

Запись [math]\displaystyle{ C_n }[/math] означает «циклическая группа порядка n».

Структура группы **(Z/nZ)^×**
[math]\displaystyle{ n\; }[/math]	[math]\displaystyle{ (\mathbb{Z}/n\mathbb{Z})^\times }[/math]	[math]\displaystyle{ \varphi(n) }[/math]	[math]\displaystyle{ \lambda(n)\; }[/math]	Генератор группы	[math]\displaystyle{ n\; }[/math]	[math]\displaystyle{ (\mathbb{Z}/n\mathbb{Z})^\times }[/math]	[math]\displaystyle{ \varphi(n) }[/math]	[math]\displaystyle{ \lambda(n)\; }[/math]	Генератор группы	[math]\displaystyle{ n\; }[/math]	[math]\displaystyle{ (\mathbb{Z}/n\mathbb{Z})^\times }[/math]	[math]\displaystyle{ \varphi(n) }[/math]	[math]\displaystyle{ \lambda(n)\; }[/math]	Генератор группы	[math]\displaystyle{ n\; }[/math]	[math]\displaystyle{ (\mathbb{Z}/n\mathbb{Z})^\times }[/math]	[math]\displaystyle{ \varphi(n) }[/math]	[math]\displaystyle{ \lambda(n)\; }[/math]	Генератор группы
1	C₁	1	1	0	33	C₂×C₁₀	20	10	2, 10	65	C₄×C₁₂	48	12	2, 12	97	C₉₆	96	96	5
2	C₁	1	1	1	34	C₁₆	16	16	3	66	C₂×C₁₀	20	10	5, 7	98	C₄₂	42	42	3
3	C₂	2	2	2	35	C₂×C₁₂	24	12	2, 6	67	C₆₆	66	66	2	99	C₂×C₃₀	60	30	2, 5
4	C₂	2	2	3	36	C₂×C₆	12	6	5, 19	68	C₂×C₁₆	32	16	3, 67	100	C₂×C₂₀	40	20	3, 99
5	C₄	4	4	2	37	C₃₆	36	36	2	69	C₂×C₂₂	44	22	2, 68	101	C₁₀₀	100	100	2
6	C₂	2	2	5	38	C₁₈	18	18	3	70	C₂×C₁₂	24	12	3, 69	102	C₂×C₁₆	32	16	5, 101
7	C₆	6	6	3	39	C₂×C₁₂	24	12	2, 38	71	C₇₀	70	70	7	103	C₁₀₂	102	102	5
8	C₂×C₂	4	2	3, 5	40	C₂×C₂×C₄	16	4	3, 11, 39	72	C₂×C₂×C₆	24	6	5, 17, 19	104	C₂×C₂×C₁₂	48	12	3, 5, 103
9	C₆	6	6	2	41	C₄₀	40	40	6	73	C₇₂	72	72	5	105	C₂×C₂×C₁₂	48	12	2, 29, 41
10	C₄	4	4	3	42	C₂×C₆	12	6	5, 13	74	C₃₆	36	36	5	106	C₅₂	52	52	3
11	C₁₀	10	10	2	43	C₄₂	42	42	3	75	C₂×C₂₀	40	20	2, 74	107	C₁₀₆	106	106	2
12	C₂×C₂	4	2	5, 7	44	C₂×C₁₀	20	10	3, 43	76	C₂×C₁₈	36	18	3, 37	108	C₂×C₁₈	36	18	5, 107
13	C₁₂	12	12	2	45	C₂×C₁₂	24	12	2, 44	77	C₂×C₃₀	60	30	2, 76	109	C₁₀₈	108	108	6
14	C₆	6	6	3	46	C₂₂	22	22	5	78	C₂×C₁₂	24	12	5, 7	110	C₂×C₂₀	40	20	3, 109
15	C₂×C₄	8	4	2, 14	47	C₄₆	46	46	5	79	C₇₈	78	78	3	111	C₂×C₃₆	72	36	2, 110
16	C₂×C₄	8	4	3, 15	48	C₂×C₂×C₄	16	4	5, 7, 47	80	C₂×C₄×C₄	32	4	3, 7, 79	112	C₂×C₂×C₁₂	48	12	3, 5, 111
17	C₁₆	16	16	3	49	C₄₂	42	42	3	81	C₅₄	54	54	2	113	C₁₁₂	112	112	3
18	C₆	6	6	5	50	C₂₀	20	20	3	82	C₄₀	40	40	7	114	C₂×C₁₈	36	18	5, 37
19	C₁₈	18	18	2	51	C₂×C₁₆	32	16	5, 50	83	C₈₂	82	82	2	115	C₂×C₄₄	88	44	2, 114
20	C₂×C₄	8	4	3, 19	52	C₂×C₁₂	24	12	7, 51	84	C₂×C₂×C₆	24	6	5, 11, 13	116	C₂×C₂₈	56	28	3, 115
21	C₂×C₆	12	6	2, 20	53	C₅₂	52	52	2	85	C₄×C₁₆	64	16	2, 3	117	C₆×C₁₂	72	12	2, 17
22	C₁₀	10	10	7	54	C₁₈	18	18	5	86	C₄₂	42	42	3	118	C₅₈	58	58	11
23	C₂₂	22	22	5	55	C₂×C₂₀	40	20	2, 21	87	C₂×C₂₈	56	28	2, 86	119	C₂×C₄₈	96	48	3, 118
24	C₂×C₂×C₂	8	2	5, 7, 13	56	C₂×C₂×C₆	24	6	3, 13, 29	88	C₂×C₂×C₁₀	40	10	3, 5, 7	120	C₂×C₂×C₂×C₄	32	4	7, 11, 19, 29
25	C₂₀	20	20	2	57	C₂×C₁₈	36	18	2, 20	89	C₈₈	88	88	3	121	C₁₁₀	110	110	2
26	C₁₂	12	12	7	58	C₂₈	28	28	3	90	C₂×C₁₂	24	12	7, 11	122	C₆₀	60	60	7
27	C₁₈	18	18	2	59	C₅₈	58	58	2	91	C₆×C₁₂	72	12	2, 3	123	C₂×C₄₀	80	40	7, 83
28	C₂×C₆	12	6	3, 13	60	C₂×C₂×C₄	16	4	7, 11, 19	92	C₂×C₂₂	44	22	3, 91	124	C₂×C₃₀	60	30	3, 61
29	C₂₈	28	28	2	61	C₆₀	60	60	2	93	C₂×C₃₀	60	30	11, 61	125	C₁₀₀	100	100	2
30	C₂×C₄	8	4	7, 11	62	C₃₀	30	30	3	94	C₄₆	46	46	5	126	C₆×C₆	36	6	5, 13
31	C₃₀	30	30	3	63	C₆×C₆	36	6	2, 5	95	C₂×C₃₆	72	36	2, 94	127	C₁₂₆	126	126	3
32	C₂×C₈	16	8	3, 31	64	C₂×C₁₆	32	16	3, 63	96	C₂×C₂×C₈	32	8	5, 17, 31	128	C₂×C₃₂	64	32	3, 127

Применение

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

История

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

Примечания

↑ ^1,0 ^1,1 И. М. Виноградов Основы теории чисел. изд. 9-е, перераб., М. : Наука. 1981
↑ Сагалович Ю. Л. Введение в алгебраические коды. 2011.
↑ Бухштаб, 1966.
↑ ^4,0 ^4,1 ^4,2 ^4,3 В. Босс Лекции по математике. Том 14. Теория чисел. 2014.
↑ ^5,0 ^5,1 ^5,2 ^5,3 ^5,4 Айерлэнд, Роузен, 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.

[Виноградов-1] 1,0 ^1,1 И. М. Виноградов Основы теории чисел. изд. 9-е, перераб., М. : Наука. 1981

[2] Сагалович Ю. Л. Введение в алгебраические коды. 2011.

[_8f405c19096568b3-3] Бухштаб, 1966.

[Босс-4] 4,0 ^4,1 ^4,2 ^4,3 В. Босс Лекции по математике. Том 14. Теория чисел. 2014.

[_fee111f27d4c2846-5] 5,0 ^5,1 ^5,2 ^5,3 ^5,4 Айерлэнд, Роузен, 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.

[_9a013555f84ece4c-7] Алферов и др., 2002.

[1]

[2]

[3]

[4]

[5]

[6]

[7]