Русская Википедия:Мультипликативная группа кольца вычетов

Мультипликативная группа кольца вычетов по модулю 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 }.

Свойства

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

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

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

Формы записи

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

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

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

Теорема: <math>U(\mathbb{Z}/p\mathbb{Z})</math> — циклическая группа. Шаблон:Sfn

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

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

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

<math>2^1 \equiv 2\ \pmod 9</math>

<math>2^2 \equiv 4\ \pmod 9</math>

<math>2^3 \equiv 8\ \pmod 9</math>

<math>2^4 \equiv 7\ \pmod 9</math>

<math>2^5 \equiv 5\ \pmod 9</math>

<math>2^6 \equiv 1\ \pmod 9</math>

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

Общий случай

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

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

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

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

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

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

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

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

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

<math>a^t\equiv 1\pmod m</math>

или

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

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

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

Свойства

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

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

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

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

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

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

Пример

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

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

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

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

Применение

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

История

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

Примечания

Шаблон:Примечания

Литература

Ссылки

↑ ^1,0 ^1,1 И. М. Виноградов Основы теории чисел. изд. 9-е, перераб., М. : Наука. 1981
↑ Сагалович Ю. Л. Введение в алгебраические коды. 2011.
↑ ^3,0 ^3,1 ^3,2 ^3,3 В. Босс Лекции по математике. Том 14. Теория чисел. 2014.
↑ Шаблон:Статья

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

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

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

[4] Шаблон:Статья

[1]

[2]

[3]

[4]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.