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

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

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

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

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

Свойства

• Набор любых $\mathrm{\phi <!--\; \phi \; -->}(m)$$\varphi(m)$  (функция Эйлера) попарно несравнимых по модулю 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 <!--\; \equiv \; -->b(\mathrm{mod}m)$$ax\equiv b{\pmod {m}}$  разрешимо относительно x.

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

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

Формы записиПравить

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

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

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

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

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

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

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

$2^1\equiv <!--\; \equiv \; -->2(\mathrm{mod}9)$$2^{1}\equiv 2\ {\pmod {9}}$ 

$2^2\equiv <!--\; \equiv \; -->4(\mathrm{mod}9)$$2^{2}\equiv 4\ {\pmod {9}}$ 

$2^3\equiv <!--\; \equiv \; -->8(\mathrm{mod}9)$$2^{3}\equiv 8\ {\pmod {9}}$ 

$2^4\equiv <!--\; \equiv \; -->7(\mathrm{mod}9)$$2^{4}\equiv 7\ {\pmod {9}}$ 

$2^5\equiv <!--\; \equiv \; -->5(\mathrm{mod}9)$$2^{5}\equiv 5\ {\pmod {9}}$ 

$2^6\equiv <!--\; \equiv \; -->1(\mathrm{mod}9)$$2^{6}\equiv 1\ {\pmod {9}}$ 

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

Общий случайПравить

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

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

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

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

Из китайской теоремы об остатках следует, что при $n=p_1^{a_1}{p}_2^{a_2}...p_l^{a_l}$$n=p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{l}^{a_{l}}$  имеет место изоморфизм $U(\mathbb{Z}/n\mathbb{Z})$$U({\mathbb {Z}}/n{\mathbb {Z}})$  ≈ $U(\mathbb{Z}/p_1^{a_1}\mathbb{Z})\times <!--\; \times \; -->U(\mathbb{Z}/p_2^{a_2}\mathbb{Z})\times <!--\; \times \; -->\dots <!--\; \dots \; -->U(\mathbb{Z}/p_l^{a_l}\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})$$U({\mathbb {Z}}/p_{i}^{{a_{i}}}{\mathbb {Z}})$  — циклическая. Её порядок равен $p_i^{a_i-<!--\; -\; -->1}(p_i-<!--\; -\; -->1)$$p_{i}^{{a_{i}-1}}(p_{i}-1)$ .

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

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

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

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

• $a^t\equiv <!--\; \equiv \; -->1(\mathrm{mod}m)$$a^{t}\equiv 1{\pmod {m}}$ 

или

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

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

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

СвойстваПравить

Экспонента группыПравить

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

Порядок группыПравить

Порядок группы равен функции Эйлера: $|U(\mathbb{Z}/m\mathbb{Z})|=\mathrm{\phi <!--\; \phi \; -->}(m)$$|U(\mathbb {Z} /m\mathbb {Z} )|=\varphi (m)$ . Отсюда и из изоморфизма $U(\mathbb{Z}/m\mathbb{Z})$$U({\mathbb {Z}}/m{\mathbb {Z}})$  ≈ $U(\mathbb{Z}/p_1^{a_1}\mathbb{Z})\times <!--\; \times \; -->U(\mathbb{Z}/p_2^{a_2}\mathbb{Z})\times <!--\; \times \; -->...U(\mathbb{Z}/p_l^{a_l}\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}})$  можно получить ещё один способ доказательства равенства $\mathrm{\phi <!--\; \phi \; -->}(m)=\mathrm{\phi <!--\; \phi \; -->}(m_1)\mathrm{\phi <!--\; \phi \; -->}(m_2)...\mathrm{\phi <!--\; \phi \; -->}(m_t)$$\varphi (m)=\varphi (m_{1})\varphi (m_{2})...\varphi (m_{t})$  при $m=m_1{m}_2...m_t$$m=m_{1}m_{2}...m_{t}$ 

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

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

ПримерПравить

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

Структура группыПравить

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

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

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

ПрименениеПравить

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

ИсторияПравить

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

ЛитератураПравить

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

СсылкиПравить

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