Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 222
Текст из файла (страница 222)
Согласно (В.32), ожидаемое количество испытаний примерно равно !и п. Таким образом, чтобы найти простое число, длина которого совпадает с длиной числа и, понадобится проверить приблизительно !пп целых чисел, выбрав их случайным образом в окрестности числа ть, Например, следует ожидать, что, чтобы найти 1024-битовое простое число, понадобится перебрать приблизительно !и 2'бз4 — 710 случайным образом выбранных 1024-битовых чисел, проверяя их простоту. (Конечно же, ограничившись толью нечетными числами, это количество можно уменьшить в два раза.) В оставшейся части этого раздела рассматривается задача определения того, является ли простым большое целое нечетное число и. Для удобства обозначений предположим, что разложение числа п на простые множители имеет вид (31.39) где т ) 1, ры рз,...,р„— простые множители числа и, а ем ез,..., е„— положительные целые числа.
Целое число и является простым тогда н только тогда, когда т = 1ие1 =1. Одним из элементарных подходов к задаче проверки на простоту является нробное деление (пйа! Йч(з!оп). При этом предпринимается попытка нацело разделить и на все целые числа 2,3,..., ~ь/п~. (Здесь также можно опустить все четные числа, большие 2.) Легко понять, что число и простое тогда и только !О!! Глава 3!. Теоретило-ииеловые алгоритмы тогда, когда оно не делится ни на один из пробных множителей.
Если предположить, что для обработки каждого пробного делителя требуется фиксированное время, то в худшем случае время решения задачи при таком подходе будет равно 9(ь/й), а это означает, что оно выражается экспоненциальной функцией от длины числа и. (Напомним, что если бинарное представление числа и имеет длину !3, то Д = (1й(и + 1)1, поэтому,/й = св(2а!з).) Таким образом, пробное деление хорошо работает только при условии, что число и очень мало илн если окажется, что у него есть маленький простой делитель. Преимущество этого метода заключается в том, что он не только позволяет определить, является ли число и простым, но и находит один из его простых делителей, если оно составное.
В этом разделе нас будет интересовать только факт, является ли заданное число и простым; если оно составное, мы не станем искать его простые множители. Как будет показано в разделе 31.9, разложение чисел на простые множители вычислительными средствами — вычислительно весьма дорогостоящая операция.
Возможно, вам покажется странным, что намного легче определить, является ли заданное число и простым, чем разложить составное число на простые множители. Проверка псевдопростых чисел Рассмотрим "почти работающий" метод проверки простых чисел, который оказывается вполне пригодным для многих практических приложений. Позже будет представлена усовершенствованная версия этого метода, устраняющая его небольшой дефект.
Обозначим через Ц ненулевые элементы множества е,„: Х+ = (1,2,...,и — 1) Если и — простое, то Е„+ = е,„". Будем говорить, что число и всевдоиросюое ло основанию а (Базе-а рзецдорпше), если оно составное и а":— 1 (шос) и) (31.40) Из теоремы Ферма (теорема 3!.31) следует, что если и — простое, то оно удовлетворяет уравнению (31.40) для каждого элемента а множества К~. Таким образом, если удается найти какой-нибудь элемент а Е л.+, такой, что и не удовлетворяет уравнению (31.40), то и — определенно составное. Удивительно, что обратное утверждение ночюи справедливо, поэтому этот критерий является почти идеальным тестом на простоту. Мы проверяем, удовлетворяет ли число и уравнению (31.40) при а = 2.
Если это не так, то можно сделать вывод, что и— составное. В противном случае можно выдвинуть гипотезу, что и — простое (в то время как фактически известно лишь то, что оно либо простое, либо псевдопростое по основанию 2). Приведенная ниже процедура проверяет число и на простоту описанным способом. В ней используется процедура Мопцьлк-Ехронент!Атюн, описанная в разделе 31.б. Предполагается, что входное значение и — нечетное целое число, большее 2.
1012 Часть Л1. Избранаые теьт Рве!лэОРд1ме(п) 1 Ы Мо!з!Л.лк-Ехро!черт!Ат!ОХ(2, и — 1, и) Ф 1 (шос! Л) 2 гегпгп состлвнон // Гарантированно 3 е1зе гегнгп пгостоя // Будем надеяться! Эта процедура может допускать ошибки, но только одного типа. Если процедура говорит, что и — составное, то это всегда верно. Если же она утверждает, что ив простое, то это заключение ошибочно только тогда, когда и — псевдопростое ло основанию 2.
Как часто эта процедура допускает ошибки? На удивление редко, Всего имеется лишь 22 значения и, меньших 10000, для которых ответ будет неправильным. Первые четыре таких значения равны 341, 561, 654 и 1105. Можно показать, что вероятность того, что в этой процедуре будет допущена ошибка для случайно выбранного 13-битового числа, стремится к нулю при 13 -+ оо. Воспользовавшись результатами статьи Померанца (Рошегапсе) [277], содержащей более точную оценку количества псевдопростых чисел фиксированного размера по основанию 2, можно заключить, что случайным образом выбранное 612-битовое число, названное приведенной выше процедурой простым, окажется псевдопростым по основанию 2 менее чем в одном случае из 10зо, а случайным образом выбранное 1024-битовое число, названное простым, окажется псевдопростым по основанию 2 менее чем в одном случае из 104е. Поэтому, если вы просто ищете большое простое число для каких-то приложений, для всех практических целей почти никогда не возникнет ошибки, если большие числа подбираются случайным образом до тех пор, пока для одного из них процедура Рзнппогк!Мн выдаст результат пгосток.
Но если числа, которые проверяются на простоту, подбираются не случайным образом, необходим более качественный тест. Как вы увидите, немного сообразительности и рандомизации позволят создать программу проверки простых чисел, которая будет хорошо работать для любых входных данных. К сожалению, мы ие можем устранить все ошибки, просто проверив выполнение (31.40) для другого основания, скажем, для а = 3, поскольку существуют составные числа и, удовлетворяющие уравнению (31.40) для всех а е У,*„. Этн числа известны как числа Ка1аееайкла (Сапп!сЬае! пшпЬегз).
(Заметим, что уравнение (3!.40) не выполняется, когда ксд(а, и) > 1 — т.е. когда а ф Е*„, — но продемонстрировать путем поиска соответствующего а, что и — составное число, может оказаться очень трудно, если и делится толью на большие простые числа.) Первые три числа Кармайкла — 561, ! !05 и 1729. Числа Кармайкла встречаются крайне редко, например имеется всего 255 таких чисел, меньших 100000000.
Понять, почему эти числа так редко встречаются, поможет упр. 31.8.2. В следующем подразделе будет показано, как улучшить тест простоты таким образом, чтобы в нем не возникали ошибки из-за чисел Кармайкла. Раидомнзнрованный тест простоты Миллера-Рабина Тест простоты Миллера — Рабина позволяет решить проблемы, возникающие в простом тесте Рзлипогк!Мн. Этого удается достичь за счет двух модификаций, описанных ниже. Т0!3 Глава 3!. Теоретико-числовые алгоривслсы В этом тесте выполняется проверка не одного, а нескольких случайным обра- зом выбранных значений а. В процессе вычисления каждой степени по модулю в тесте проверяется, не обнаружен ли нетривиальный квадратный корень из 1 по модулю и в ходе последней серии возведений в квадрат.
Если это так, то процедура останавливает свою работу и выдает сообщение состАЕпоЕ. Правильность выявления составных чисел таким способом подтверждается следствием 31.35 из раздела 31.6. Ниже приведен псевдокод теста простоты Миллера — Рабина. На его вход подаются проверяемое нечетное число и > 2 и значение в — количество случайным образом выбранных значений из множества К„+, относительно которых проверяется простота. В этом коде используется генератор случайных чисел КАьспом, описанный на с.
!43: процедура КАсчсэом(1,и — 1) возвращает случайное целое число, удовлетворяющее неравенству 1 < а < и — 1. В коде используется вспомогательная процедура %сткезз. Процедура %!Тсчезз(а, и) выдает значение тКСЗЕ тогда и только тогда, когда значение а "свидетельствует" о том, что число и составное, т.е. если с помощью а можно доказать (способом, который станет понятен через некоторое время), что и — составное. Проверка %!тссезз(а, и)— это более эффективное обобщение теста Рзес3сэоексме, основанного на проверке соотношения а" ф 1 (шос( и) при а = 2. Сначала представим и обоснуем схему работы процедуры %!тсчеез, а затем покажем, как она используется в тесте простоты Миллера-Рабина.
Пусть и — 1 = 2си, где 1 > 1, а и — нечетное; т.е. бинарное представление значения и — 1 имеет вид бинарного представления нечетного числа и, после которого слеи Зс дует ровно 1 нулей. Таким образом, выполняется соотношение а" 1 = (а")з (пюс( и), поэтому можно вычислить величину а" сшос) и, сначала вычислив значение а" гаос1 и, а затем 1 раз последовательно возведя результат в квадрат. %!ТЬСЕЗЗ(а, и) 1 Пусть 1 и и — такие, что 1 > 1, и нечетно н и — 1 = 2са 2 хо = Мопс3еАк-Ехгомент!Ат!оьс(а, и, и) 3 1ог с = 1 го 1 4 хс =хе пюс1и 5 11хс ==1 и хс 1 ф 1 и хс 1 ф и — 1 6 ге1пгп ткссе 7 !$хс Ф 1 8 ге1пгп ткее 9 гегнгп ЕАЕБЕ В псевдокоде процедуры %стмезз вычисляется величина а" ~ пюд и. Для этого сначала в строке 2 вычисляется значение хо = а" шос( и, а затем результат последовательно 1 раз возводится в квадрат в цикле 1ог в строках 3-6.
! О!4 Часть етз' Избранные тены Применив индукцию по з, можно сделать вывод, что последовательность вычисленных значений хо, хы..., хз удовлетворяет уравнению ач = о~" (шоп' и) при з = О, 1,..., ~, так что, в частности, хз = а" ' (шоб п). Однаю этот цикл может закончиться раньше, если после очередного возведения в квадрат в строке 4 в строках 5 и 6 будет обнаружен нетривиальный квадратный корень из 1, В этом случае работа алгоритма завершается, и он возвращает значение тите. Зто же значение возвращается и в строках 7 и 8, если значение, вычисленное для хз ав а" (шой и), не равно 1. Зто именно тот случай, когда процедура Рееипоркгме выдает сообщение состАвное. Если в строке 6 или 8 не возвращается значение типе, в строке 9 возвращается значение ЕАезе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
