Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 70

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 64 65 66 67 68 69 < 70 > 71 72 73 74 75 76 .. 311 >> Следующая

Глава 5. Алгебраические основы
185
2. Пусть d > 1 и d | тп — Тогда (а л ^ — подгруппа группы (а), имеющая порядок d, поскольку d — наименьшее целое число, удовлетворяющее условию ^а"? ^ = е. Предположим, что существует другая подгруппа
группы (а), имеющая порядок d и не совпадающая с подгруппой Из пункта 1 следует, что такая подгруппа должна быть циклической и, следовательно, имеет вид (ак) при некотором к > 1. Из равенства akd — — е и минимальности числа тп следует, что тп | kd, т.е. ^ | Таким
образом, ак € т-е- {ак) ^= (°^}' Поскольку обе группы имеют одина-
ковый порядок, (ак) = Это противоречит нашему предположению
(а*)ф(аЪ).
3. Пусть d = gcd(fc, тп). Тогда согласно п. 2 существует единственная подгруппа группы (а), имеющая порядок d. Допустим, что ею является подгруппа (ае) при некотором ? > 1, где ? — наименьшее целое число, удовлетворяющее условию adl - е. Из условия минимальности числа тп следует, что тп | dl, т.е. I ? Наименьшее значение числа ? достигается, когда d = = gcd(?,m), т.е. ?—к.
4. Пусть d | тп = #(а) и ак — произвольный элемент группы (а) при О ^ & < т. Из п. 3 следует, что элемент ак имеет порядок ^ тогда и только тогда, когда ^ = gcd(fc,m). Представим число к в виде к = с1-^, где О ^ с < d. Тогда условие gcd(fc,m) = ^ означает, что gcd(c,d) = 1. По определению 5.11 существует ф{<?) таких чисел с.
5. В силу п. 4 из условия т — #(а) следует, что группа (а) содержит ф(т) элементов порядка т, порождающих группу (а). Согласно п. 3 этими порождающими элементами являются числа аг, удовлетворяющие условию gcd(r, т) = 1. а
Следствие 5.3. Группа, имеющая простой порядок, циклично, и любой ее элемент, не совпадающий с нейтральным, является порождающим.
Доказательство. Пусть G — группа с простым порядком р. Пусть а G G — произвольный элемент, не являющийся нейтральным. Из следствия 5.2 вытекает, что ord(a) | #G = р. Поскольку а ф е, ord(a) ф 1. Тогда ord(a) = р. Следовательно, (a) = G, т.е. число а порождает группу G. ?
186
Часть II. Математические основы
Пример 5.9. Рассмотрим "часовую группу" Z12, которая является циклической.
1. Поскольку 1 | 12, она содержит подгруппу {0}, имеющую порядок 1. Так как ф(1) = 1, единственным элементом, имеющим порядок 1, является число 0.
2. Поскольку 2 | 12, она содержит подгруппу {0,6}, имеющую порядок 2. Так как ф(2) = 1, единственным элементом, имеющим порядок 2, является число 6.
3. Поскольку 3 | 12, она содержит подгруппу {0,4,8}, имеющую порядок 3. В группе существует ф(3) = 2 элемента, имеющих порядок 3: ими являются числа 4 и 8.
4. Поскольку 4 | 12, она содержит подгруппу {0,3,6,9}, имеющую порядок 4. В группе существует ф(4) = 2 элемента, имеющих порядок 4: ими являются числа 3 и 9.
5. Поскольку 6 | 12, она содержит подгруппу {0,2,4,6,8,10}, имеющую порядок 6. В группе существует ф(6) = 2 элемента, имеющих порядок 6: ими являются числа 2 и 10.
6. Поскольку 12 | 12, она содержит подгруппу, имеющую порядок 12. В группе существует $(12) = 4 элемента, имеющих порядок 12: ими являются числа 1, 5, 7 и 11.
Мультипликативная группа Щ анализируется аналогично. ?
5.2.4 Мультипликативная группа Z*
Пусть п = pq, где р и q — разные нечетные простые числа. Мультипликативная группа Z* играет очень важную роль в современной криптографии. Рассмотрим ее структуру. На протяжении всего раздела будем считать, что число п является составным.
Элементами группы Z* являются положительные целые числа, которые меньше числа п и являются взаимно простыми с ним. По определению 5.11 эта группа состоит из ф(п) = (р — l)(q — 1) элементов (см. лемму 6.1).
Теорема 5.3. Порядок любого элемента в группе Z* является делителем числа lcm(p — l,q—l).
Доказательство. Пусть a G Z*. Из малой теоремы Ферма (теорема 6.10 из раздела 6.4) следует, что
a(p-i) = i(modp). Обозначая А = lcm(p — 1, q — 1), получаем, что
аЛ = l(modp).
Глава 5. Алгебраические основы
187
Аналогично
аА = l(modg).
Эти сравнения означают, что число аА — 1 кратно числам р и q. Поскольку числа р и q являются простыми и не равны друг другу, число аЛ — 1 должно кратным числу п = pq. Следовательно,
Итак, число Л кратно порядку числа а по модулю п. ?
Обратите внимание на то, что числа р — 1 и q — 1 являются четными. Отсюда следует, что Л = lcm(p — 1, q — 1) < (р — l)(g — 1) = ф(п). Из теоремы 5.3 следует, что в группе Z* не существует элемента, имеющего порядок 6{п). Иначе говоря, группа Z* не содержит порождающий элемент. Следовательно, по определению 5.10 группа Z* не является циклической. Величина Л(п) называется числом Кармайкла (Carmichael number).
Пример 5.10. Пусть п — 5 х 7 = 35, а элемент a G Щ5 удовлетворяет следующим условиям: 1) число a(mod5) G Щ, и его максимальный порядок равен 4, т.е. это число порождает циклическое представление группы Щ (левая окружность с периодом 4); 2) число a(mod 7) € Щ, и его максимальный порядок равен 6, т.е. это число порождает циклическое представление группы Щ (правая окружность с пе-
Таким образом, порядок элемента a G Щ5 можно представить в виде периода вращения двух сцепленных шестеренок. Одна из шестеренок имеет четыре зубца, а другая — шесть. Точка сцепления изображена на рисунке более крупной. Представим себе, что шестеренки начали вращаться. Тогда крупная точка разделится на две разные точки, принадлежащие разным окружностям. Эти точки встретятся снова после того, как шестеренка с четырьмя зубьями сделает три оборота, а шестеренка с шестью зубьями — два. Следовательно, порядок (период) элемента a G Щ5 равен расстоянию, пройденному точками между моментом разделения и моментом воссоединения: 3x4 = 2x6 = lcm((5 — 1), (7 — 1)). ?
Предыдущая << 1 .. 64 65 66 67 68 69 < 70 > 71 72 73 74 75 76 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed