Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Доказательство. Если Н = G условие #Н \ #G выполняется тривиальным образом. Рассмотрим вариант, когда Н ф G.
По аксиоме замкнутости для любого элемента а Е G\H смежный класс ооЯ является подмножеством группы G. Докажем два факта.
1. Если для любого элемента а ф о! выполняется условие а ? а' о Н, то (аоЯ)П(о'оЯ) = 0.
2. #(а о #) = ##.
Для доказательства первого факта предположим, что 3b € (а о Н) П (а' о Н). Тогда Эс, d G Н : а о с = Ъ = а' о с1. Применяя аксиомы инверсии, тождества, замкнутости и ассоциативности, получаем
а = оое = оо(со с-1) = Ьо с-1 = (а' о с') о с-1 = а' о (с' о с-1) G а' о Н.
180
Часть II. Математические основы
Это противоречит предположению, что а $ а' о Н. Если же а ^ Н = е о Н, то НП{аоН) = 0.
Для доказательства второго факта отметим, что условие #(а о Н) ^ #Н тривиальным образом вытекает из определения смежного класса. Допустим, что неравенство является строгим. Это возможно лишь тогда, когда для некоторых b ф с, где Ь,сЕ Н, выполняется условие а о Ъ = а о с. Применяя к группе G аксиому инверсии, получаем, что b = с, что противоречит условию Ьф с.
Итак, группа G разбивается на подгруппу if и семейство ее попарно непересекающихся смежных классов, каждый из которых имеет размер #Н. Следовательно, #// | #G. (Разбиение множества означает его разделение на непересекающиеся подмножества.) о
Пример 5.4.
1. Проверим пример 5.2.3: условие #Н | #Zi2 выполняется для каждой подгруппы Н "часовой группы" Z12.
2. Конкретизируем пример 5.2.5 для случая, когда п = 21. Тогда подгруппа Fermat(21) = {1,8,13,20} удовлетворяет условию #Fermat(21) = 4 |
Теорема Лагранжа имеет очень большое значение для приложений. Вернемся к вероятностному алгоритму проверки простоты числа PrimeTest, рассмотренному в разделе 4.4.3.1. Этот алгоритм проверяет, является ли нечетное целое число п простым, выполняя сравнение
где х Е и^п — случайное число. Анализируя пример 5.2.5, мы убедились, что множество Fermat(n) является подгруппой группы Z*, определенной этим сравнением, причем она является собственной подгруппой группы Z* тогда и только тогда, когда число п не является простым. Следовательно, по теореме Лагранжа #Fermat(n) | Значит, если число п — не простое, величина #Fermat(n)
не превышает половины числа Итак, вероятность ошибки на каждом шаге проверки не превышает \. Это гарантирует работоспособность алгоритма PrimeTest, вероятностным пространством которого является группа Z*.
Другое важное применение теоремы Лагранжа в криптографии с открытым ключом будет рассмотрено в разделе 5.2.2.
Определение 5.8 (Фактор-группа). Пусть G — абелева группа и HC.G. Факторгруппой G/H группы G по модулю Н называется множество всех смежных классов аоН, где элемент а пробегает все множество G с групповой операцией *, определенной по правилу (а о Н) * (Ь о Н) = (а о Ь) о Н, и нейтральным элементом
12 = #Z|
?
х
:(n-l)/2 = ±lmDdnj
еоН.
Глава 5. Алгебраические основы
181
Пример 5.5. Пусть п > 0 — целое число. Множество nZ = {0. ±п, ±2п,... } является подгруппой группы Z относительно целочисленного сложения. Факторгруппа
Z/nZ = {x+nZ\xeZ}
может состоять только из конечного количества элементов, поскольку п + nZ = = 0 + nZ, п + 1 + nZ = 1 + nZ и т.д. Следовательно,
Z/(nZ) = {0 + nZ,l+nZ,2 + nZ,...,n-l + nZ}.
Учитывая, что множество nZ может содержать только нуль по модулю п, приходим к выводу, что
Z/nZ = Zn. а
Обозначение Z/nZ является стандартным для группы Zn. Однако для удобства в книге используется более короткое обозначение Zn.
Следствие 5.1. Пусть G — конечная абелева группа и Н С G. Тогда
Пример 5.6. Пусть тип — положительные целые числа, удовлетворяющие условию m | п. Из примера 5.5 вытекают следующие утверждения.
1. Множество mZn = {0, m, 2m,..., [i^rJ "m} является подгруппой группы (Zn, +) и состоит изп/т элементов.
2. Zn/mZn - Zm.
3. №JmZn) = #Zm = m = ^ = ф1-у
В качестве примера рассмотрим "часовую группу" Z\2 (т.е. п — 12) и ее подгруппу 3Zi2 = {0,3,6,9} (т.е. m = 3). Читатель может повторить анализ примера 5.5 и убедиться, что Z^/SZu — Z3. Следовательно, #(^12/3^12) = #Z$ = = 3 = 12/4 = ^Ц^у- Аналогично доказываются все остальные варианты для m | 12. ?
5.2.2 Порядок элемента группы
Не только нейтральный, но и другие элементы группы могут иметь особые свойства. Одним из таких свойств является "расстояние" от нейтрального элемента
182
Часть II. Математические основы
Определение 5.9 (Порядок элемента группы). Пусть G — группа и а Е G. По-\ рядком элемента а называется наименьшее положительное число ieN, удовлеЛ творяющее условию аг = е. Это число обозначается ord(a). Если такое число г\ не существует, то элемент а называется элементом бесконечного порядка.
Напомним, что обозначение аг представляет собой сокращение, введенное в определении 5.4 и проиллюстрированное в замечании 5.1.
Пример 5.7.
1. В "часовой группе" Ъ\2 ord(l) = 12, поскольку 12 — это наименьшее положительное число, удовлетворяющее условию 12 -1 = 0(mod 12). Читатель может самостоятельно проверить, что ord(2) = 6,ord(3) = 4,ord(4) =\ = 3, ord(5) = 12. Попробуйте определить порядки остальных элементов.
