WikiSort.ru - Не сортированное

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

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

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

Формы записи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общий случай

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

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

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

Структуру группы определяет следующая теорема: Если p — нечётное простое число и l — целое положительное, то существуют примитивные корни по модулю ${\displaystyle p^{l}}$ , то есть ${\displaystyle U(\mathbb {Z} /p^{l}\mathbb {Z} )}$  — циклическая группа.

Из китайской теоремы об остатках следует, что при ${\displaystyle n=p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{l}^{a_{l}}}$ имеет место изоморфизм ${\displaystyle U(\mathbb {Z} /n\mathbb {Z} )}$ ≈ ${\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} )}$ .

Группа ${\displaystyle U(\mathbb {Z} /p_{i}^{a_{i}}\mathbb {Z} )}$  — циклическая. Её порядок равен ${\displaystyle p_{i}^{a_{i}-1}(p_{i}-1)}$ .

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

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

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

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

• ${\displaystyle a^{t}\equiv 1{\pmod {m}}}$

или

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

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

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

Свойства

Пример

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

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

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

Структура группы (Z/nZ)^×

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

История

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

Примечания

Литература

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

Ссылки

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