Алгоритмы - построение и анализ (1021735), страница 206
Текст из файла (страница 206)
тогда, когда число и выбрано случайным образом и производится проверка его простоты). Пусть В = (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 ) Теперь воспользуемся фактом существования значения и, чтобы продемонстрировать, что существует элемент и е Е;, — В. Поскольку пз'" = — 1 (шос(и), из следствия 31.29 из китайской теоремы об остатках вытекает„что пз" ш = — 1(шос1иг). Согласно следствию 31.28, существует значение со, которое одновременно удовлетворяет таким уравнениям: и = и (гпос1пг), со = 1(шос1пз).
Глава 31. Теоретико-числовые алгоритмы 1005 Поэтому се~ "= — 1 (пюс(п1), иР "= 1(пюс1из). Согласно следствию 31.29, из соотношения саз " ф1 (пюс(пг) следует, что саз'" ф ф1(пюс1п), а из соотношения се~'" ~ — 1(шос)пз) — что са~'" ф'= — 1(пюс1п). Таким образом, иР'" ф ~ 1 (пюс1п), поэтому са ф В. Остается показать, что са е 2;,. Для этого построим рассуждения отдельно по модулю п1 и по модулю из. Что касается операций по модулю пм заметим, что поскольку о Е У„', справедливо равенство 8сс)(и,п) = 1, так что и 8сс((о,п1) = 1; если у числа е нет общих делителей с п, то у него также нет общих делителей с пп Поскольку са ив з е(пюс1п1), можно сделать вывод, что 8сс1(щ,п1) = 1. Что же касается операций по модулю пз, заметим, что из соотношения и = 1 (шос1из) следует, что 8сс1 (са, пз) = 1. Для того чтобы объединить эти результаты, воспользуемся теоремой 31.6, из которой следует, что 8сс1(ю,и|из) = бсс1(са,и) = 1, т.е.
и Е Х;,. Следовательно, ю ЕЕ„'-В, и мы приходим к выводу, что в случае 2 В является истинной подгруппой 2„'. Итак, мы убедились, что в обоих случаях количество свидетельств того, что число п — составное, не меньше (п — 1)/2. И Теорема 31.39. При любом нечетном п ) 2 и положительном целом в вероятность того, что процедура Мцл.нн КАвпч(п, в) выдаст неправильный результат, не превышает 2 '.
Доказансыьснсво. Из теоремы 31.38 следует, что если п — составное, то при каждом выполнении цикла 1ог в строках 1-4, вероятность обнаружить свидетельство х того, что и — составное, не меньше 1/2. Процедура Мшьнк Клинч допускает ошибку только в том случае, когда ей не удалось обнаружить такое свидетельство в каждой из в итераций основного цикла. Вероятность подобной последовательности неудач не превышает 2 '.
й Таким образом, если выбрать в = 50, то этого должно хватить почти для любого приложения, какое только можно себе представить. Если поиск больших простых чисел производится путем применения процедуры Мп.енк КАнлч к случайно выбранным большим целым числам, то можно показать (хотя мы не станем здесь этого делать), что выбор небольшого значения в (скажем, 3) с очень малой вероятностью приведет к ошибочным результатам. Другими словами, для случайным образом выбранного нечетного составного целого числа п математическое ожидание количества значений оснований, не являющихся свидетельствами того, 1006 Часть ЧП.
Избранные темы что и — составное, с большой вероятностью намного меньше (и — 1)/2. Однако если число п выбирается не случайным образом, самое лучшее, что можно доказать с помощью улучшенной версии теоремы 31.38, — что количество значений оснований, не являющихся свидетельствами, не превышает (и — 1)/4.
Более того, существуют такие целые числа п, для которых это количество равно (и — 1)/4. Упражнения 31.8-1. Докажите, что если целое нечетное число и > 1 не является простым числом или степенью простого числа, то существует нетривиальный квадратный корень из 1 по модулю и. * 31.8-2. Теорему Эйлера можно слегка усилить, придав ей такой вид: а 00 се 1(шос1п) для всех аЕ Щ, где п = р"р" р~", а функция Л (и) определена как Л(п) = 1ст(ф(рг~'),...,ф(р~')) .
(31.40) Докажите, что Л(и) ~ ф(п). Составное число п является числом Кармайкла, если Л (и) ~ и — 1. Наименьшее из чисел Кармайкла равно 661 = = 3 11 17; при этом Л(п) = 1сш(2,10,16) = 80, а это делитель 560. Докажите, что числа Кармайкла должны быть "свободными от квадратов" (т.е. не делиться на квадрат ни одного простого числа) и в то же время представлять собой произведение не менее трех простых чисел. По этой причине они встречаются не очень часто. 31.8-3. Докажите, что если х — нетривиальный квадратный корень из единицы по модулю и, то и бсг1 (х — 1, и), и бсс1 (х + 1, и) являются нетривиальными делителями и.
* 31.9 Целочисленное разложение Предположим, задано целое число и, которое нужно разложить (Гас1ог) на простые множители. Тест простоты, представленный в предыдущем разделе, может дать информацию о том, что число п — составное„однако он обычно не выводит его простых множителей. Разложение больших целых чисел п представляется намного более сложной задачей, чем определение того, является ли число п простым или составным.
Располагая суперкомпьютерами и наилучшими на сегодняшний день алгоритмами, нереально разложить произвольное 1024-битовое число. Глава 31. Теоретико-числовые алгоритмы 1007 Эвристический р-метод Полларда РОы.Акп Кно(п) 1 з — 1 2 х1 < — КАХООМ(0, и — 1) 3 у — х1 4 й -2 5 иЫ1е ТЛЕ 6 де( -1+1 7 х; — (хз — 1) щог) п 8 г( — бсг1(у — х;, п) 9 Идф1идфп 10 1йеп рппг г( 11 Ыг=й 12 гйепу -х; 13 7с — 27г Опишем работу этой процедуры.
В строках 1-2 переменной 1 присваивается начальное значение 1, а переменной х1 — случайное значение из Е„. Итерации цикла и Ьйе, который начинается в строке 5, продолжаются до бесконечности в поисках множителей числа п. При каждой итерации этого цикла в строке 7 используется рекуррентное соотношение х; — (хз, — 1) щодп, (31.41) позволяющее получить очередное значение х; бесконечной последовательности (31.42) хмхз, хз,..., а соответствующее значение индекса 1 увеличивается в строке 6. Несмотря на то, что для простоты восприятия в коде используются значения переменных с индексами х;, программа работает точно так же, если мы опустим все индексы, Пробное деление на каждое целое число вплоть до В гарантирует, что будет полностью разложено любое число вплоть до Вз.
Представленная ниже процедура позволяет разложить любое число вплоть до В4 (еслн мы не окажемся неудачниками), выполнив тот же объем работы. Поскольку эта процедура носит лишь эвристический характер, ничего нельзя утверждать наверняка ни о времени ее работы, ни о том, что она действительно достигнет успеха. Несмотря на это„ данная процедура оказывается очень эффективной на практике. Другое преимущество процедуры РОгл.Акп КнО состоит в том„что в ней используется лишь фиксированное количество памяти. (Для небольших чисел ее легко реализовать даже на программируемом калькуляторе.) 1008 Часть ЧП. Избранные темы поскольку при каждой итерации необходимо поддерживать толью одно последнее значение х;. С учетом этой модификации в процедуре используется лишь фиксированное количество ячеек памяти. Время от времени программа сохраняет самые последние из сгенерированных значений х; в переменной у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
