Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 224
Текст из файла (страница 224)
Назовем пару (о, 7) целых чисел приемлемой (ассерсзЪ|е), если и Е а'„', д Е (0,1,...,1) и зги Приемлемые пары точно существуют, поскольку и нечетно; если выбрать о = и — 1 и д = О, то такая пара (п — 1, 0) будет приемлемой. Теперь выберем наибольшее из возможных значений 7', для которого существует приемлемая пара Часть И1 Избранные тены /018 (и, з), и зафиксируем значение о.
Пусть В = (х Е е.*„: х~ " = ~1 (шос) п)) Поскольку множество В замкнуто относительно операции умножения по модулю п, оно является подгруппой группы Ж„. Поэтому согласно теореме 31.15 ~В~ является делителем ~Ж'„~. Каждое значение, которое не является свидетельством, должно быть элементом множества В, поскольку последовательность Х, образованная такими значениями, должна либо полностью состоять из единиц, либо содержать — 1 не позже чем в у-й позиции в соответствии с условием максимальности значения з1 (Если пара (а, за) приемлемая, а значение а не является свидетельством, то из способа выбора значения з должно следовать неравенство У <З1) Теперь воспользуемся фактом существования значения о, чтобы продемонстрировать, что существует элемент ю е е'.„— В, а следовательно, что В является истинной подгруппой Ж„'.
Поскольку оз'" = — 1 (шос) п), из следствия 31.29 китайской теоремы об остатках вытекает, что из'н = — 1 (шос1 пс). Согласно следствию 31.28 существует значение ю, которое одновременно удовлетворяет таким уравнениям: ю ив з о (гпос1 пс), ю = 1 (шос) пз) . Следовательно, ю "— = — 1 (шос) пз), ю — = 1 (шос1 пз) . Согласно следствию 31.29 из соотношения юз' ф 1 (шос) пз) следует юззн ~ 1 (шос) и), а из юззн ~ — 1 (шос) пз) вытекает ю~з" 91 — 1 (щос) п). Следовательно, можно сделать вывод, что юз " ф ~1 (шос1 п), так что ю ф В. Остается показать, что ю б е,„'. Для этого построим рассуждения отдельно по модулю пз и по модулю пз. Что касается операций по модулю пн заметим, что, поскольку о е е'„*, справедливо равенство асс)(о,п) = 1, так что и кос)(зз, пз) = 1; если у числа о нет общих делителей с п, то у него также нет общих делителей с пь Поскольку ю = е (гпос1 пс), можно сделать выжщ, что ксс1(ю, пс) = 1.
Что же касается операций по модулю пз, заметим, что из соотношения ю = 1 (шос1 пз) следует, что кос)(ю,пз) = 1. Для того, чтобы объединить эти результаты, воспользуемся теоремой 31.6„из которой следует, что кос((ю, пспз) = ксс1(ю, и) = 1, т.е. ю е е.„". Следовательно, ю б К*„— В, и мы приходим к выводу, что в случае 2 В является истинной подгруппой е'*„. Итак, мы убедились, что в обоих случаях количество свидетельств того, что число и — составное, не меньше (п — 1)/2. !019 Глава ЗЛ Теоретико-числовые алгоритмы Теорема 31.39 При любом нечетном и ) 2 и положительном целом в вероятность того, что процедура Мпл.вк-Клвпч(и,в) вьщаст неправильный результат, не превышает 2 '.
Даказалеельсзааа. Из теоремы 31.38 следует, что если и — составное, то при каждом выполнении цикла Тог в строках 1-4 вероятность обнаружить свидетельство х того, что и — составное, не меньше 1/2. Процедура М1ы.вк-Клвпч допускает ошибку только в том случае, если ей не удалось обнаружить такое свидетельство в каждой из в итераций основного цикла. Вероятность подобной последовательности неудач не превышает 2 '.
Если и — простое, то процедура Мп.ьвк-Клв1гч всегда будет сообщать простое, а если и — составное, то вероятность того, что процедура Мп.свк-Клв11ч сообщит П9ОСтОВ, не превышает 2 '. Однако при применении процедуры М!саек-Клвпч к большому случайно выбранному целому числу и необходимо оценить вероятность того, что и — простое, чтобы корректно интерпретировать результаты работы процедуры Мйл.вкКлвпч. Предположим, что мы фиксируем битовую длину )3 и случайным образом выбираем число и длиной Д бит для проверки на простоту. Обозначим через А событие, заключающееся в том, что и — простое число.
В соответствии с теоремой о простых числах (теорема 31.37) вероятность того, что и — простое, приближенно равна Рг (А) — 1/ 1и и 1.443/,3 . Пусть теперь В означает событие, что процедура Мп.ьвк-Клинч вернула простоя. Мы имеем Рг(В ! А) = 0 (нли, что эквивалентно, Рг(В ~ А) = 1) и Рг (В ! А) < 2 ' (или, что эквивалентно, Рг (В ) А) ) 1 — 2 '). Но чему равно Рг(А ~ В), вероятность того, что и — простое, если процедура Мп ввк-Клвпч вернула значение простов? Согласно альтернативной форме теоремы Байеса (уравнение (В.18)) имеем Рг (А) Рг (В ) А) Рг(А) Рг(В / А) + Рг (А) Рг (В / А) 1 1+ 2 '(1пи — 1) Эта вероятность не превышает 1/2, пока в не превысит 18(1пи — 1).
Интуитивно ясно, что большое количество испытаний нужно только для того, чтобы преодолеть недоверие к результату, возникающее из возможной неспособности найти свидетельство того, что число и — составное, прн том что составных чисел существенно больше, чем простых. Для чисел длиной )3 = 1024 бит это количество гвгО Часть сгг Избранные темы составляет около !8(!и и — 1) !8()3/1.443) 9 испытаний.
В любом случае выбор а = 50 должен быть достаточен для любого мыслимого приложения. В действительности ситуация намного лучше. Если пытаться искать большие целые числа, применяя процедуру Мп.ькк-КАв1м к большим случайным образом выбранным нечетным целым числам, то выбор небольшого значения з (скажем, 3) приведет к ошибочному результату с очень малой вероятностью, хотя здесь мы и не будем это доказывать. Причина заключается в том, что для случайным образом выбранного составного нечетного целого числа и ожидаемое количество оснований, не являющихся свидетельствами того, что и составное, оказывается гораздо меньшим, чем (и — 1)/2. Однако если число и выбирается не случайным образом, то лучшее, что можно доказать с помощью улучшенной версии теоремы 31.38, — это то, что количество значений оснований, не являющихся свидетельствами, не превышает (и — 1)/4. Более того, существуют такие целые числа и, для которых это количество равно (и — 1)/4.
Упражнения 31.8.1 Докажите, что если целое нечетное число и > 1 не является простым числом или степенью простого числа, то существует нетривиальный квадратный корень из 1 по модулю и. 31.8.г * Теорему Эйлера можно слегка усилить, придав ей следующий вид: а !"1: — 1 (щи и) для всех а 6 У,„* где и = р" ,..
° р,'" и Л(и) определено как Л(и) = !сш(ф(р1'),...,ф(р„'")) . (3! .42) Докажите, что Л(и) ~ ф(и). Составное число и является числом Кармайкла, если Л(и) ~ и — 1. Наименьшее из чисел Кармайкла равно 561 = 3 11 17; при этом Л(и) = !сгп(2, 10, 16) = 80, а зто делитель 560. Докажите, что числа Кармайкла должны быть "свободными от квадратов" (т.е. не должны делиться на квадрат ни одного простого числа) и в то же время представлять собой произведение не менее трех простых чисел. (По этой причине они встречаются не очень часто.) 31.8.3 Докажите, что если х является нетривиальным квадратным корнем 1 по модулю и, то и 8сб(х — 1, и), и 8се!(х + 1, и) являются нетривиальными делителями и.
102! елово 31. Теоремиео-числовые олгориесиы * 31.9. Целочисленное разложение Предположим, что задано целое число и, которое нужно разлоогсилеь (тастот) на простые множители. Тест простоты, представленный в предыдущем разделе, может дать информацию о том, что число и — составное, однако он не говорит о его простых множителях. Разложение больших целых чисел и представляется намного более сложной задачей, чем определение того, является ли число и простым или составным.
Располагая суперкомпьютерами и наилучшими на сегодняшний день алгоритмами, нереально разложить на множители произвольное 1024-битовое число. Эвристический р-метод Полларда Пробное деление на каждое целое число вплоть до П гарантирует, что будет полностью разложено любое число вплоть до Лз. Представленная ниже процедура позволяет разложить любое число вплоть до В4 (если только нам не будет хронически не везти), выполнив тот же объем работы. Поскольку эта процедура носит лишь эвристический характер, ничего нельзя утверждать наверняка ни о времени ее работы, ни о том, что она действительно достигнет успеха. Несмотря на это, данная процедура оказывается весьма эффективной на практике.
Другое преимущество процедуры РО11АКО-КНО состоит в том, что в ней используется лишь фиксированное количество памяти. (Для небольших чисел ее легко реализовать даже на программируемом калькуляторе.) РОееАкп-КнО(и) 1 1=1 2 х1 = КАИНОМ(О,и — 1) 3 у=хз 4 )4=2 5 лтЬ~!е ткпн 6 1=!+! 7 х; = (х4 т — 1) шое! и 8 с( = код(у — х,,и) 9 Гс(ф1идфи 10 рппт И !1 Ы(==й 12 у=х; 13 к = 2)с Эта процедура работает следующим образом. Строки 1 и 2 инициализируют 4 единицей, а х1 — случайно выбранным из У,„значением. Цикл теййе, начинающийся в строке 5, продолжается до бесконечности в поисках множителей числа и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
