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

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

Файл №1123758 Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.)) 204 страницаТ. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758) страница 2042019-05-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Одним из элементарных подходов к задаче проверки на простоту является пробное деление (нба! 41ч1з(оп). При этом предпринимается попытка нацело разделить п на все целые числа 2, 3,..., ~~/й~. (Здесь также можно опустить четные числа, большие 2.) Легко понять, что число п простое тогда и только тогда, когда оно не делится ни на один из пробных множителей. Если предположить, что Глава 31. Теоретико-числовые алгоритмы 997 для обработки каждого пробного делителя требуется фиксированное время, то в худшем случае время решения задачи при таком подходе будет равно О (~/й), а это означает, что оно выражается экспоненциальной функцией от длины числа и.

(Напомним, что если бинарное представление числа п имеет длину,9, то 13 = ~18 (и+ 1)1, поэтому,/й = 9 (2д~з).) Таким образом, пробное деление хорошо работает толью при условии, что число и очень мало, или если окажется, что у него есть маленький простой делитель. Преимушество этого метода заключается в том, что он не только позволяет определить, является ли число и простым, но и находит один из его простых делителей, если оно составное. В этом разделе нас будет интересовать только тот факт, является ли заданное число и простым; если оно составное, мы не станем искать его простые множители. Как будет показано в разделе 31.9, разложение чисел на простые множители вычислительными средствами — дорогостоящая операция. Возможно, может показаться странным, что намного легче определить, является ли заданное число п простым, чем разложить на простые множители составное число.

Проверка псевдопростых чисел Рассмотрим "почти работающий" метод проверки простых чисел, который оказывается вполне пригодным для многих практических приложений. Позже будет представлена усовершенствованная версия этого метода, устраняющая его небольшой дефект. Обозначим через Е+ ненулевые элементы множества Е„: Е~~ = (1,2,..., — 1). Если п — простое, то Е„+ = Е;,. Говорят, что число п псевдонростое по основанию а (Ьазе-а рзецборпше), если оно составное и а" = 1 (шос1п) . (31.38) Из теоремы Ферма (теорема 31.31) следует, что если п — простое, то оно удовлетворяет уравнению (31.38) для каждого элемента а множества Е+.

Таким образом, если удается найти какой-нибудь элемент а Е Е+, при котором п не удовлетворят уравнению (31.38), то и — определенно составное. Удивительно, что почти справедливо обратное утверждение, поэтому этот критерий является почти идеальным тестом на простоту. Мы проверяем, удовлетворяет ли число и уравнению (31.38) при а = 2. Если зто не так, то делается вывод, что п — составное.

В противном случае можно выдвинуть гипотезу, что и — простое (в то время как фактически известно лишь то, что оно либо простое, либо псевдопростое по основанию 2). Приведенная ниже процедура проверяет число и на простоту описанным способом. В ней используется процедура Мопглык Ехромнчт1Атюи, описанная в разделе 31.6. Предполагается, что входное значение п — нечетное целое число, большее 2. 998 Часть Ч!!. Избранные темы Рзе««ООРЕ«ме(и) 1 1«МОО«««.Ак ЕхРО«че«чт«Ат«О«4(2, и — 1, и) ~! (п«о«! и) 2 тйеп ге«пгп СОстАвнОе «> Определенно 3 е1$е гепдгв ПРОСТОЕ «> Предположительно Эта процедура может допускать ошибки, но только одного типа.

Если процедура говорит, что и — составное, то это всегда верно. Если же она утверждает, что и— простое, то зто заключение ошибочно только тогда, когда и — псевдопростое по основанию 2. Как часто процедура допускает ошибки? На удивление редко. Всего имеется лишь 22 значения и, меньших 10000, для которых ответ будет неправильным. Первые четыре таких значения равны 341, 561, 654 и 1105. Можно показать, что вероятность того, что в этой процедуре будет допущена ошибка для случайно выбранного «3-битового числа, стремится к нулю при «3 — оо. Воспользовавшись результатами статьи Померанца (Рошегапсе) 1244), содержащей более точную оценку количества псевдопростых чисел фиксированного размера по основанию 2, можно заключить, что случайным образом выбранное 512-битовое число, названное приведенной выше процедурой простым, окажется псевдопростым по основанию 2 в менее чем одном случае из 10зо, а случайным образом выбранное 1024-битовое число, названное простым, окажется псевдопростым по основанию 2 в менее чем одном случае из 104'.

