Меню Главная Случайная статья Настройки Мультипликативная группа кольца вычетов Материал из https://ru.wikipedia.org Мультипликативная группа кольца вычетов по модулю m — мультипликативная группа обратимых элементов кольца вычетов по модулю m. При этом в качестве множества элементов может рассматриваться любая приведенная система вычетов по модулю m. Содержание 1 Приведённая система вычетов 2 Формы записи 3 Простейший случай 4 Общий случай 5 Подгруппа свидетелей простоты 6 Свойства 6.1 Экспонента группы 6.2 Порядок группы 6.3 Порождающее множество 7 Пример 8 Структура группы 9 Применение 10 История 11 Примечания 12 Литература 13 Ссылки Приведённая система вычетов Приведённая система вычетов по модулю m — множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. В качестве приведённой системы вычетов по модулю m обычно берутся взаимно простые с m числа от 1 до m — 1[1]. Пример: приведенной системой вычетов по модулю 42 будет: { 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41 }. Свойства Набор любых ${\displaystyle \varphi (m)}$ (функция Эйлера) попарно несравнимых по модулю m и взаимно простых с m чисел образует приведённую систему вычетов по модулю ${\displaystyle 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}}$ является полем[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 \leq \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 — нечётное простое число и ${\displaystyle \ell }$ — целое положительное, то существуют примитивные корни по модулю ${\displaystyle p^{\ell }}$, то есть ${\displaystyle U(\mathbb {Z} /p^{\ell }\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 \lambda (n)=}$${\displaystyle \textstyle \operatorname {lcm} }$${\displaystyle (p_{1}^{a_{1}-1}(p_{1}-1),\cdots ,p_{s}^{a_{s}-1}(p_{s}-1))}$. Порядок группы Порядок группы равен функции Эйлера: ${\displaystyle |U(\mathbb {Z} /m\mathbb {Z} )|=\varphi (m)}$. Отсюда и из изоморфизма ${\displaystyle U(\mathbb {Z} /m\mathbb {Z} )}$ ${\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} )}$ можно получить ещё один способ доказательства равенства ${\displaystyle \varphi (m)=\varphi (m_{1})\varphi (m_{2})...\varphi (m_{t})}$ при ${\displaystyle m=m_{1}m_{2}...m_{t}}$ [5] Порождающее множество ${\displaystyle U(\mathbb {Z} /n\mathbb {Z} )}$ — циклическая группа тогда и только тогда, когда ${\displaystyle \varphi (n)=\lambda (n).}$ В случае циклической группы генератор называется первообразным корнем. Пример Приведённая система вычетов по модулю ${\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 C2C10 20 10 2, 10 65 C4C12 48 12 2, 12 97 C96 96 96 5 2 C1 1 1 1 34 C16 16 16 3 66 C2C10 20 10 5, 7 98 C42 42 42 3 3 C2 2 2 2 35 C2C12 24 12 2, 6 67 C66 66 66 2 99 C2C30 60 30 2, 5 4 C2 2 2 3 36 C2C6 12 6 5, 19 68 C2C16 32 16 3, 67 100 C2C20 40 20 3, 99 5 C4 4 4 2 37 C36 36 36 2 69 C2C22 44 22 2, 68 101 C100 100 100 2 6 C2 2 2 5 38 C18 18 18 3 70 C2C12 24 12 3, 69 102 C2C16 32 16 5, 101 7 C6 6 6 3 39 C2C12 24 12 2, 38 71 C70 70 70 7 103 C102 102 102 5 8 C2C2 4 2 3, 5 40 C2C2C4 16 4 3, 11, 39 72 C2C2C6 24 6 5, 17, 19 104 C2C2C12 48 12 3, 5, 103 9 C6 6 6 2 41 C40 40 40 6 73 C72 72 72 5 105 C2C2C12 48 12 2, 29, 41 10 C4 4 4 3 42 C2C6 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 C2C20 40 20 2, 74 107 C106 106 106 2 12 C2C2 4 2 5, 7 44 C2C10 20 10 3, 43 76 C2C18 36 18 3, 37 108 C2C18 36 18 5, 107 13 C12 12 12 2 45 C2C12 24 12 2, 44 77 C2C30 60 30 2, 76 109 C108 108 108 6 14 C6 6 6 3 46 C22 22 22 5 78 C2C12 24 12 5, 7 110 C2C20 40 20 3, 109 15 C2C4 8 4 2, 14 47 C46 46 46 5 79 C78 78 78 3 111 C2C36 72 36 2, 110 16 C2C4 8 4 3, 15 48 C2C2C4 16 4 5, 7, 47 80 C2C4C4 32 4 3, 7, 79 112 C2C2C12 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 C2C18 36 18 5, 37 19 C18 18 18 2 51 C2C16 32 16 5, 50 83 C82 82 82 2 115 C2C44 88 44 2, 114 20 C2C4 8 4 3, 19 52 C2C12 24 12 7, 51 84 C2C2C6 24 6 5, 11, 13 116 C2C28 56 28 3, 115 21 C2C6 12 6 2, 20 53 C52 52 52 2 85 C4C16 64 16 2, 3 117 C6C12 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 C2C20 40 20 2, 21 87 C2C28 56 28 2, 86 119 C2C48 96 48 3, 118 24 C2C2C2 8 2 5, 7, 13 56 C2C2C6 24 6 3, 13, 29 88 C2C2C10 40 10 3, 5, 7 120 C2C2C2C4 32 4 7, 11, 19, 29 25 C20 20 20 2 57 C2C18 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 C2C12 24 12 7, 11 122 C60 60 60 7 27 C18 18 18 2 59 C58 58 58 2 91 C6C12 72 12 2, 3 123 C2C40 80 40 7, 83 28 C2C6 12 6 3, 13 60 C2C2C4 16 4 7, 11, 19 92 C2C22 44 22 3, 91 124 C2C30 60 30 3, 61 29 C28 28 28 2 61 C60 60 60 2 93 C2C30 60 30 11, 61 125 C100 100 100 2 30 C2C4 8 4 7, 11 62 C30 30 30 3 94 C46 46 46 5 126 C6C6 36 6 5, 13 31 C30 30 30 3 63 C6C6 36 6 2, 5 95 C2C36 72 36 2, 94 127 C126 126 126 3 32 C2C8 16 8 3, 31 64 C2C16 32 16 3, 63 96 C2C2C8 32 8 5, 17, 31 128 C2C32 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] Примечания 1 2 И. М. Виноградов Основы теории чисел. изд. 9-е, перераб., М. : Наука. 1981 Сагалович Ю. Л. Введение в алгебраические коды. 2011. Бухштаб, 1966. 1 2 3 4 В. Босс Лекции по математике. Том 14. Теория чисел. 2014. 1 2 3 4 5 Айерлэнд, Роузен, 1987. Erds, Paul; Pomerance, Carl. On the number of false witnesses for a composite number (англ.) // Math. Comput.[англ.] : journal. — 1986. — Vol. 46. — P. 259—279. — . Алферов и др., 2002. Литература Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — М.: Мир, 1987. Ссылки Weisstein, Eric W. Modulo Multiplication Group (англ.) на сайте Wolfram MathWorld.