Алгоритмы - построение и анализ (1021735), страница 204
Текст из файла (страница 204)
Теоретико-числовые алгоритмы 995 имел в распоряжении ее открытый ключ и смог проверить ее подпись. Поскольку ключ Алисы подписан источником Т, получатель убеждается, что ключ Алисы действительно принадлежит ей. Упражнения 31.7-1. Рассмотрим набор значений р = 11, д = 29, п = 312 и е = 3, образующих ключи в системе КБА. Какое значение Н следует использовать в секретном ключе? Как выглядит результат шифровки сообщения М = = 100? 31.7-2. Докажите, что если показатель степени е в открытом ключе Алисы равен 3, и если постороннему известен показатель степени Н секретного ключа Алисы, где 0 < д < ф (и), то он может разложить на множители входящее в состав ключа число и в течение времени, которое выражается полиномиальной функцией от количества битов в числе и.
(Читателю может быть интересен тот факт (хотя в упражнении не требуется его доказать), что этот результат остается истинным даже без условия е = 3. Дополнительные сведения можно почерпнуть из статьи Миллера (Мй1ег) [221].) *31.7-3. Докажите, что схема КБА является мультипликативной в том смысле, что Рд (М1) Рд (Мз) ив ь Рд (М1 Мг) (шодп) .
Докажите с помощью этого факта, что если злоумышленник располагает процедурой, способной эффективно расшифровать 1 процент зашифрованных с помощью ключа Рд сообщений из Е„, то он может воспользоваться вероятностным алгоритмом, чтобы с высокой степенью вероятности расшифровывать все сообщения, зашифрованные с помощью ключа Рд. * 31.8 Проверка простоты В этом разделе рассматривается задача поиска больших простых чисел. Начнем с того, что обсудим плотность распределения простых чисел на числовой оси, после чего перейдем к исследованию правдоподобного (но неполного) подхода к проверке простоты чисел. Затем будет представлен эффективный рандомизированный тест простоты, предложенный Миллером (М(Нег) и Рабином (КИЬ1п). Часть ЧП. Избранные темы Плотность распределения простых чисел Во многих приложениях (например, в криптографии) возникает необходимость поиска больших "случайных" простых чисел.
К счастью, большие простые числа встречаются достаточно часто, поэтому для поиска простого числа путем проверки случайных целых чисел соответствующего размера потребуется не так уж много времени. Функции распределения простых чисел (ргппе йз1г1Ьаюп Йпсбоп) я(п) определяется как количество простых чисел, не превышающих числа и.
Например, я (10) = 4, поскольку количество простых чисел, не превышающих 10, равно 4 (зто числа 2, 3, 5 и 7). В теореме о распределении простых чисел приводится полезное приближение функции я (и). Теорема 31.37 (Теорема о простых числах). 11гп = 1. к (п) о п/1пп Приближенная оценка и/1пп дает достаточно точную оценку функции я (и) даже при малых и. Например, при п = 10в, когда я (и) = 50847534, а и/1п и = - 48254942, отклонение не превышает 6%. (Для специалиста в области теории чисел 10з — число небольшое.) С помощью теоремы о простых числах вероятность того, что случайным образом выбранное число и окажется простым, можно оценить как 1/1пп. Таким образом, чтобы найти простое число, длина которого совпадает с длиной числа и, понадобится проверить приблизительно 1пп целых чисел, выбрав их случайным образом в окрестности числа и.
Например, чтобы найти 512-битовое простое число, понадобится перебрать приблизительно 1п 2ыз = 355 случайным образом выбранных 512-битовых чисел, проверяя их простоту. (Ограничившись только нечетными числами, это количество можно уменьшить в два раза.) В оставшейся части этого раздела рассматривается задача по определению того, является ли простым большое целое число и. Для удобства обозначений предположим, что разложение числа п на простые множители имеет вид (31.37) где т > 1, ры рз,...,р„— простые множители числа и, а ем ез,..., е„— положительные целые числа. Конечно же, число п является простым тогда и только тогда, когда т = 1 и е1 = 1.
Одним из элементарных подходов к задаче проверки на простоту является пробное деление (нба! 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
