В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 11. Простые числа 90 , . . . , 96 все числа являются составными. Программа никогда не должна “зависнуть”, невзирая на то, что было подано ей на вход, поэтому ограничим количество попыток и сгенерируем ошибку в случае, если это количество бу- дет превышено. Как уже отмечалось, в окружении числа u примерно одно из каждых 0 , 7 · log 2 u чисел является простым. (Функция log 2 — это лога- рифм по основанию 2. Для простоты ее можно определить следующим об- разом: log 2 ( x ) := ln x/ ln 2) . Подсчитать число log 2 u довольно сложно, а вот b log 2 u c + 1 намного проще: это количество бит, необходимое для того, чтобы представить u в виде двоичного числа. Таким образом, если длина числа u равна 2017 бит, тогда b log 2 u c + 1 = 2017 . Множитель 100 гарантирует, что мы с большой вероятностью найдем простое число. Для достаточно больших интервалов вероятность того, что простое число не будет найдено, составляет менее 2 − 128 , поэтому ею можно пренебречь. В то же время наличие данного ограничения гарантирует, что выполнение функции GenerateLargePrime когда-нибудь завершится. В этом примере мы весьма небрежно использова- ли утверждения assert для генерации ошибки; реальная программа должна выдать ошибку с объяснениями того, что было сделано неправильно. Основной цикл алгоритма очень прост. Проверив, не исчерпано ли чис- ло попыток, мы выбираем случайное число и с помощью функции isPrime выясняем, не является ли оно простым. Убедитесь, что полученное число n действительно выбрано равноверо- ятным случайным образом из диапазона l, . . . , u . Кроме того, если простое число необходимо сохранить в секрете, интервал l, . . . , u должен быть доста- точно большим. Если злоумышленник знает, какой интервал вы используете, и этот интервал содержит менее 2 128 простых чисел, он потенциально сможет перебрать их все. При желании вы можете гарантировать, что сгенерированное случайное число является нечетным, установив наименее значимый бит только что сге- нерированного числа n . Поскольку число 2 не находится в заданном интер- вале, изменение бита никак не повлияет на вероятностное распределение вы- бираемых вами простых чисел, зато наполовину сократит число попыток, которые вам пришлось бы осуществить для обнаружения простого числа. К сожалению, данная операция допустима только в том случае, если u яв- ляется нечетным. В противном случае установка наименее значимого бита может выбросить n за пределы допустимого диапазона. Функция isPrime — это фильтр, состоящий из двух этапов. Первый этап — это простой тест, в котором мы пытаемся проверить делимость n на все малые простые числа. Это позволит быстро откинуть множество составных чисел, которые делятся на малые простые числа. Если же такие делители не бу- дут найдены, в ход пойдет “тяжелая артиллерия” — тест Рабина–Миллера (Rabin–Miller). 11.4. Большие простые числа 223 функция isPrime вход: n Целое число ≥ 3 . выход: b Булево значение, указывающее, является ли n простым чис- лом. assert n ≥ 3 for p ∈ { все простые числа ≤ 1000 } do if p является делителем n then return p = n fi od return Rabin-Miller ( n ) Если у вас нет желания генерировать малые простые числа, можете немно- го схитрить. Вместо того чтобы проверять делимость на все простые числа, вы можете проверять делимость на 2 и все нечетные числа 3 , 5 , 7 , . . . , 999 в по- рядке возрастания последних. Эта последовательность содержит все простые числа до 1000, а также множество не интересующих нас составных чисел. Порядок использования чисел по возрастанию важен для того, чтобы малое составное число наподобие 9 было правильно распознано как составное. Гра- ница 1000 выбрана произвольным образом и может быть изменена в целях оптимизации производительности. Все, что нам остается, — это рассмотреть тот самый таинственный тест Рабина–Миллера, который выполняет всю тяжелую работу. 11.4.1 Проверка того, является ли число простым Оказывается, проверить, является ли число простым, невероятно легко (по крайней мере по сравнению с разложением числа на множители и по- иском его простых делителей). К сожалению, подобные “легкие” алгоритмы далеко не совершенны. Все они определяют простые числа с некоторой до- лей вероятности. Существует определенный риск получить неверный ответ. Повторяя одну и ту же проверку несколько раз, мы можем сократить веро- ятность ошибки до приемлемого уровня. Для проверки того, является ли число простым, будем использовать тест Рабина–Миллера. Математическое обоснование этого теста выходит за рамки нашей книги, хотя его структура довольно проста. Цель теста — определить, является ли нечетное число n простым. Мы выбираем случайное число a , меньшее n (число a называется базисом (basis) ), и проверяем наличие опре- деленного свойства a по модулю n , которое выполняется всегда, когда n яв- ляется простым числом. Тем не менее мы можем доказать, что, даже если n не является простым числом, это свойство будет выполняться максимум |