Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 205

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 205)

2. Х = (1, 1,..., 1): последовательность Х состоит из одних единиц. В этом случае возвращается значение Рльзе; значение а не свидетельствует о том, что и — составное. 3. Х = (..., -1, 1,..., 1): последовательность Х оканчивается единицей, и последнее отличное от единицы значение равно — 1. В этом случае возвращается значение Елее; значение а не свидетельствует о том, что и — составное.

4. Х = (...,г1,1,...,1), где И ф х1: последовательность Х оканчивается единицей, но последнее отличное от единицы значение не равно — 1. В этом случае возвращается значение ткое; значение а свидетельствует о том, что и — составное, поскольку И вЂ” нетривиальный квадратный корень 1. Теперь рассмотрим тест Миллера-Рабина на простоту, основанный на применении процедуры %гпчезз.

Как и раньше, предполагается, что и — нечетное целое число, большее 2. М!1л.ее Клвпч(и, з) 1 Тогу' — 1 то а 2 Йо а — Клноом(1, и — 1) 3 11 %птчезз(а, и) 4 1пеп гетнгп Состлвное 5 ге1пгп ПРОСТОЕ [> Наверняка. ~> Почти наверняка. В процедуре Мн еек Клшн реализован вероятностный поиск доказательства того факта, что число и — составное. В основном цикле (который начинается в строке 1) выбирается а случайных значений величины а из множества г.+ (строка 2).

Если одно из этих значений свидетельствует о том, что число и — составное, то процедура Мп. ее Клвпч в строке 4 выдает значение Состлвное. Такой вывод всегда верный, согласно корректности процедуры %1ТНЕЗЗ для этого случая. Если в ходе а попыток не было таких свидетельств, то в процедуре М!ы.ее Клвпч предполагается, что нет причин считать число и составным, так что оно считается простым. Скоро можно будет убедиться, что при достаточно больших значениях а этот вывод правильный с высокой вероятностью, но тем не менее существует небольшая вероятность, что в процедуре могут неудачно выбираться значения а, и что существуют свидетельства того, что и — составное, хотя ни одно из них не было найдено.

Чтобы проиллюстрировать работу процедуры Мп.еек Клвпч, предположим, что и равно числу Кармайкла 561, так что и — 1 = 560 = 24 35. Из табл. 31.4 Часть Ч11. Избранные темы 1002 видно, что если выбрано значение а = 7, то в процедуре %ггнезз будет найдено значение хо = азв = 241 (пюд561), что даст нам последовательность Х = = (241, 289, 166, 67, 1). Таким образом, при последнем возведении в квадрат обнаружен нетривиальный корень из 1, поскольку азю ш 67 (шоди) и а~~~ =-1 (шос1и).

Таким образом, значение а = 7 свидетельствует о том, что число и — составное, процедура%!тнезЯ(7, и) возвращает значение ткое, а процедура Мп.1ек йлвпч— значение Состлвное. Если длина числа и равна 13 битов, то для выполнения процедуры Мп еек йлвпч требуется О (а 11) арифметических операций и О (з 13з) битовых операций, посюльку в асимптотическом пределе требуется выполнять не более з возведений в степень по модулю.

Частота ошибок в тесте Миллера-Рабина Если процедура Мй.~.ек Клвпч выводит значение Пеостое, то с небольшой вероятностью в ней может быть допущена ошибка. Однако, в отличие от процедуры РзеоооРк~ме, эта вероятность не зависит от и; другими словами, для этой процедуры не существует неблагоприятных входных данных. Зато вероятность ошибки в процедуре Мп.ьее Клвпч зависит от а и от того, насюлько удачно выбирались значения а. Кроме того, поскольку каждая проверка является более строгой, чем обычная проверка уравнения (31.38); исходя из общих принципов можно ожидать, что для случайно выбранных целых значений и частота ошибок должна быть очень небольшой.

Более точное обоснование представлено в сформулированной ниже теореме. Теорема 31.38. Если и — нечетное составное число, то количество свидетельств того, что и — составное, не меньше (и — 1)/2. Доказаюельсюаво. В ходе доказательства теоремы будет показано, что количество значений, не являющихся свидетельствами, не превышает (и — 1)/2, из чего следует справедливость теоремы. Начнем с утверждения, что любое значение, которое не является свидетельством, должно быть элементом множества 2„'. Почему? Рассмотрим такое значение а, не являющееся свидетельством. Оно должно удовлетворять соотношению а" ' — = 1(тос1и) или эквивалентному соотношению а . а" з = 1(шоби).

Таким образом, а" з является решением уравнения ах = 1(пюви). Согласно следствию 31.21, 8сй(а, и) ~ 1, из чего в свою очередь следует, что 8сг1 (а, и) = 1. Поэтому а является элементом множества Е„'; этому множеству принадлежат все значения оснований, не свидетельствующие о том, что число и — составное. Чтобы завершить доказательство, покажем, что все значения оснований, не свидетельствующие о том, что число и — составное, не просто содержатся в множестве Е„', но и находятся в истинной подгруппе В группы Е,",.