Поэтому если достаточно найти большое простое число для каких-то приложений, то для всех практических целей почти никогда не возникнет ошибки, если большие числа подбираются случайным образом до тех пор, пока для одного из них процедура Рве««ООРЕ«ме выдаст результат ПРОстОе. Но если числа, которые проверяются на простоту, подбираются не случайным образом, необходим более качественный тест. Как станет ясно через некоторое время, немного сообразительности и рандомизация позволят создать программу проверки простых чисел, которая будет хорошо работать для любых входных данных.

К сожалению, путем проверки уравнения (31.38) не удается полностью исключить все ошибки, возникающие из-за псевдопростых чисел по другим основаниям, например, при а = 3, поскольку существуют составные числа и, удовлетворяющие уравнению (31.38) при всех а Е Е„*. Эти числа известны как числа Кал«майкла (СапшсЬае! пшпЬегз). Первые три числа Кармайкла — 561, 1105 и 1729.

Числа Кармайкла встречаются крайне редко, например, имеется всего 255 таких чисел, меньших 100000000. Понять, почему зти числа так редко встречаются, поможет упражнение 3!.8-2. В следующем подразделе будет показано, как улучшить тест простоты таким образом, чтобы в нем не возникали ошибки из-за чисел Кармайкла. Глава 31. Теоретико-числовые алгоритмы 999 Рандомизированный тест простоты Миллера-Рабина Тест простоты Миллера-Рабина позволяет решить проблемы, возникающие в простом тесте РзеУг10Рк1ме.

Этого удается достичь за счет двух модификаций, описанных ниже. ° В этом тесте производится проверка не одного, а нескольких случайным образом выбранных значений а. ° В процессе вычисления каждой степени по модулю в тесте проверяется, обнаружен ли нетривиальный квадратный корень из 1 по модулю и в ходе последней серии возведений в квадрат. Если это так, то процедура останавливает свою работу и выдает сообщение СостАвное. Правильность выявления составных чисел таким способом подтверждается следствием 31.35. Ниже приведен псевдокод теста простоты Миллера-Рабина. На его вход подается проверяемое нечетное число и > 2 и значение в, — количество случайным образом выбранных значений из множества Е+, относительно которых проверяется простота.

В этом коде используется генератор случайных чисел йлхоом, описанный в главе 5: процедура КА1ч1эом(1, и — 1) возвращает случайное целое число, удовлетворяющее неравенству 1 < а < и — 1. В коде используется вспомогательная процедура %1т1чезз. Процедура %гпжзз(а, и) выдает значение тк11е тогда и только тогда, когда значение а "свидетельствует" о том, что число и составное, т.е. если с помощью а можно доказать (способом, который станет понятен через некоторое время), что т1 — составное. Тест %1т1чезз(а, и) — это более эффективное обобщение теста Рзе1дзОКК1ые, основанного на проверке соотношения а" 1ф1(то11п) при а = 2.

Сначала представим и обоснуем схему работы процедуры %1т1чезз, а затем покажем, как она используется в тесте простоты Миллера-Рабина. Пусть и — 1 = 21и, где Ф > 1, а и — нечетное; т.е. бинарное представление значения и — 1 имеет вид бинарного представления нечетного числа и, после которого следует ровно т нулей. Таким образом, выполняется соотношение а" 1 = (а")~ (шо1)п), поэтому чтобы вычислить величину а" 1 шод и, можно сначала вычислить величину а" шос1 и, а затем последовательно возвести ее в квадрат 1 раз. йГ1ТХЕЗБ(а, и) 1 Пусть и — 1 = 21и, где ~ > 1 и и — нечетное 2 хо — Могз~.Ак Ехео1чеыт1Ат10ы(а, и, и) 3 1огг' — 11о1 4 оох1+ — х9 1шодп 5 Н хз = 1 и х; 1 ф 1 и хг 1 ~ г1 — 1 6 01еп гетпгп тКиЕ 1000 Часть ЧП. Избранные темы 7 1гхг~1 8 Феп гегпгп ТЛЕ 9 геГпгп ГАЕРЕ В псевдоюде процедуры %1тнезз вычисляется величина а" ~ гпос1п.

Для этого сначала в строке 2 вычисляется значение хо = а" шос1п, а затем результат последовательно т раз возводится в квадрат в цикле 1ог в строках 3-6. Применив индукцию по г, можно сделать вывод, что последовательность вычисленных значений хо,хы, ..,хг удовлетворяет уравнению х;: — аз "(шог1п) при1 = 0,1,...,1. В частности, х~ =а" г (шос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: последовательность Х не заканчивается единицей. В этом случае возвращается значение ткое; о том, что и — составное, свидетельствует значение а (согласно теореме Ферма).

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

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

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6559
Авторов
на СтудИзбе
299
Средний доход
с одного платного файла
Обучение Подробнее