До сих пор мы в основном изучали отдельные группы. Теперь научимся брать несколько групп и собирать из них одну новую, более крупную группу.
Такая конструкция называется external direct product (внешнее прямое произведение). Главная идея очень простая:
элемент новой группы состоит сразу из нескольких компонентов, а операция выполняется отдельно в каждом компоненте.
Определение
Пусть есть группы:
G1, G2, ..., Gn
Их external direct product обозначается:
G1 ⊕ G2 ⊕ ... ⊕ Gn
Элементы этой группы — кортежи:
(g1, g2, ..., gn)
где:
g1 ∈ G1
g2 ∈ G2
...
gn ∈ Gn
Формально:
G1 ⊕ G2 ⊕ ... ⊕ Gn
=
{(g1, g2, ..., gn) | gi ∈ Gi}
Получившаяся группа будет абелевой, если изначальные группы тоже были абелевыми. Если хотя бы одна “изначальная” группа была неабелевой, то и результат тоже неабелева группа.
Как работает операция
Операция выполняется componentwise / покомпонентно. То есть:
(g1, g2, ..., gn)(h1, h2, ..., hn)
=
(g1h1, g2h2, ..., gnhn)
Каждая пара компонентов объединяется по правилам своей группы.
Важно: в разных компонентах могут использоваться разные операции. Например, в первой компоненте может быть умножение modulo 8, а во второй — умножение modulo 10.
Простой пример с обычным сложением
Рассмотрим:
Z2 ⊕ Z3
Здесь:
Z2 = {0, 1}
и:
Z3 = {0, 1, 2}
Поэтому элементы direct product — все возможные пары:
Z2 ⊕ Z3 =
{
(0,0), (0,1), (0,2),
(1,0), (1,1), (1,2)
}
Всего элементов:
2 · 3 = 6
Как складываются элементы
Операция выполняется по координатам:
(a, b) + (c, d)
=
(a + c mod 2, b + d mod 3)
Например:
(1, 2) + (1, 2)
Первая координата считается modulo 2:
1 + 1 ≡ 0 (mod 2)
Вторая координата считается modulo 3:
2 + 2 ≡ 1 (mod 3)
Поэтому:
(1, 2) + (1, 2) = (0, 1)
Почему это группа
External direct product наследует свойства исходных групп.
Closure
Если:
g1, h1 ∈ G1
то:
g1h1 ∈ G1
То же самое верно для каждой компоненты.
Значит результат покомпонентной операции снова лежит в direct product.
Identity
Если identity elements исходных групп:
e1, e2, ..., en
то identity direct product:
(e1, e2, ..., en)
Потому что:
(g1, ..., gn)(e1, ..., en)
=
(g1, ..., gn)
Inverse
Inverse элемента:
(g1, g2, ..., gn)
равен:
(g1^-1, g2^-1, ..., gn^-1)
То есть inverse тоже вычисляется покомпонентно.
Associativity
Associativity выполняется в каждой исходной группе, поэтому она выполняется и для кортежей.
Размер direct product
Если все группы конечны, то:
|G1 ⊕ G2 ⊕ ... ⊕ Gn|
=
|G1||G2|...|Gn|
Почему? Потому что для первой компоненты есть |G1| вариантов, для второй — |G2| вариантов и так далее.
Пример
|Z2 ⊕ Z3| = |Z2| · |Z3| = 2 · 3 = 6
И действительно, мы получили шесть пар.
Пример с U(8) и U(10)
Рассмотрим:
U(8) = {1, 3, 5, 7}
и:
U(10) = {1, 3, 7, 9}
Обе группы используют multiplication modulo соответствующего числа.
Элемент direct product имеет вид:
(a, b)
где:
a ∈ U(8)
b ∈ U(10)
Например:
(3, 7)
и:
(7, 9)
Перемножим их:
(3, 7)(7, 9)
Первая координата считается modulo 8:
3 · 7 = 21 ≡ 5 (mod 8)
Вторая координата считается modulo 10:
7 · 9 = 63 ≡ 3 (mod 10)
Поэтому:
(3, 7)(7, 9) = (5, 3)
Почему произведение называется external
Слово external / внешнее означает, что мы начинаем с отдельных групп:
G1
G2
...
Gn
и строим из них новую группу кортежей. То есть новая группа изначально не обязана находиться внутри какой-то уже существующей группы.
Позже появится похожая конструкция internal direct product. Там, наоборот, большая группа уже существует, а мы разлагаем её на подгруппы.
Связь с обычными координатами
Знакомый пример:
R² = R ⊕ R
Элемент R² — это пара:
(x, y)
Сложение выполняется покомпонентно:
(x1, y1) + (x2, y2)
=
(x1 + x2, y1 + y2)
Аналогично:
R³ = R ⊕ R ⊕ R
То есть external direct product — это та же идея координат, только компоненты теперь могут быть любыми группами.
Пример: Z2 ⊕ Z3 изоморфна Z6
Рассмотрим элемент:
(1, 1) ∈ Z2 ⊕ Z3
Почему берём именно (1,1)? Элемент 1 является generator и в Z2, и в Z3. Поэтому порядки его компонентов равны 2 и 3. Так как:
gcd(2,3) = 1
порядок пары равен:
|(1,1)| = lcm(2,3) = 6
А вся группа Z2 ⊕ Z3 тоже имеет 6 элементов. Значит (1,1) может породить всю группу.
Будем складывать его с самим собой:
0(1,1) = (0,0)
1(1,1) = (1,1)
2(1,1) = (0,2)
3(1,1) = (1,0)
4(1,1) = (0,1)
5(1,1) = (1,2)
6(1,1) = (0,0)
Мы получили все шесть элементов группы.
Значит (1,1) порождает всю группу. Следовательно:
Z2 ⊕ Z3
является cyclic group порядка 6. А любая cyclic group порядка 6 изоморфна Z6.
Поэтому:
Z2 ⊕ Z3 ≅ Z6
Кстати…
Кстати, (1,2) тоже generator. В группе:
Z2 ⊕ Z3
элемент 1 порождает Z2:
<1> = {0,1}
А элемент 2 порождает Z3:
<2> = {0,2,1}
Теперь посмотрим на пару:
(1,2)
Порядок первой координаты:
|1| = 2
Порядок второй координаты:
|2| = 3
Поэтому порядок пары:
|(1,2)| = lcm(2,3) = 6
А во всей группе:
|Z2 ⊕ Z3| = 2·3 = 6
Значит (1,2) имеет тот же порядок, что и вся группа, и потому порождает её целиком.
Но direct product не всегда cyclic
Рассмотрим:
Z2 ⊕ Z2
Её элементы:
(0,0)
(1,0)
(0,1)
(1,1)
У каждого non-identity element порядок равен 2.
Например:
(1,0) + (1,0) = (0,0)
(0,1) + (0,1) = (0,0)
(1,1) + (1,1) = (0,0)
Ни один элемент не имеет порядка 4. Значит ни один элемент не может породить всю группу. Поэтому:
Z2 ⊕ Z2
не cyclic.
Хотя:
|Z2 ⊕ Z2| = 4
она не изоморфна Z4 потому что Z4 cyclic, а Z2 ⊕ Z2 — нет.
Какие вообще бывают группы порядка 4?
Если не смотреть на названия элементов, а смотреть только на структуру, то существуют ровно два варианта:
Z4
и:
Z2 ⊕ Z2
Z4 cyclic:
Z4 = <1>
А в Z2 ⊕ Z2 каждый non-identity element имеет порядок 2. Это показывает, что одинаковый порядок группы ещё не означает одинаковую структуру.
Теорема: Порядок элемента в direct product
Пусть есть элемент:
(g1, g2, ..., gn)
в direct product конечных групп.
Тогда его порядок равен least common multiple / наименьшему общему кратному порядков компонентов:
|(g1, g2, ..., gn)|
=
lcm(|g1|, |g2|, ..., |gn|)
Почему используется lcm
Элемент:
(g1, g2, ..., gn)
вернётся в identity, когда одновременно:
g1^k = e1
g2^k = e2
...
gn^k = en
То есть k должно быть кратно порядку каждой компоненты.
Самое маленькое такое число — это:
lcm(|g1|, |g2|, ..., |gn|)
Простой пример
Пусть:
|a| = 2
|b| = 3
Тогда:
|(a,b)| = lcm(2,3) = 6
Почему? Первая компонента возвращается в identity каждые 2 шага:
2, 4, 6, ...
Вторая — каждые 3 шага:
3, 6, 9, ...
Впервые обе возвращаются одновременно на шаге 6.
Пример в Z2 ⊕ Z3
Порядок элемента:
(1,1)
Первая компонента 1 ∈ Z2 имеет порядок:
|1| = 2
Вторая компонента 1 ∈ Z3 имеет порядок:
|1| = 3
Поэтому:
|(1,1)| = lcm(2,3) = 6
А так как вся группа имеет порядок 6, элемент (1,1) порождает всю группу.
Теорема: Когда direct product двух cyclic groups тоже cyclic
Пусть:
G
H
— finite cyclic groups.
Тогда:
G ⊕ H
является cyclic тогда и только тогда, когда порядки групп взаимно просты:
gcd(|G|, |H|) = 1
Почему
Пусть:
G = <a>
H = <b>
Тогда порядок элемента:
(a,b)
равен:
|(a,b)| = lcm(|G|, |H|)
Чтобы (a,b) породил весь direct product, его порядок должен быть равен размеру всей группы:
|G ⊕ H| = |G||H|
Поэтому нужно:
lcm(|G|, |H|) = |G||H|
А это выполняется ровно тогда, когда:
gcd(|G|, |H|) = 1
Пример: Z2 ⊕ Z3
Порядки групп:
|Z2| = 2
|Z3| = 3
Они взаимно просты:
gcd(2,3) = 1
Поэтому:
Z2 ⊕ Z3
cyclic.
И:
Z2 ⊕ Z3 ≅ Z6
Контрпример: Z2 ⊕ Z4
Порядки:
2
4
не взаимно просты:
gcd(2,4) = 2
Максимальный возможный порядок элемента:
lcm(2,4) = 4
Но размер всей группы:
|Z2 ⊕ Z4| = 2 · 4 = 8
Чтобы группа была cyclic, в ней должен быть элемент порядка 8. Но максимальный порядок здесь только 4.
Значит:
Z2 ⊕ Z4
не cyclic.
Несколько cyclic groups
Direct product:
G1 ⊕ G2 ⊕ ... ⊕ Gn
finite cyclic groups является cyclic тогда и только тогда, когда порядки всех групп попарно взаимно просты.
То есть:
gcd(|Gi|, |Gj|) = 1
для любых:
i != j
Пример
Z2 ⊕ Z3 ⊕ Z5
Порядки:
2, 3, 5
попарно взаимно просты.
Поэтому группа cyclic и:
Z2 ⊕ Z3 ⊕ Z5 ≅ Z30
Контрпример
Z2 ⊕ Z6
Так как:
gcd(2,6) = 2
эта группа не cyclic.
И хотя её порядок:
|Z2 ⊕ Z6| = 12
она не изоморфна Z12.
Когда Z_m ≅ Z_n1 ⊕ ... ⊕ Z_nk
Пусть:
m = n1n2...nk
Тогда:
Z_m ≅ Z_n1 ⊕ Z_n2 ⊕ ... ⊕ Z_nk
тогда и только тогда, когда числа:
n1, n2, ..., nk
попарно взаимно просты.
Пример
Так как:
30 = 2 · 3 · 5
и числа 2, 3, 5 попарно взаимно просты:
Z30 ≅ Z2 ⊕ Z3 ⊕ Z5
Также:
Z30 ≅ Z6 ⊕ Z5
потому что:
gcd(6,5) = 1
Неудачный пример
Z60
не изоморфна:
Z2 ⊕ Z30
Хотя:
2 · 30 = 60
числа 2 и 30 не взаимно просты:
gcd(2,30) = 2
Поэтому direct product не cyclic, а Z60 cyclic.
Значит:
Z2 ⊕ Z30 not ≅ Z60
Группа U(n) как external direct product
До этого мы рассматривали direct products обычных cyclic groups:
Z_m ⊕ Z_n
Теперь применим ту же конструкцию к группам обратимых элементов modulo n:
U(n)
Напомним:
U(n) = {x ∈ Z_n | gcd(x, n) = 1}
Операция в U(n) — multiplication modulo n.
Например:
U(10) = {1, 3, 7, 9}
Специальная подгруппа U_k(n)
Пусть:
k divides n
Определим:
U_k(n) = {x ∈ U(n) | x ≡ 1 (mod k)}
То есть U_k(n) состоит из тех элементов U(n), которые дают остаток 1 modulo k. Важно не путать:
U_k(n)
и:
U(k)
Это разные объекты.
U(k)— самостоятельная группа units modulok;U_k(n)— специальная подгруппа внутриU(n).
Пример: U_3(15)
Сначала выпишем:
U(15) = {1, 2, 4, 7, 8, 11, 13, 14}
Теперь оставим элементы, которые равны 1 modulo 3:
1 ≡ 1 (mod 3)
4 ≡ 1 (mod 3)
7 ≡ 1 (mod 3)
13 ≡ 1 (mod 3)
Получаем:
U_3(15) = {1, 4, 7, 13}
Теорема: разложение U(st)
Пусть:
gcd(s, t) = 1
То есть s и t взаимно просты.
Тогда:
U(st) ≅ U(s) ⊕ U(t)
Иными словами, multiplicative structure modulo st можно разделить на две независимые компоненты:
modulo s
и:
modulo t
Как выглядит isomorphism
Определим mapping:
Φ : U(st) -> U(s) ⊕ U(t)
по правилу:
Φ(x) = (x mod s, x mod t)
То есть берём один элемент modulo st и смотрим на его остатки отдельно modulo s и modulo t.
Конкретный пример: U(15)
Так как:
15 = 3 · 5
и:
gcd(3, 5) = 1
получаем:
U(15) ≅ U(3) ⊕ U(5)
Mapping выглядит так:
Φ(x) = (x mod 3, x mod 5)
Например:
Φ(7) = (1, 2)
потому что:
7 ≡ 1 (mod 3)
7 ≡ 2 (mod 5)
А:
Φ(13) = (1, 3)
потому что:
13 ≡ 1 (mod 3)
13 ≡ 3 (mod 5)
Структура U(15)
Так как:
U(3) ≅ Z2
и:
U(5) ≅ Z4
то:
U(15) ≅ U(3) ⊕ U(5) ≅ Z2 ⊕ Z4
Поэтому порядок группы:
|U(15)| = 2 · 4 = 8
И действительно:
U(15) = {1, 2, 4, 7, 8, 11, 13, 14}
содержит ровно 8 элементов.
Однако:
U(15) not ≅ Z8
Хотя обе группы имеют по 8 элементов, этого недостаточно для isomorphism.
Группа Z8 cyclic:
Z8 = <1>
В ней есть элемент порядка 8:
|1| = 8
А:
U(15) ≅ Z2 ⊕ Z4
Порядок любого элемента (a, b) в Z2 ⊕ Z4 равен:
|(a,b)| = lcm(|a|, |b|)
В Z2 порядок компоненты может быть максимум 2, а в Z4 — максимум 4.
Поэтому максимальный возможный порядок элемента:
lcm(2,4) = 4
То есть в Z2 ⊕ Z4 вообще нет элемента порядка 8, а значит эта группа не cyclic.
Изоморфизм обязан сохранять порядки элементов и свойство cyclic, поэтому:
Z2 ⊕ Z4 not ≅ Z8
и, следовательно:
U(15) not ≅ Z8
Почему это действительно isomorphism
Нужно проверить, что mapping:
Φ(x) = (x mod s, x mod t)
является one-to-one, onto и сохраняет операцию.
Mapping корректно задан
Если:
x ∈ U(st)
то:
gcd(x, st) = 1
Значит x не имеет общих делителей ни с s, ни с t:
gcd(x, s) = 1
gcd(x, t) = 1
Поэтому:
x mod s ∈ U(s)
и:
x mod t ∈ U(t)
Следовательно:
Φ(x) ∈ U(s) ⊕ U(t)
Operation-preserving
Операция во всех этих группах — multiplication modulo соответствующего числа.
Берём:
x, y ∈ U(st)
Тогда:
Φ(xy)
=
(xy mod s, xy mod t)
Но умножение совместимо с остатками:
xy mod s = (x mod s)(y mod s) mod s
и:
xy mod t = (x mod t)(y mod t) mod t
Поэтому:
Φ(xy) = Φ(x)Φ(y)
То есть операция сохраняется.
One-to-one и onto
Здесь работает Chinese Remainder Theorem / Китайская теорема об остатках.
Она говорит, что если:
gcd(s, t) = 1
то для любой пары остатков:
(a mod s, b mod t)
существует ровно один соответствующий класс:
x mod st
То есть каждая пара из:
U(s) ⊕ U(t)
соответствует ровно одному элементу U(st).
Поэтому Φ одновременно one-to-one и onto. Значит:
U(st) ≅ U(s) ⊕ U(t)
Проверка операции на конкретных числах
В U(15) возьмём: 7, 13. Перемножаем modulo 15:
7 · 13 = 91 ≡ 1 (mod 15)
Значит:
Φ(7 · 13) = Φ(1) = (1, 1)
Теперь сначала применим Φ:
Φ(7) = (1, 2)
Φ(13) = (1, 3)
Перемножим покомпонентно:
(1, 2)(1, 3)
=
(1 · 1 mod 3, 2 · 3 mod 5)
Получаем:
(1, 6 mod 5) = (1, 1)
То есть:
Φ(7 · 13) = Φ(7)Φ(13)
Операция действительно сохранилась.
Связь с подгруппами U_s(st) и U_t(st)
Теорема также утверждает:
U_s(st) ≅ U(t)
и:
U_t(st) ≅ U(s)
Напомним:
U_s(st)
— это элементы U(st), которые равны 1 modulo s.
Пример для U(15)
Так как:
15 = 3 · 5
получаем:
U_3(15) ≅ U(5)
Мы уже нашли:
U_3(15) = {1, 4, 7, 13}
А:
U(5) = {1, 2, 3, 4}
У обеих групп по 4 элемента, и их multiplication structure совпадает через reduction modulo 5.
Например mapping:
x -> x mod 5
даёт:
1 -> 1
4 -> 4
7 -> 2
13 -> 3
То есть все элементы U(5) покрыты ровно по одному разу.
Аналогично:
U_5(15) = {1, 11}
и:
U_5(15) ≅ U(3)
Разложение на несколько компонентов
Пусть:
m = n1n2...nk
и числа:
n1, n2, ..., nk
попарно взаимно просты:
gcd(ni, nj) = 1
при:
i != j
Тогда:
U(m)
≅
U(n1) ⊕ U(n2) ⊕ ... ⊕ U(nk)
То есть можно разложить U(m) на несколько независимых modular components.
Пример: U(105)
Разложим:
105 = 3 · 5 · 7
Числа:
3, 5, 7
попарно взаимно просты.
Поэтому:
U(105)
≅
U(3) ⊕ U(5) ⊕ U(7)
Также можно группировать множители иначе:
105 = 7 · 15
и:
gcd(7, 15) = 1
поэтому:
U(105) ≅ U(7) ⊕ U(15)
Ещё вариант:
105 = 21 · 5
и:
gcd(21, 5) = 1
значит:
U(105) ≅ U(21) ⊕ U(5)
Все эти записи описывают одну и ту же группу разными способами.
Разложение U(105) на cyclic groups
Нам известны структуры:
U(3) ≅ Z2
U(5) ≅ Z4
U(7) ≅ Z6
Поэтому:
U(105)
≅
Z2 ⊕ Z4 ⊕ Z6
Это гораздо удобнее, чем работать напрямую со всеми units modulo 105.
Структура U(p^n)
Пусть p — нечётное простое число, а n ≥ 1 — целое число, которое используется как показатель степени.
Тогда:
p^n
— степень простого числа, а:
U(p^n)
— группа обратимых элементов modulo p^n.
Для нечётного простого p группа U(p^n) является cyclic и имеет порядок:
|U(p^n)| = p^n - p^(n-1)
Эта же формула является значением Euler totient function:
φ(p^n) = p^n - p^(n-1)
Её также можно записать так:
φ(p^n) = p^(n-1)(p - 1)
Поэтому:
U(p^n) ≅ Z_(p^n - p^(n-1))
Пример: U(9)
Представим 9 как степень простого числа:
9 = 3^2
Значит:
p = 3
n = 2
Подставляем в формулу:
|U(3^2)| = 3^2 - 3^(2-1)
Получаем:
|U(9)| = 9 - 3 = 6
Поэтому:
U(9) ≅ Z6
Сама группа:
U(9) = {1, 2, 4, 5, 7, 8}
В ней действительно 6 элементов.
Пример: U(25)
Представим 25 как:
25 = 5^2
Значит:
p = 5
n = 2
Подставляем:
|U(5^2)| = 5^2 - 5^(2-1)
Получаем:
|U(25)| = 25 - 5 = 20
Поэтому:
U(25) ≅ Z20
Ещё пример: U(27)
27 = 3^3
Значит:
p = 3
n = 3
Подставляем:
|U(3^3)| = 3^3 - 3^(3-1)
Получаем:
|U(27)| = 27 - 9 = 18
Следовательно:
U(27) ≅ Z18
Откуда берётся формула
Всего классов modulo p^n:
p^n
Необратимыми являются числа, которые делятся на p.
Таких чисел:
p^(n-1)
Поэтому количество обратимых элементов:
p^n - p^(n-1)
Главное:
p— нечётное простое число, аn— показатель степени в числеp^n.
Особый случай степеней двойки
Для нечётного простого p группа U(p^n) cyclic. Но для степеней двойки, начиная с 8, структура уже другая.
Самые маленькие случаи:
U(2) = {1}
Поэтому:
U(2) ≅ {e}
Далее:
U(4) = {1, 3}
Элемент 3 имеет порядок 2, поэтому:
U(4) ≅ Z2
А для:
n >= 3
выполняется:
U(2^n) ≅ Z_(2^(n-2)) ⊕ Z2
То есть группа уже не cyclic: она раскладывается в direct product двух cyclic components.
Пример: U(16)
Представим:
16 = 2^4
Значит:
n = 4
Подставляем в формулу:
U(2^4) ≅ Z_(2^(4-2)) ⊕ Z2
Получаем:
U(16) ≅ Z4 ⊕ Z2
Порядок этой группы:
|U(16)| = 4 · 2 = 8
И действительно:
U(16) = {1, 3, 5, 7, 9, 11, 13, 15}
содержит 8 элементов.
При этом:
U(16) not ≅ Z8
потому что в Z4 ⊕ Z2 максимальный порядок элемента равен:
lcm(4, 2) = 4
Элемента порядка 8 там нет, поэтому группа не cyclic.
Пример: U(144)
Разложим модуль:
144 = 16 · 9
Причём:
gcd(16, 9) = 1
Поэтому по Chinese Remainder Theorem:
U(144) ≅ U(16) ⊕ U(9)
Мы уже знаем:
U(16) ≅ Z4 ⊕ Z2
А так как:
9 = 3^2
и 3 — нечётное простое число:
U(9) ≅ Z6
Следовательно:
U(144)
≅
Z4 ⊕ Z2 ⊕ Z6
Порядок группы:
|U(144)| = 4 · 2 · 6 = 48
Это совпадает с:
φ(144) = 48
Почему U(144) ≅ U(105)
Ранее мы получили:
U(105) ≅ Z2 ⊕ Z4 ⊕ Z6
А для U(144):
U(144) ≅ Z4 ⊕ Z2 ⊕ Z6
Порядок компонентов в direct product не влияет на структуру:
Z4 ⊕ Z2 ⊕ Z6
≅
Z2 ⊕ Z4 ⊕ Z6
Поэтому:
U(105) ≅ U(144)
Важно:
одинакового количества элементов недостаточно для isomorphism. Здесь группы изоморфны потому, что обе раскладываются в одинаковые cyclic components.
Зачем вообще раскладывать U(n)
На первый взгляд можно спросить: зачем заменять одну группу direct product нескольких групп?
Потому что структура становится намного прозрачнее.
Сразу виден порядок группы
Из:
U(105) ≅ Z2 ⊕ Z4 ⊕ Z6
сразу получаем:
|U(105)| = 2 · 4 · 6 = 48
Это совпадает с Euler totient function:
φ(105) = 48
Легко находить возможные порядки элементов
Для элемента:
(a, b, c) ∈ Z2 ⊕ Z4 ⊕ Z6
порядок равен:
lcm(|a|, |b|, |c|)
В компонентах возможны порядки:
Z2: 1, 2
Z4: 1, 2, 4
Z6: 1, 2, 3, 6
Поэтому возможные порядки элементов U(105):
1, 2, 3, 4, 6, 12
Например, элемента порядка 24 там быть не может.
Пример: сколько элементов порядка 12 в U(105)
Мы знаем, что:
U(105) ≅ Z2 ⊕ Z4 ⊕ Z6
Изоморфизм сохраняет порядки элементов. Поэтому вместо прямой работы с U(105) можно посчитать элементы порядка 12 в более понятной группе:
Z2 ⊕ Z4 ⊕ Z6
Элемент этой группы имеет вид:
(a, b, c)
где:
a ∈ Z2
b ∈ Z4
c ∈ Z6
Порядок такого элемента равен:
|(a,b,c)| = lcm(|a|, |b|, |c|)
Нам нужно получить:
lcm(|a|, |b|, |c|) = 12
Так как:
12 = 4 · 3
среди компонентов обязательно должны появиться множители 4 и 3.
Компонент b ∈ Z4
Только компонент из Z4 может дать порядок 4.
В Z4 элементы порядка 4:
1, 3
Значит для b есть 2 варианта.
Компонент c ∈ Z6
Чтобы добавить множитель 3, элемент c должен иметь порядок 3 или 6.
В Z6:
elements of order 3: 2, 4
elements of order 6: 1, 5
Значит для c есть 4 варианта.
Оба порядка подходят:
lcm(4,3) = 12
lcm(4,6) = 12
Компонент a ∈ Z2
В Z2 есть два элемента:
0, 1
Их порядки:
|0| = 1
|1| = 2
Оба подходят, потому что ни 1, ни 2 не меняют уже полученный порядок 12:
lcm(1,4,3) = 12
lcm(2,4,3) = 12
lcm(1,4,6) = 12
lcm(2,4,6) = 12
Значит для a есть 2 варианта.
Считаем все комбинации
2 варианта для a
2 варианта для b
4 варианта для c
Поэтому:
2 · 2 · 4 = 16
Значит в:
Z2 ⊕ Z4 ⊕ Z6
ровно 16 элементов порядка 12.
А поскольку:
U(105) ≅ Z2 ⊕ Z4 ⊕ Z6
то и в U(105) тоже ровно:
16
элементов порядка 12.
Главная идея:
direct product позволяет считать порядок сложного элемента через
lcmпорядков его компонентов.
Связь с automorphisms
Ранее мы получили:
Aut(Z_n) ≅ U(n)
Поэтому:
Aut(Z_105) ≅ U(105)
А значит из структуры:
U(105) ≅ Z2 ⊕ Z4 ⊕ Z6
следует, что в группе:
Aut(Z_105)
тоже есть ровно:
16
automorphisms порядка 12.
Без direct product такую информацию было бы намного сложнее получить напрямую.
Почему условие взаимной простоты необходимо
Теорема:
U(st) ≅ U(s) ⊕ U(t)
требует:
gcd(s, t) = 1
Без этого утверждение может быть неверным.
Например:
20 = 10 · 2
но:
gcd(10, 2) = 2
Сравним размеры.
|U(20)| = φ(20) = 8
А:
|U(10)| = 4
и:
|U(2)| = 1
Поэтому:
|U(10) ⊕ U(2)| = 4 · 1 = 4
Получаем:
|U(20)| = 8
но:
|U(10) ⊕ U(2)| = 4
Группы даже имеют разный порядок, поэтому не могут быть isomorphic.
Связь с Chinese Remainder Theorem
Chinese Remainder Theorem / Китайская теорема об остатках отвечает на такой вопрос:
Если мы знаем остатки неизвестного целого числа при делении на несколько взаимно простых модулей, можем ли мы восстановить это число хотя бы с точностью до некоторого общего модуля?
Пусть:
gcd(s, t) = 1
То есть s и t взаимно просты.
Рассмотрим систему:
x ≡ a (mod s)
x ≡ b (mod t)
Теорема утверждает две вещи:
- такая система всегда имеет решение;
- это решение единственно modulo
st.
Иными словами, существует ровно один класс остатков modulo st, элементы которого одновременно дают остаток a при делении на s и остаток b при делении на t.
Это можно записать как соответствие:
x mod st <-> (x mod s, x mod t)
Каждому классу modulo st соответствует ровно одна пара остатков:
(a, b)
И наоборот: любая возможная пара остатков modulo s и modulo t определяет ровно один класс modulo st.
Почему появляется произведение st
Если два числа x и y дают одинаковые остатки modulo s и modulo t, то:
x ≡ y (mod s)
и:
x ≡ y (mod t)
Значит их разность делится и на s, и на t:
s | (x - y)
t | (x - y)
Так как s и t взаимно просты, их разность должна делиться на произведение:
st | (x - y)
Следовательно:
x ≡ y (mod st)
Поэтому решение единственно именно modulo st.
Это не означает, что существует только одно целое решение. Все решения отличаются друг от друга на число, кратное st:
x = x0 + kst
где:
k ∈ Z
Маленький пример
Решим систему:
x ≡ 2 (mod 5)
x ≡ 6 (mod 7)
Числа 5 и 7 взаимно просты, поэтому по Chinese Remainder Theorem существует единственное решение modulo:
5 · 7 = 35
Одно из решений:
x = 27
Проверяем:
27 ≡ 2 (mod 5)
и:
27 ≡ 6 (mod 7)
Значит общее решение:
x ≡ 27 (mod 35)
или в обычном виде:
x = 27 + 35k
Все числа из этой последовательности дают те же два остатка.
Для нескольких попарно взаимно простых модулей идея та же.
Если известна система:
x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
...
x ≡ ak (mod nk)
и все ni попарно взаимно просты, то существует единственное решение modulo:
N = n1n2...nk
Именно поэтому несколько отдельных остатков можно «склеить» в один класс остатков modulo произведения всех модулей.
Пример: modulo 15
Возьмём:
15 = 3 · 5
Причём:
gcd(3, 5) = 1
Допустим, мы знаем, что число x удовлетворяет:
x ≡ 1 (mod 3)
x ≡ 2 (mod 5)
Ищем число от 0 до 14, которое подходит под оба условия.
Числа, равные 1 modulo 3:
1, 4, 7, 10, 13
Из них остаток 2 modulo 5 даёт только 7. Значит:
x ≡ 7 (mod 15)
То есть пара:
(1 mod 3, 2 mod 5)
однозначно соответствует элементу:
7 mod 15
Именно это утверждает Chinese Remainder Theorem.
Пример с U(15)
Так как:
15 = 3 · 5
и:
gcd(3, 5) = 1
то:
U(15) ≅ U(3) ⊕ U(5)
Например:
7 ∈ U(15)
и:
Φ(7) = (1, 2)
где:
1 ∈ U(3)
2 ∈ U(5)
Пара:
(1, 2)
содержит ту же modular information, что и число:
7 mod 15
Главная мысль
Chinese Remainder Theorem позволяет заменить вычисления modulo произведения взаимно простых чисел несколькими независимыми вычислениями по меньшим модулям:
modulo st
заменяется на:
modulo s
modulo t
Поэтому вместо одной сложной группы:
U(st)
можно изучать direct product двух меньших групп:
U(s) ⊕ U(t)
Именно поэтому Chinese Remainder Theorem и direct products постоянно появляются в modular arithmetic, RSA и других криптографических конструкциях.
CRT attack on badly used RSA
Как ни странно, Китайская теорема об остатках может использоваться для взлома (в частности, для прочтения шифрованного сообщения). Идея такая. В RSA encryption обычно выглядит как:
c ≡ m^e (mod n)
где:
m
— message,
e
— public exponent,
n
— public modulus. Числа e и n вместе образуют открытый ключ получателя.
Допустим, кто-то использует маленький exponent:
e = 3
и отправляет один и тот же message нескольким людям без padding. Хотя e входит в открытый ключ, оно не обязано быть уникальным. На практике многие используют одно и то же значение e, а ключи различаются за счёт разных модулей n.
Тогда attacker видит три ciphertexts:
c1 ≡ m^3 (mod n1)
c2 ≡ m^3 (mod n2)
c3 ≡ m^3 (mod n3)
Если n1, n2, n3 взаимно просты, то Chinese remainder theorem позволяет восстановить одно число:
M
такое что:
M ≡ c1 (mod n1)
M ≡ c2 (mod n2)
M ≡ c3 (mod n3)
Причём для независимо сгенерированных RSA-ключей разные модули n1, n2, n3 с практически полной вероятностью попарно взаимно просты (хотя сами по себе простыми не являются), так как они генерируются из больших случайных простых чисел.
Но если message маленький и:
m^3 < n1n2n3
то это M будет не просто congruent to m^3. Это будет буквально:
M = m^3
А дальше attacker просто берёт кубический корень:
m = ∛M
И message восстановлен.
Простой пример
Возьмём:
m = 3
и:
e = 3
Тогда:
m^e = 3^3 = 27
Пусть у нас три разных modulus:
n1 = 5
n2 = 7
n3 = 11
Они pairwise coprime. Теперь encrypt:
c1 ≡ 27 (mod 5) = 2
c2 ≡ 27 (mod 7) = 6
c3 ≡ 27 (mod 11) = 5
Attacker видит:
c1 = 2
c2 = 6
c3 = 5
и public moduli:
5, 7, 11
Теперь attacker решает систему:
M ≡ 2 (mod 5)
M ≡ 6 (mod 7)
M ≡ 5 (mod 11)
Посмотрим пошагово, как здесь работает Chinese remainder theorem. Из первого сравнения:
M ≡ 2 (mod 5)
следует, что M имеет вид:
M = 2 + 5a
для некоторого integer a.
Подставляем это во второе сравнение:
2 + 5a ≡ 6 (mod 7)
Вычитаем 2:
5a ≡ 4 (mod 7)
Обратный элемент для 5 modulo 7 равен 3, потому что:
5 · 3 = 15 ≡ 1 (mod 7)
Умножаем обе стороны на 3:
a ≡ 12 ≡ 5 (mod 7)
Значит:
a = 5 + 7b
для некоторого integer b.
Подставляем обратно:
M = 2 + 5(5 + 7b)
M = 27 + 35b
Теперь используем третье сравнение:
M ≡ 5 (mod 11)
Подставляем найденный вид M:
27 + 35b ≡ 5 (mod 11)
Приводим числа modulo 11:
27 ≡ 5 (mod 11)
35 ≡ 2 (mod 11)
Поэтому:
5 + 2b ≡ 5 (mod 11)
Вычитаем 5:
2b ≡ 0 (mod 11)
Так как 2 обратимо modulo 11, получаем:
b ≡ 0 (mod 11)
Значит:
b = 11k
для некоторого integer k.
Подставляем:
M = 27 + 35 · 11k
То есть все решения системы имеют вид:
M = 27 + 385k
или короче:
M ≡ 27 (mod 385)
Зачем мы умножаем 5, 7 и 11
Chinese remainder theorem говорит, что для попарно взаимно простых moduli решение единственно modulo их произведения:
5 · 7 · 11 = 385
Почему именно произведения?
Если два числа M и M' дают одинаковые остатки modulo 5, 7 и 11, то их разность делится на каждое из этих чисел:
5 | (M - M')
7 | (M - M')
11 | (M - M')
Так как 5, 7 и 11 попарно взаимно просты, разность делится и на их произведение:
385 | (M - M')
Поэтому все решения отличаются друг от друга на число, кратное 385:
..., 27 - 385, 27, 27 + 385, 27 + 2 · 385, ...
Именно это означает фраза:
единственное решение modulo 385
Речь не о единственном integer вообще, а об одном классе остатков:
M ≡ 27 (mod 385)
Обычно выбирают наименьшего неотрицательного представителя этого класса:
M = 27
Почему attacker получил именно m^3
Мы знаем:
m^3 = 27
и:
27 < 385
CRT восстановила значение:
M ≡ m^3 (mod 385)
Но среди чисел от 0 до 384 этому сравнению соответствует только:
M = 27
Поэтому здесь attacker восстановил не просто остаток от m^3, а само число:
M = m^3 = 27
Теперь остаётся взять обычный кубический корень:
m = ∛27 = 3
Если бы:
m^3 >= 385
то CRT дала бы только остаток от m^3 modulo 385, и однозначно восстановить исходное m^3 таким способом уже не получилось бы.
Что здесь сломалось
Сломалось плохое использование RSA:
same message
small exponent
no padding
different recipients
CRT просто дал attacker удобный способ собрать три congruences в одно число. В нормальном RSA используют padding schemes вроде OAEP, чтобы один и тот же message не превращался в один и тот же математический m^e.
Ещё пример
В настоящем RSA moduli не простые, а composite:
n = pq
Но для идеи атаки важно, чтобы разные n1, n2, n3 были pairwise coprime.
Например, пусть:
m = 42
e = 3
Тогда:
m^3 = 42^3 = 74088
Возьмём три moduli:
n1 = 55
n2 = 391
n3 = 1189
Они взаимно просты между собой.
Ciphertexts:
c1 ≡ 74088 (mod 55) = 3
c2 ≡ 74088 (mod 391) = 189
c3 ≡ 74088 (mod 1189) = 370
Attacker решает:
M ≡ 3 (mod 55)
M ≡ 189 (mod 391)
M ≡ 370 (mod 1189)
CRT восстанавливает:
M = 74088
А потом:
∛74088 = 42
Message снова восстановлен без private key.