(Напомним, что В Глава 31. Теоретико-числовые алгоритмы 1003 называется истинной подгруппой группы Е„', если она является подгруппой Е*„, но не равна Е;,.) Согласно свойству 31.1б, выполняется неравенство (В( < )Е„')/2. Поскольку )Е„'! < и — 1, мы получаем неравенство (В) < (и — 1)/2.

Поэтому количество значений оснований, не являющихся свидетельствами, не превышает (и — 1)/2, следовательно, количество свидетельств не меньше (и — 1)/2. Теперь покажем, как найти истинную подгруппу В группы Е„', которая содержит все значения оснований, не являющиеся свидетельствами. Выделим два случая. Случай 1: существует значение х б Е;„такое что х" ~ ф1 (шос(и). Другими словами, и не является числом Кармайкла.

Поскольку, как мы уже знаем, числа Кармайкла встречаются крайне редко, то случай 1 — основной случай, который встречается "на практике" (т.е. тогда, когда число и выбрано случайным образом и производится проверка его простоты). Пусть В = (6 Е Е;,: 6" з = 1(шоди)). Очевидно, что множество В непустое, так как 1 е В. Поскольку группа В замкнута относительно операции умножения по модулю и, то из теоремы 31.14 следует, что  — подгруппа группы Е;,.

Заметим, что каждое значение а, которое не является свидетельством, принадлежит множеству В, поскольку такое а удовлетворяет соотношению а" ' = = 1 (шос1и). Поскольку х б Е„' — В, то  — истинная подгруппа группы Е„*. Случай 2: для каждого х Е Е,", выполняется соотношение х" з ь— а 1(шоби) (31.39) Другими словами, и — число Кармайкла. На практике этот случай встречается крайне редко.

Однако тест Мы.нк КАвпч (в отличие от теста на псевдопростоту), как сейчас будет показано, в состоянии эффективно определить, что число Кармайкла — составное. В этом случае число и не может быть степенью простого числа. Чтобы понять, почему это так, предположим обратное, т.е. что и = р', где р — простое, а е ) 1. Противоречие мы получим следующим образом. Поскольку предполагается, что и — нечетное, то число р также должно быть нечетным. Из теоремы 31.32 следует, что Е,*, — циклическая группа: она содержит генератор д, такой что огс(„(д) = ~Е„'~ = ф(и) = ре (1 — 1/р) = (р — Ц ра Согласно уравнению (3!.39), д" з = 1 (шог1и).

Тогда из теоремы о дискретном логарифме (теорема 31.33 при у = 0) следует, что и — 1 = 0 (шос1ф (и)) или (р — 1) р' з! р' — 1. При е ) 1 мы получаем противоречие, поскольку (р — 1) ре ~ делится на простое число р, а р' — 1 — нет. Таким образом, число и не является степенью простого числа. Часть Ч1!. Избранные темы 1004 Поскольку нечетное составное число п не является степенью простого, оно раскладывается на множители пгиз, где п~ и пз — взаимно простые нечетные числа, большие 1. (Таких разложений может быть несюлью; в этом случае не играет роли, каюе из них выбирается.

Например, если и = р" ,р~~' . р„'', то можно выбрать пг = р~' и пз = р" р" . р,'".) Напомним, что значения 1 и и связаны соотношением п — 1 = 2'и, гдето > 1, а и — нечетно, и что в процедуре %~тынзз для входного значения а вычисляется последовательность (все вычисления производятся по модулю и). Назовем пару (и, т) целых чисел приемлемой (ассерсаЫе), если и Е Е*„, 2Е(0,1,...>1) и ю " ю — 1 (шос1и) Для нечетных значений и приемлемые пары точно существуют; если выбрать е = п — 1 и з = О, то такая пара будет приемлемой. Теперь выберем наибольшее из возможных значений т', для которого существует приемлемая пара (е,2), и зафиксируем значение и.

Пусть В = (х Е Е„': х~ "— : х1(пюс1п)~ . Поскольку множество В замкнуто относительно операции умножения по модулю и, то оно является подгруппой группы Е„'. Поэтому, согласно следствию 31.16, ~В~ является делителем ~Е„'~. Каждое значение, которое не является свидетельством, должно быть элементом множества В, поскольку последовательность Х, образованная такими значениями, должна либо полностью состоять из единиц, либо содержать — 1 в позиции, расположенной не позже з-й, в соответствии с условием максимальности значения з. (Если пара (а,~') приемлемая, а значение а не является свидетельством, то из способа выбора значения у должно следовать неравенство уо < 2 ) Теперь воспользуемся фактом существования значения и, чтобы продемонстрировать, что существует элемент и е Е;, — В.

Характеристики

Список файлов книги