Алгоритмы - построение и анализ (1021735), страница 205
Текст из файла (страница 205)
В частности, х~ =а" г (шос1п). Однако этот цикл может закончиться раньше, если после очередного возведения в квадрат в строке 4 в строках 5-6 будет обнаружен нетривиальный квадратный юрень 1. В этом случае работа алгоритма завершается, и он возвращает значение тле. Это же значение возвращается и в строках 7-8, если значение, вычисленное из соотношения хг аа а" ~ (шодп), не равно 1. Это именно тот случай, когда процедура Рзеппогк|ме выдает сообщение СостАвное. Если в строках 6 или 8 не возвращается значение ТКиЕ, в строке 9 возвращается значение елгаве. Теперь покажем, что если процедура%гпчезз(а, п) возвращает значение тле, то с помощью величины а можно доказать, что число п — составное.
Если процедура %1тнезз(а, п) возвращает значение тле в строке 8, то она обнаружила, что справедливо соотношение х~ — — а" ~ щи п ф 1. Однако если число п — простое, то для всех а Е Е+ выполняется равенство а"— : 1 (шасси) согласно теореме Эйлера (теорема 31.31). Поэтому п не может быть простым, и неравенство а" ~ гпос1 п ф 1 служит доказательством этого факта. Если процедура %~тнезз(а, и) возвращает значение тле в строке 6, то она обнаружила, что значение х, г является нетривиальным квадратным корнем х, = = 1 по модулю п, поскольку выполняется соотношение х; 1 ~ х 1(тос1и), но х; = х8 1 = 1 (пюс1п).
В следствии 31.35 утверждается, что нетривиальный квадратный корень из 1 по модулю и может существовать лишь тогда, когда и— составное. Таким образом, тот факт, что х; 1 — нетривиальный квадратный корень из 1 по модулю п, доказывает, что п — составное. На этом доказательство корректности процедуры %гп езз завершено. Если при вызове процедуры %~тнезз(а, п) выдается значение ткОе, то и — гарантированно составное; доказательство этого факта легко провести, пользуясь значениями а и п. Сейчас будет представлено краткое альтернативное описание поведения алгоритма %1тнезз как функции от последовательности Х = (хо, хы..., хг). Это описание окажется полезным впоследствии при анализе эффективности работы проверки простоты Миллера-Рабина.
Заметим, что если при некоторых значениях 0 < 1 < т выполняется равенство х; = 1, то остальная часть последовательности в процедуре %1т~езз может не вычисляться. В таком случае все значения Глава 31. Теоретико-числовые алгоритмы 1001 х;+их;+з,..., х~ равны 1, и мы считаем, что в последовательности Х на этих позициях находятся единицы. Имеем четыре различных случая. 1.
Х = (...,д), где Н ф 1: последовательность Х не заканчивается единицей. В этом случае возвращается значение ткое; о том, что и — составное, свидетельствует значение а (согласно теореме Ферма). 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 — основной случай, который встречается "на практике" (т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
