Алгоритмы - построение и анализ (1021735), страница 199
Текст из файла (страница 199)
Таким образом, группы (2„, +„) и (Е;„.„) будут обозначаться как 2„и Е„' соответственно. Элемент, обратный (относительно умножения) к элементу а, будет обозначаться как (а 1 тос1 и). Операция деления в множестве Е„' определяется уравнением а/5— : аб 1(тог1п). Например, в множестве Еш 7 ~ = 13 (тос(15), поскольку 7 13 ив э 91 = 1(п1ос115), поэтому 4/7 е— э 4 13 = 7(п1од15). Обозначим размер множества г;, как ф(п). Эта функция, известная под названием ф-функции Эйлера (Еи!ег'з рЫ йшсг1оп), удовлетворяет уравнению (31.19) где индекс р пробегает значения всех простых делителей числа и (включая само и„ если оно простое). Здесь мы не станем доказывать эту формулу, а попробуем дать для нее интуитивное пояснение. Выпишем все возможные остатки от деления на п — (О, 1,..., п — Ц, а затем для каждого простого делителя р числа п вычеркнем из этого списка все элементы, кратные р.
Например, простые делители числа 45— числа 3 н 5, поэтому ф (45) = 45 1 — — 1 — — = 45 — — = 24. Если р — простое число, то Е„" = (1,2,...,р — Ц и ф(р) = р — 1. (31.20) Если же п — составное, то ф (и) ( п — 1. Подгруппы Если (Я, ®) — группа, У С Я и (У, Ю) — тоже группа, то (У, 03) называется подгруппой (зцЬйгоир) группы (Я,(9).
Например, четные числа образуют подгруппу группы целых чисел с операцией сложения. Полезным инструментом для распознавания подгрупп является сформулированная ниже теорема. Глава 31. Теоретико-числовые алгоритмы 973 Теорема 31.14. (Непустое замкнутое подмножество конечной группы является подгруппой). Если (Я, Ю) — конечная группа, а У вЂ” любое непустое подмножество множества Я, такое что а Ю Ь б У для всех а, 6 Е У, то (У, Ю) — подгруппа группы (Я, ®). Доказапсельспсво. Доказать эту теорему читателю предлагается самостоятельно в упражнении 31.3-2. И Например, множество (0,2,4,6) образует подгруппу группы Еа, поскольку оно непустое и замкнутое относительно операции + (т.е.
оно замкнуто относительно операции +в). Сформулированная ниже теорема крайне полезна для оценки размера подгруппы; доказательство этой теоремы опущено. Теорема 31.15 (Теорема Лагранжа). Если (Я, 9) — конечная группа, и (У, Ю)— ее подгруппа, то (У) — делитель числа !Я!.
И Подгруппу У группы Я называю~ истинной (ргорег) подгруппой, если У ф Я. Приведенное ниже следствие из этой теоремы окажется полезным при анализе теста простых чисел Миллера-Рабина (Мй!ег-йаЬ1п), описанного в разделе 31дй Следствие 31.16. Если У вЂ” истинная подгруппа конечной группы Я, то ~У~ < < ф)/2.
И Подгруппы, сгенерированные элементом группы Теорема 3! .14 обеспечивает интересный способ, позволяющий сформировать подгруппу конечной группы (Я, 9). Для этого следует выбрать какой-нибудь элемент группы а и выделить все элементы, которые можно сгенерировать с помощью элемента а и групповой операции.
Точнее говоря, определим элемент а1Я1 дляк) 1как Например, если в группе Еа задать элемент а = 2, то последовательность а01, а!~1,... имеет вид 2,4,0,2,4,0,2,4,0,.... В группе Е„справедливо соотношение а!"1 = ка шос! и, а в группе Е,*, — соотношение а!"1 = аь шос! п. Подгруппа, сгенерированная элементом а (зцЬйгоир йепегагеб Ьу а) обозначается как (а) или ((а), Ю) и определяется следующим образом: (а) = (а! 1:/с>1). 974 Часть Ч11. Избранные темы Говорят, что элемент а генерируем (8епега1ез) подгруппу (а) или что а — генератор (8епегагог) подгруппы (а). Поскольку множество Я конечное, то (а)— конечное подмножество множества Я, которое может содержать все элементы множества Я.
Поскольку из ассоциативности операции Ю следует соотношение ас') Е ао) Ои-У) то подмножество (а) — замкнутое и, согласно теореме 31.14, (а) — подгруппа группы Я. Например, в группе Еа справедливы соотношения (0) = (О), (1) = (0,1,2,3,4,5), (2) = (0,2,4). Аналогично, в группе Щ (1) = (1), (2) = (1,2,4), (3) = (1,2,3,4,5,6). Порядок (оп)ег) элемента а (в группе Я) обозначается как огг1 (а) и определяется как наименьшее положительное целое число г, для которого выполняется соотношение ай) = е.
Теорема 31.17. Для любой конечной группы (Я, Ю) и любого ее элемента а Е Я порядок элемента равен размеру генерируемой им подгруппы, т.е. огс1 (а) = ~ (а) ~. Доказаиельсюаво. Пусть г = огг1 (а). Поскольку для й > 1 справедливы соотношения ай) = е и ай+") = а10 Ю а(") = а1"), то при г > 1 для некоторого у < в' выполняется равенство а10 = а0). Таким образом, после элемента ай) не появляется никаких новых элементов, так что (а) = (а0), а(з),..., а10 ) и 1(а)1 < г. Докажем неравенство 1(а) ! > 1 методом "от противного". Предположим, что при некоторых 1 и ), удовлетворяющих неравенству 1 < 1 < 7' < 1, выполняется равенство а10 = а13).
Тогда при )с > 0 ай+~) = аО+ь). Однако из этого следует, что а1'+О У)) = ай+О 3)) = е. Так мы приходим к противоречию, поскольку г+ (1 — ) ) < г, но 1 — наименьшее положительное значение такое, что ай) = е. Поэтому все элементы последовательности а("), а(з),..., ай) различны, и 1(а) ! > г. Таким образом, мы приходим к заключению, что огд (а) = ~(а) ~. и Следствие 31.18.
Последовательность а0), а(з),... является периодической с пе- риодом 1 = оп1 (а); т.е. а(0 = а0) тогда и только тогда, когда г = 7' (шогИ). Глава 31. Теоретико-числовые алгоритмы 975 С приведенным следствием согласуется определение а(о) как е, а аб) для всех целых 1 как аб "' ~ '1, где Ф = огс1 (а). Следствие 31.19. Если (Я, Ю) — конечная группа с единичным элементом е, то для всех а Е Я выполняется соотношение ай 1)=е. Доказавсельсвсво.
Из теоремы Лагранжа следует, что огс1 (а) / Д, так что ф/ =- : — 0 (шос11), где 1 = оп1 (а). Следовательно, абл<1 = а(о) = е. Упражнения 31.3-1. Составьте таблицу операций для групп (Е4, +4) и (Ез, в). Покажите, что этн группы изоморфны. Для этого обоснуйте взаимное однозначное соответствие сг между элементами этих групп, такое что а+ Ь= с (гпос(4) тогда и только тогда, когда о (а) . сс (Ь) = о (с) (тпос15). 31.3-2.
Докажите теорему 31.14. 31.3-3. Покажите, что если р — простое число, а е — положительное целое число, то справедливо соотношение ф (р') = р' ' (р — 1). 31.3-4. Покажите, что для любого числа п > 1 и для любого а е Е„' функция г'„: Е„' Е„', определяемая соотношением г" (х) = ах шос1 п, представляет собой перестановку Е;,. 3!.3-5. Перечислите все подгруппы групп Ев и Е*,з. 31.4 Решение модульных линейных уравнений Теперь рассмотрим задачу о решении уравнений вида ах г— в Ь (тос1п), (31.21) где а > 0 и и > О. Эта задача имеет несколько приложений.
Например, она используется как часть процедуры, предназначенной для поиска ключей для криптографической схемы В5А с открытым ключом, описанной в разделе 31.7. Предположим, что для заланных чисел а, Ь и и нужно найти все значения переменной х, которые удовлетворяют уравнению (31.21). Количество решений может быть равным нулю, единице, или быть больше единицы. Обозначим через (а) подгруппу группы Е„, сгенерированную элементом а. Поскольку (а) = (а(з): х > 0) = (ах шос1 п: х > О), уравнение (31.21) имеет Часть Ч11. Избранные темы 976 решение тогда и только тогда, когда Ь е (а). В теореме Лагранжа (теорема 31.15) утверждается, что величина ~(а) ~ должна быть делителем числа п.
Сформулированная ниже теорема дает точную характеристику подгруппы (а). Теорема 31.20. Для всех положительных целых чисел а и п из соотношения Н = бей(а,п) следует, что (а) = (с1) = (О,Ы,2с(,..., ((и/с1) — 1)<Ц (31.22) в с„, так что )(а) / = и/й. Доказательство. Для начала покажем, что Н Е (а).
Напомним, что процедура Ехтнмпнп Еоп.пз(а, п) выдает целые числа х' и у', удовлетворяющие уравнению ах'+ пу' = Ы. Таким образом, выполняется соотношение ах' = д (пзос1п), так что и е (а). Поскольку Ы Е (а), можно сделать вывод, что подгруппе (а) принадлежат все числа, кратные Н, так как любое число, кратное числу, кратному а, является кратным числу а. Таким образом, подгруппа (а) содержит все элементы множества (О, с(, 2Н,..., ((п/ф — 1) с1), т е. (Н) С (а). Теперь покажем, что (а) С (с1). Если т б (а), то для некоторого целого числа х выполняется равенство т = ах пюй п, так что т = ах + пу для некоторого целого у.
Однако И ! а и И ( п, поэтому Ы ! т согласно уравнению (3!.4). Таким образом, т е (д). Обьединяя эти результаты, получаем (а) = (с1). Чтобы убедиться, что ~(а) ~ = = и/г1, заметим, что между числами О и и — 1 включительно, имеется ровно п/Й чисел, кратных И. И Следствие 31.21. Уравнение ах=Ь (шодп) разрешимо относительно неизвестной величины х тогда и только тогда, когда бей (а, и) ~ 6. Ю Следствие 31.22. Уравнение ах = — 6 (шог)п) либо имеет д = ась (а, п) различных решений по модулю п, либо не имеет решений вовсе. Доказательство. Если уравнение ах = Ь (шойи) имеет решение, то 6 Е (а).
Согласно теореме 31.17, огс1 (а) = ~(а) ~, поэтому из следствия 31.18 и теоремы 31.20 вытекает, что последовательность а1 шод п при г = 0,1,...,п — 1 периодична с периодом ((а)! = и/с(. Если 6 е (а) то Ь появляется в последовательности аг шоб и (1 = О, 1,..., и — 1) ровно д раз, поскольку при возрастании индекса 1 от О до п — 1 блок элементов подгруппы (а) длиной п/д. повторяется ровно И раз. Индексы х тех Ы позиций, для которых ах шой п = Ь, и являются решениями уравнения ах ив з Ь (шос1п). И Глава 31. Теоретико-числовые алгоритмы 977 Теорема 31.23.
Пусть с1 = ясс1 (а, п), и предположим, что равенство И = ах'+ + Ьу' выполняется для некоторых значений х' и у' (эти значения можно получить, например, с помощью процедуры ЕХтнчРЕо Еисми). Если с1 ~ Ь, то одно из решений уравнения ах = Ь (пюс1п) — значение хо = х' (Ь/с1) шос1 и. Даказалсельслсво. Справедлива цепочка равенств ахо = ах' (Ь/с1) (шос1п) — = с1 (Ь/с1) (пюс1п) — = Ь (тос1 п), где второе тождество следует из того, что ах' = с1(пюс1п), так что хо является решением уравнения ах = Ь (пюс1п). Теорема 31.24. Предположим, что уравнение ах аа Ь(пюс1п) имеет решение (т.е. с1 ! Ь, где с1 = ясс1 (а, и)), и что хо — некоторое решение этого уравнения. Тогда это уравнение имеет ровно И различных решений по модулю и, и эти решения выражаются соотношением х; = хо + 1 (и/с1) при 1 = О, 1,..., с1 — 1.
Доказательство. Поскольку п/с1 ) О, и О < г(п/с1) < п при 1 = 0,1,..., с1 — 1, все значениЯ последовательности хо,хы..., х4 ~ по модУлю п Различны. Поскольку хо — решение уравнения ах = Ь(шос)п), справедливо соотношение ахо шос1 п = Ь. Таким образом, при 1 = О, 1,..., с1 — 1 выполняются соотношения ах, пюс1 и = а (хо + 1п/с1) шос1 п = = (ахо + азп/с1) шос1 и = = ахо шос1 и = =Ь, где третье равенство следует из того, что с1 ~ а, поэтому все х; тоже являются решениями данного уравнения. В соответствии со следствием 31.22, всего имеется с1 различных решений, так что все рассматриваемые значения хо,хы..., х4 ~ должны быть таковыми. Теперь у нас имеется математический аппарат, необходимый для решения уравнения вида ах = Ь (шос1п), а ниже приведен алгоритм, который выводит все его решения.
На вход алгоритма подаются произвольные положительные целые числа а и п, и произвольное целое число Ь. Мооя.лк ?.ЕчеАк ЕОилтюм Босзсек(а, Ь, и) 1 (сз, х', у') — ЕХТЕХОЕ0 Ес3СЕ10(а, п) 2 11с1! Ь 3 гйеп хо — х'(Ь/с1) пюс1 п 4 1ог1 ~ — О го И вЂ” 1 5 с1о рйпс (хо + з(п/с1)) шос) п 6 е!зе рппс "Решений нет" 978 Часть Чпй Избранные темы В качестве примера работы этой процедуры рассмотрим уравнение 14х = = 30(шог1100) (здесь а = 14, Ь = 30 и п = 100). Взывав в строке 1 процедуру Ехткыоко Еосьш, получаем набор выходных данных (Ы,х,у) = (2,-7,1). Поскольку 2 ) 30, выполняются строки 3-5. В строке 3 вычисляется значение хо = (-7) (15) шос1 100 = 95.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
