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

Мультипликативная группа кольца вычетов по модулю m — мультипликативная группа обратимых элементов кольца вычетов по модулю m . При этом в качестве множества элементов может рассматриваться любая приведенная система вычетов по модулю m .

Приведённая система вычетов

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

Пример : приведенной системой вычетов по модулю 42 будет: { 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41 }.

Свойства

Набор любых $\varphi (m)$ ( функция Эйлера ) попарно несравнимых по модулю m и взаимно простых с m чисел образует приведённую систему вычетов по модулю $m$ .
Если НОД ( a , m ) = 1 , то множество значений ax , где x пробегает приведенную систему вычетов по модулю m , также является приведенной системой вычетов по модулю m .
Если НОД( k , m ) = 1, то множество значений kx + my , где x пробегает приведенную систему вычетов по модулю m и y пробегает приведенную систему вычетов по модулю k , является приведенной системой вычетов по модулю km .
В случае, когда число m простое, приведенная система вычетов по модулю m отличается от полной системы вычетов отсутствием нуля .
Если a — элемент приведенной системы вычетов по модулю m , то, для любого b сравнение $ax\equiv b{\pmod {m}}$ разрешимо относительно x .

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

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

Формы записи

Кольцо вычетов по модулю 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})$ .

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

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

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

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

U(\mathbb {Z} /9\mathbb {Z} )

= {1,2,4,5,7,8}

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

2^{1}\equiv 2\ {\pmod {9}}

2^{2}\equiv 4\ {\pmod {9}}

2^{3}\equiv 8\ {\pmod {9}}

2^{4}\equiv 7\ {\pmod {9}}

2^{5}\equiv 5\ {\pmod {9}}

2^{6}\equiv 1\ {\pmod {9}}

Как видим, любой элемент группы

U(\mathbb {Z} /9\mathbb {Z} )

может быть представлен в виде

2^{l}

, где

1\leq \ell \leq \varphi (m)

. То есть группа

U(\mathbb {Z} /9\mathbb {Z} )

— циклическая.

Общий случай

Для рассмотрения общего случая необходимо определение примитивного корня . Примитивный корень по простому модулю $p$ — это число, которое вместе со своим классом вычетов порождает группу $U(\mathbb {Z} /p\mathbb {Z} )$ .

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

В случае целого модуля $n$ определение такое же.

Структуру группы определяет следующая теорема: Если p — нечётное простое число и $\ell$ — целое положительное, то существуют примитивные корни по модулю $p^{\ell }$ , то есть $U(\mathbb {Z} /p^{\ell }\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 \dots 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}}^{+}$ .

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

Пусть $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^{k}t}\equiv m-1{\pmod {m}}.$

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

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

Свойства

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

Экспонента группы равна функции Кармайкла $\lambda (n)=$ $\textstyle \operatorname {lcm}$ $(p_{1}^{a_{1}-1}(p_{1}-1),\cdots ,p_{s}^{a_{s}-1}(p_{s}-1))$ .

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

Порядок группы равен функции Эйлера: $|U(\mathbb {Z} /m\mathbb {Z} )|=\varphi (m)$ . Отсюда и из изоморфизма $U(\mathbb {Z} /m\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} )$ можно получить ещё один способ доказательства равенства $\varphi (m)=\varphi (m_{1})\varphi (m_{2})...\varphi (m_{t})$ при $m=m_{1}m_{2}...m_{t}$

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

$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».

Структура группы **(Z/ n Z) ^×**
$n\;$	$(\mathbb {Z} /n\mathbb {Z} )^{\times }$	$\varphi (n)$	$\lambda (n)\;$	Генератор группы	$n\;$	$(\mathbb {Z} /n\mathbb {Z} )^{\times }$	$\varphi (n)$	$\lambda (n)\;$	Генератор группы	$n\;$	$(\mathbb {Z} /n\mathbb {Z} )^{\times }$	$\varphi (n)$	$\lambda (n)\;$	Генератор группы	$n\;$	$(\mathbb {Z} /n\mathbb {Z} )^{\times }$	$\varphi (n)$	$\lambda (n)\;$	Генератор группы
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

Применение

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

История

Вклад в исследование структуры мультипликативной группы кольца вычетов внесли Артин , Билхарц, Брауэр , Вильсон, Гаусс , Лагранж , Лемер, Варинг , Ферма, Хули, Эйлер . Лагранж доказал лемму о том, что если $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. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезу Артина с предположением справедливости расширенной гипотезы Римана в полях алгебраических чисел.

Примечания

↑ И. М. Виноградов Основы теории чисел. изд. 9-е, перераб., М. : Наука. 1981
Сагалович Ю. Л. Введение в алгебраические коды. 2011.
.
↑ В. Босс Лекции по математике. Том 14. Теория чисел. 2014.
↑ .
Erdős, Paul ; Pomerance, Carl. On the number of false witnesses for a composite number (англ.) // : journal. — 1986. — Vol. 46 . — P. 259—279 .
.

Литература

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