Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
O(50(uur2y2 + yjrh)) = 0(rhuuyj) = 0(rhuueks) = 0(т\г/s)r/aeka).
Мы найдем теперь у — или, что равносильно, s, — для которого эта оценка минимальна. Так как число г бит в записи п фиксированно, это означает минимизацию (r/s)r^seks по s, или, что эквивалентно,
§ 3. ФАКТОРИЗАЦИЯ ФЕРМА И ФАКТОРНЫЕ БАЗЫ
171
минимизацию его логарифма, который равен ~ log ^ + ks. Для этого мы полагаем
d / V V \ V / т \ т т
° = Ts KS10Z-S+4= ~7 rg~s+ l)+*«-7log- + *,
т.е. мы выбираем 5 так, чтобы ks было примерно равно ~ log другими словами, чтобы два сомножителя в (r/s)r^seks были примерно равны между собой. Так как к — константа, из последнего приближенного равенства следует, что порядки s2 и г log (г / s) = г (log г - logs) одинаковы; поэтому 5 имеет порядок величины между у/г и т log г. Значит, logs близок к |logr. Делая подстановку logs « ^ log г, мы приводим полученное выше соотношение к виду
г г
О «--T:\ogr+к или s«W—г log г.
2s V 2&
Оценим теперь время работы при этом значении s. Так как при оптимальном выборе s множители (r/s)r/,s и ек" приблизительно равны по величине, то временная оценка упрощается: 0(е2 3) =
0(ev^v'r'og г). Заменяя константу V^k на С, мы, наконец, приходим к следующей оценке числа двоичных операций, затраченных на факторизацию r-разрядного двоичного числа п: 0(eC^rXogг).
Приведенные выше выкладки не являются строгими. Мы не пытались обосновывать наши упрощения или оценивать погрешности в приближенных равенствах. К тому же как сам алгоритм, так и наша оценка времени его работы — вероятностные.
До последнего времени, пока не был изобретен метод решета в числовом поле (см. замечание в конце § 5), все оценки времени работы самых лучших универсальных алгоритмов факторизации имели вид
0(eC^rlog r). В некоторых случаях оценки доказывались строго, а в иных — основывались на правдоподобных, но не доказанных предположениях. Оценки для различных алгоритмов различались, в основном, константой С в показателе. В этом отношении история задачи факторизации совершенно не похожа на историю рассмотренных в § 1 критериев простоты, где улучшение временных оценок (в особенности в детерминистических тестах на простоту) было прямо-таки поразительным. Подробный обзор и сравнение методов факторизации, которые были известны к началу 80-х гг., имеется в статье Померанца (Ротегапсе) 1982 г., указанной в приводимом ниже списке литературы.
172
гл. v. простота и факторизация
Замечание. Так как г = O(logn), приведенную выше временную оценку можно выразить в виде
Time (Разложить n) = o{eCy/lo*nlo*lo*n).
За исключением метода решета в числовых полях, эвристические оценки времени работы всех асимптотически быстрых универсальных факторизационных алгоритмов имеет указанный выше вид при C = 1 + є, где ? произвольно мало.
Применения к RSA. Напомним, что надежность криптосистемы с открытым ключом RSA (см. § IV. 2) основана на том, что разложение на множители очень большого числа п вида п = pq требует значительно больших затрат времени, чем действия, которые должны выполнять законные пользователи системы и сложность которых (как при проверке простоты) является полиномиальной или почти полиномиальной функцией от числа г бит в п. Мы только что видели, почему при анализе факторизационных алгоритмов часто возникают временные оценки вида 0(еС rlogr)- Хак как полиномиальную функцию от г можно записать в виде 0(eC]ogr), то для больших г время, затрачиваемое на факторизацию, много больше времени работы полиномиальных или почти полиномиальных алгоритмов. (Однако факториза-
ционные алгоритмы с временной оценкой 0(еС г1°6Г) для больших г лучше, чем ро-метод, временная оценка которого — приблизительно O(v^) = 0{еСг), где С = ilog2.)/'~X
Наконец, отметим, что вопрос о замене y/r log г в показателе меньшей функцией от г — это не единственный вопрос, имеющий практическое значение при оценке надежности системы RSA. В конце концов, полиномиальная функция от числа г бит становится значительно
меньшей, чем CieC2^r]ogT, лишь когда г велико, а насколько велики такие значения г, в сильной степени зависит от констант С\ и C2- Поэтому даже построение алгоритма факторизации с той же временной оценкой, но с меньшими константами, повлияло бы на оценку надежности системы RSA с открытым ключом.
УПРАЖНЕНИЯ
1. Использовать факторизацию Ферма, чтобы разложить на множители: а) 8633; б) 809009; в) 92296873; г) 88169891; д) 4061.
2. Показать, что если делитель числа п отстоит от \/п не более, чем на у/п, то факторизация Ферма дает результат при первой попытке (т.е. для t =
3. а) Доказать, что обобщенная факторизация Ферма не позволяет найти делитель большого нечетного числа га, если выбрано к = 2 или если к — любое целое число, делящееся на 2, но не на 4.
§ 3. ФАКТОРИЗАЦИЯ ФЕРМА И ФАКТОРНЫЕ БАЗЫ
173
б) Доказать, что если к = 4 и если обобщенная факторизация Ферма работает для некоторого I, то и «простая» (с А: = 1) факторизация Ферма работает столь же хорошо.
