Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 223
Текст из файла (страница 223)
Теперь докажем, что если процедура %1тНЕЗЗ(а,п) возвращает значение ткие, то с помощью величины а можно доказать, что число и — составное. Если процедура %батыеве(а, и) возвращает значение ткпе в строке 8, значит, она обнаружила, что справедливо соотношение хз = а" ' щи п ~ 1. Однако если число п — простое, то согласно теореме Ферма (теорема 31.31) для всех а 6 Ц выполняется равенство а" ' ьв 1( (щи и)). Поэтому п не может быть простым, и неравенство а" ~ шод п нб 1 доказывает этот факт. Если процедура 1И~тыезе(а, п) возвращает в строке 6 значение тите, значит, она обнаружила, что значение ач з является нетривиальным квадратным корнем 1 по модулю п, поскольку выполняется соотношение хз, р1 ~1 (шоб п), но при этом хч ев хз,: — 1 (шод зз). В следствии 3!.35 утверждается, что нетривиальный квадратный корень из 1 по модулю и может существовать лишь тогда, когда и — составное.
Таким образом, тот факт, что ач з — нетривиальный квадратный корень из 1 по модулю и, доказывает, что и — составное. На этом доказательство корректности процедуры ЖтЫЕЗЕ завершено. Если при вызове процедуры %1тыеее(а, п) выдается значение ткие (в строке 6 или 8), то и — гарантированно составное; доказательство этого факта легко провести, пользуясь значениями а и п. Сейчас будет представлено краткое альтернативное описание поведения алгоритма %зтмеез как функции от последовательности Х = (хо, хм..., хз).
Зто описание окажется полезным впоследствии, в ходе анализа эффективности работы проверки простоты Миллера-Рабина. Заметим, что если при неюторых значениях 0 < з < ~ выполняется равенство яч = 1, то остальная часть последовательности в процедуре %1тыеез может не вычисляться. В таком случае все значения х;.ьы я,.ьз,..., яз равны 1, и мы считаем, что в последовательности Х на этих позициях находятся единицы. Имеем четыре различных случая. 1. Х = (..., д), где з1 Ф 1: последовательность Х не заканчивается единицей. В строке 8 возвращается значение ткие; а является свидетельством того, что и — составное (согласно теореме Ферма). 2.
Х = (1, 1,...,1): последовательность Х состоит из одних единиц. Возвращается значение ГАЕБЕ; а не является свидетельством того, что и — составное. 3, Х = (..., — 1, 1,..., 1): последовательность Х заканчивается единицей, и последний элемент последовательности, не равный 1, — элемент — 1. Возвращается значение ЕАЕБЕ; а не является свидетельством того, что п — составное. 10!5 Глава ль Теоретико-числовые алгоритмы 4. Х = (..., 4(, 1,...,1), где Н ~ ~1: последовательность Х заканчивается единицей, но последний элемент последовательности, не равный 1, не равен и -1. В строке б возвращается значение ткое; а является свидетельством того, что и — составное, поскольку д является нетривиальным квадратным корнем 1.
Теперь рассмотрим тест Миллера — Рабина на простоту, основанный на применении процедуры %1т1ЧЕЗЗ. Как и раньше, предполагается, что и — нечетное целое число, большее 2. Мпл.ек-Клвпч (и, в) 1 Тог3' ее !то в 2 а = Кл14оом(1,п — 1) 3 Ы%1тыезз(а, и) 4 гетпгп состлвное // Определенно 5 гетцгп ПРОСТОЕ // Почти гарантированно Процедура М1ееек-Клв114 представляет собой вероятностный поиск доказательства того факта, что число и — составное. В основном цикле (который начинается в строке !) выбирается в случайных значений величины а из множества У,„+ (строка 2). Если одно нз этих значений свидетельствует о том, что число и— составное, то процедура М1ееек-Клв1ы в строке 4 выдает значение состлвное. Такой вывод всегда верный согласно корректности процедуры %1714езз для этого случая.
Если в ходе в попыток не было таких свидетельств, то в процедуре М1ЕЕЕК-КЛВП4 предполагается, что нет причин считать число и составным, так что оно считается простым. Скоро можно будет убедиться, что при достаточно большйх значениях з этот вывод правильный с высокой вероятностью. Тем не менее все же имеется небольшая вероятность, что в процедуре могут неудачно выбираться значения а и что существуют свидетельства того, что п — составное, хотя ни одно из них не было найдено. Чтобы проиллюстрировать работу процедуры М1ееек-Клвпч, предположим, что п равно числу Кармайкла 561, так что и — 1 = 560 = 24 35, 1 = 4 и и = 35.
Если выбрано значение а = 7, то из рис. 31.4 в разделе 31.6 видно, что процедура %1т1чезз вычислит хо = азь = 241 (шос! 561), что даст нам последовательность Х = (241, 298, 166, 67, 1). Таким образом, при последнем возведении в квадрат обнаружен нетривиальный корень из 1, поскольку а~~~ = 67 (глод и) и аьао = — 1 (шос! и). Итак, значение а = 7 свидетельствует о том, что число и — составное, процедура %1тыезз(7, и) возвращает значение ткое, а процедура М!ееекКлв1н — значение состлвное.
Если длина числа п равна Д бит, то для выполнения процедуры М1ееек-Клв1ы требуется 0(а13) арифметических операций и 0(з,Зз) битовых операций, поскольку в асимптотическом пределе требуется выполнять не более е возведений в степень по модулю. Частота ошибок в тесте Миллера-Рабина Если процедура М1еьек-Клв114 выводит значение пгостое, то с небольшой вероятностью в ней может быть допущена ошибка. Однако, в отличие от проце- 1016 Часть Г?1. Избранные темы дуры Рзецвогк1ме, эта вероятность не зависит от и; другими словами, для этой процедуры не существует неблагоприятных входных данных.
Зато вероятность ошибки в процедуре М1еьек-Клв1м зависит от величины б и от того, насколько удачно выбирались значения а. Кроме того, поскольку каждая проверка является более строгой, чем обычная проверка уравнения (31.40), исходя из общих принципов, можно ожидать, что для случайно выбранных целых значений и частота ошибок должна быть очень небольшой. Более точное обоснование представлено в сформулированной ниже теореме. Теорема 31.38 Если и является нечетным составным числом, то количество свидетельств того, что оно составное, — не менее (и — 1)/2.
Доказоозельсозоо. В ходе доказательства теоремы будет показано, что количество значений, не являющихся свидетельствами, не превышает (и — 1)/2, из чего следует справедливость теоремы. Начнем с утверждения, что любое значение, которое не является свидетельством, должно быть элементом множества Ж„*. Почему? Рассмотрим произвольное значение а, не являющееся свидетельством. Оно должно удовлетворять соотношению а" 1 = 1 (шос( и) или эквивалентному соотношению а а" з = 1 (пюс) и). Таким образом, уравнение ах = 1 (пюд и) имеет решение, а именно— а" з.
Согласно следствию 31.21 ясг((а, и) ~ 1, из чего, в свою очередь, следует, что ясд(а, и) = 1. Поэтому а является элементом множества У,„', этому множеству принадлежат все значения оснований, не свидетельствующие о том, что число и— составное. Чтобы завершить доказательство, покажем, что все значения оснований, не свидетельствующие о том, что число и — составное, не просто содержатся в множестве Щ, но и находятся в истинной подгруппе В группы Ж„. (Напомним, что В называется исньинной подгруппой группы У,„', если она является подзруппой Ж„*, но не равна л,„'.) Согласно следствию 31.16 в этом случае мы имеем ~В! ( Щ(/2.
Поскольку (Щ( ( и — 1, получаем неравенсгво ~В! < (и — 1)/2. Поэтому количество значений оснований, не являющихся свидетельствами, не превышает (и — 1)/2, следовательно, количество свидетельств должно быть не меньше (и — 1)/2. Теперь покажем, как найти истинную подгруппу В группы У,„', которая содержит все значения оснований, не являющиеся свидетельствами. Выделим два случая.
Случай 1. Существует значение х е Ж„', такое, что х" ф 1 (пюе) и) . Другими словами, и не является числом Кармайкла. Поскольку, как мы уже знаем, числа Кармайкла встречаются крайне редко, случай 1 — основной случай, встречающийся ана практике" (т.е. тогда, когда число и выбрано случайным образом и выполняется проверка его простоты). 70!7 Глава 31. Теоретико-числовые алгоритмы Пусть В = (Ъ е а,„*: Ъа ' = 1 (пюс1 п)). Ясно, что множество В непустое, так как 1 Е В.
Поскольку группа В замкнута относительно операции умножения по модулю и, из теоремы 31.14 следует, что  — подгруппа группы а.„'. Заметим, что каждое значение а, которое не является свидетельством, принадлежит множеству В, поскольку такое а удовлетворяет соотношению а" ~ =— 1 (шос( и). Поскольку х е Е„' — В, В является истинной подгруппой группы е о. Случай 2. Для всех х Е К*„ х" = 1 (шос1 и) (31.41) Другими словами, п — число Кармайкла. На практике этот случай встречается крайне редко. Однако тест Ми.ьек-Кявпч (в отличие от теста на псевдопростоту), как сейчас будет показано, в состоянии эффективно определить, что число Кармайкла — составное.
В этом случае число и не может быть степенью простого числа. Чтобы понять, почему это так, предположим обратное, т.е. что и = р', где Р— простое, а е > 1. Противоречие мы получим следующим образом. Поскольку предполагается, что п — нечетное, то число р также должно быть нечетным. Из теоремы 31.32 следует, что а,„' — циклическая группа: она содержит генератор д, такой, что огс1„(д) = ~У*„~ = ф(п) = Р'(1 — 1гср) = (р — 1)р' л.
(Формула для ф(п) получена из (31.20).) Согласно уравнению (31.41) имеем д" ' = 1 (шос) п). Тогда из теоремы о дискретном логарифме (теорема 31.33 при у = 0) следует, что п — 1 вя 0 (шос( ф(п)), или При е > 1 мы получаем противоречие, поскольку (Р— 1)р' ' делится на простое число р, а р' — 1 — не делится. Таким образом, число п не является степенью простого числа. Поскольку нечетное составное число и не является степенью простого, оно раскладывается на множители плит, где ис и пз — взаимно простые нечетные числа, большие единицы. (Таких разложений может быть несколько; в этом случае не играет роли, какое из них выбирается. Например, если и = р"р~' р,', то можно выбрать пс = Р~' и пз = Рз Рз' ' ' Р~ ) Напомним, что значения 1 и и определены так, что и — 1 = 2'и, где 1 > 1, а и — нечетно, и что в процедуре %1тмезз для входного значения а вычисляется последовательность Х = (а",аз",аз ",...,а ") (все вычисления проводятся по модулю и).