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

Приведённая система вычетов по модулю m — множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(·) — функция Эйлера.

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

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

Аксиоматика группы

Легко показать, что группа классов взаимнопростых с n вычетов по умножению удовлетворяет аксиоматике абелевой группы. Т.к. сравнение a ≡ b (mod n) предполагает равенство НОД(a,n)=НОД(b,n), то понятие эквивалентных классов вычетов по модулю n, взаимно простых с n, четко определено. Т.к. равенства НОД(a,n)=1 и НОД(b,n)=1 предполагают равенство НОД(ab,n)=1, то множество классов вычетов по модулю n, взаимно простых с n, замкнуто относительно умножения. При a, удовлетворяющем равенству НОД(a,n)=1, нахождение x, удовлетворяющего сравнению ax ≡ 1 (mod n), равносильно решению уравнения ax + ny = 1, которое может быть решено путем соотношения Безу. Найденное x будет обладать свойством НОД(x,n)=1.

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

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

Теорема: $\mathbb{Z}_p^{\times}$ — циклическая группа. ^[1]

Общий случай

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

Теорема: Если p – нечетное простое число и l – целое положительное, то существуют примитивные корни по модулю $p^{l}$ т.е. $U(\mathbb{Z}/p^{l}\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 ... 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}^{+}$. ^[1]

Формы записи

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

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

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

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

Свойства

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

Экспонента группы равна функции Кармайкла (англ.): для нечетных m она равна $\textstyle \operatorname{lcm}(p_1^{a_1-1}(p_1-1),\cdots, p_s^{a_s-1}(p_s-1))$, а для чётных — в 2 раза меньше.

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

Порядок группы равен функции Эйлера: $|U(\mathbb{Z}/p^{l}\mathbb{Z})|=\varphi(n).$

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

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

Структура группы $U(\mathbb{Z}/n\mathbb{Z})$

$n\;$	$U(\mathbb{Z}/n\mathbb{Z})$	$\varphi(n)$	$\lambda(n)\;$	генератор		$n\;$	$U(\mathbb{Z}/n\mathbb{Z})$	$\varphi(n)$	$\lambda(n)\;$	генератор
2	C1	1	1	1		33	C2×C10	20	10	10, 2
3	C2	2	2	2		34	C16	16	16	3
4	C2	2	2	3		35	C2×C12	24	12	6, 2
5	C4	4	4	2		36	C2×C6	12	6	19, 5
6	C2	2	2	5		37	C36	36	36	2
7	C6	6	6	3		38	C18	18	18	3
8	C2×C2	4	2	7, 3		39	C2×C12	24	12	38, 2
9	C6	6	6	2		40	C2×C2×C4	16	4	39, 11, 3
10	C4	4	4	3		41	C40	40	40	6
11	C10	10	10	2		42	C2×C6	12	6	13, 5
12	C2×C2	4	2	5, 7		43	C42	42	42	3
13	C12	12	12	2		44	C2×C10	20	10	43, 3
14	C6	6	6	3		45	C2×C12	24	12	44, 2
15	C2×C4	8	4	14, 2		46	C22	22	22	5
16	C2×C4	8	4	15, 3		47	C46	46	46	5
17	C16	16	16	3		48	C2×C2×C4	16	4	47, 7, 5
18	C6	6	6	5		49	C42	42	42	3
19	C18	18	18	2		50	C20	20	20	3
20	C2×C4	8	4	19, 3		51	C2×C16	32	16	50, 5
21	C2×C6	12	6	20, 2		52	C2×C12	24	12	51, 7
22	C10	10	10	7		53	C52	52	52	2
23	C22	22	22	5		54	C18	18	18	5
24	C2×C2×C2	8	2	5, 7, 13		55	C2×C20	40	20	21, 2
25	C20	20	20	2		56	C2×C2×C6	24	6	13, 29, 3
26	C12	12	12	7		57	C2×C18	36	18	20, 2
27	C18	18	18	2		58	C28	28	28	3
28	C2×C6	12	6	13, 3		59	C58	58	58	2
29	C28	28	28	2		60	C2×C2×C4	16	4	11, 19, 7
30	C2×C4	8	4	11, 7		61	C60	60	60	2
31	C30	30	30	3		62	C30	30	30	3
32	C2×C8	16	8	31, 3		63	C6×C6	36	6	2, 5

Применение

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

История

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

Примечания

1. ↑ ^{1 2 3} Айерлэнд. Роузен. Классическое введение в современную теорию чисел.

Литература

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

Ссылки

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