Квадратные корни по модулю п

V V

_е(1.923 + 0(1))(1п(п))Л(1п((1п(и)))/з

В 1970 году большой новостью стало разложение на множители 41-разрядного трудного числа [1123]. ("Трудным" является такое число, у которого нет маленьких множителей, и которое не обладает специальной формой, позволяющей упростить процесс.) Десять лет спустя разложение в два раз более длинного числа заняло лишь несколько часов на компьютере Cray [440].

В 1988 году Карл Померанс (Carl Pomerance), используя обычные СБИС, спроектировал устройство для ра з-ложения на множители [1259]. Размер числа, которое можно было разложить, зависел только от размеров ус т-ройства, которое так и не было построено.

В 1993 году с помощью квадратичного решета было разложено на множители 120-разрядное трудное число. Расчет, потребовавший 825 mips-лет, был выполнен за три месяца реального времени [463]. Другие результаты приведены в [504].

Сегодня для разложения на множители используются компьютерные сети [302, 955]. Для разложения 116_разрядного числа Аржат Ленстра (Arjen Lenstra) и Марк Манасс (Mark Manasse) в течение нескольких м е-сяцев использовали свободное время массива компьютеров, разбросанных по всему миру, - 400 mips-лет.

В марте 1994 года с помощью двойной вариации множественного полиномиального QS [66] командой м а-тематиков под руководством Ленстры было разложено на множители 129-разрядное (428-битовое) число. В ы-числения выполнялись добровольцами в Internet - в течение восьми месяцев трудились 600 человек и 1600 ко м-пьютеров, возможно, самый большой в истории многопроцессорный конгломерат. Трудоемкость вычислений была в диапазоне от 4000 до 6000 mips-лет. Компьютеры соединялись по электронной почте, передавая свои результаты в центральное хранилище, где выполнялся окончательный анализ. В этих вычислениях использов а-лись QS и теория пятилетней давности, NFS мог бы ускорить выполнение расчетов раз в десять [949]. В соо т-ветствии с [66]: "Мы делаем вывод, что широко используемые 512-битовые модули RSA могут быть вскрыты организацией, готовой потратить несколько миллионов долларов и подождать несколько месяцев." По оценкам авторов разложение 512-битового числа в 100 раз более трудоемко при использовании той же техники и только в 10 сложнее при использовании NFS и современной техники [949].

С целью развития искусства разложения на множители RSA Data Security, Inc. в марте 1991 года объявило о

программе RSA Factoring Challenge (состязание RSA по разложению на множители) [532]. Состязание состоит в разложении на множители ряда трудных чисел, каждое из которых является произведением двух простых чисел примерно одинакового размера. Каждое простое число было выбрано конгруэнтным 2 по модулю 3. Всего было предложено 42 числа, по одному числу в диапазоне от 100 до 500 разрядов с шагом 10 разрядов (плюс одно д о-полнительное, 129-разрядное число). К моменту написания этой книги RSA-100, RSA-110, RSA-120, и RSA-129 были разложены на множители, все с помощью QS. Следующим (с помощью NFS) может быть RSA-130, или чемпионы по разложению на множители сразу возьмутся за RSA -140.

Данная область развивается быстро. Технику разложения на множители трудно экстраполировать, так как невозможно предсказать развитие математической теории. До открытия NFS многие считали, что любой метод разложения на множители не может асимптотически быть быстрее QS. Они были неправы.

Предстоящее развитие NFS, по видимому, будет происходить в форме уменьшения константы: 1.923. Для ряда чисел специальной формы, таких как числа Ферма, константа приближается к 1.5 [955, 954]. Если бы для трудных чисел, используемых в сегодняшней криптографии, константу тоже можно было снизить до этого уровня, то 1024-битовые числа раскладывались бы на множители уже сегодня. Одним из способов уменьшить константу является обнаружение лучших способов представления чисел как полиномов с маленькими коэфф и-циентами. Пока еще проблема не изучалась достаточно эффективно, но возможно решающий успех уже близок [949].

Последние результаты программы RSA Factoring Challenge можно узнать, отправив запрос по электронной почте по адресу [email protected].

Если п - произведение двух простых чисел, то возможность вычислить квадратные корни по модулю п вы­числительно эквивалентна возможности разложить число п на множители [1283, 35, 36, 193]. Другими словами, тот, кто знает простые множители числа п, может легко вычислить квадратные корни любого числа по модулю и, но для любого другого вычисление окажется таким же трудным, как и разложение на простые множители числа п.

11.5 Генерация простого числа

Для алгоритмов с открытыми ключами нужны простые числа. Их нужно множество для любой достаточно большой сети. Прежде, чем обсуждать математику генерации простого числа, я отвечу на несколько очевидных вопросов.

Если каждому понадобится свое простое число, не иссякнет ли у нас запас? Нет. В действительности сущее т-вует приблизительно 10151 простых чисел длино1 до 512 бит включительно. Для чисел, близких и, вероятность того, что случайно выбранное число окажется простым, равна 1/1п п. Поэтому полное число простых чисел, меньших п, равно я/(1п п). Во вселенной всего 10⁷⁷ атомов. Если бы для каждого атома во вселенной с начала времен каждую микросекунду требовался бы миллиард простых чисел, понадобилось бы только 10 ¹⁰⁹ простых чисел, осталось бы еще примерно 10 ^ш простых чисел.

Что если два человека случайно выберут одно и то же простое число? Этого не случится. При выборе из 10151 простых чисел вероятность совпадения выбора значительно меньше, чем вероятность, что ваш компь ю-тер случайно вспыхнет в тот самый момент, когда вы выиграете в лотерею.

Если кто-то создаст базу данных всех простых чисел, не сможет ли он использовать эту базу данных для вскрытия алгоритмов с открытыми ключами? Нет. Если бы вы хранили один гигабайт информации на устро й-стве, весящем один грамм, то перечень простых чисел размером до 512 бит включительно весил бы столько, что масса хранилища превысила бы предел Чандрасекара, и оно сколлапсировало бы в черную дыру... в любом случае вы не сможете извлечь данные.

Но если так трудоемко разложение на множители, как может быть простой генерация простых чисел? Фокус в том, что ответить "да" или "нет" на вопрос "Является ли число п простым?" гораздо проще, чем ответить на более сложный вопрос "Каковы множители и?"

Генерация случайных чисел с последующей попыткой разложения их на множители - это неправильный сп о-соб поиска простых чисел. Существуют различные вероятностные проверки на простоту чисел, определяющие, является ли число простым, с заданной степенью достоверности. При условии, что эта "степень достоверности" достаточна велика, такие способы проверки достаточно хороши. Я слышал, что простые числа, генерированные таким образом называются "промышленно простыми числами": эти числа вероятно являются простыми с ко н-тролируемой возможностью ошибки.

Предположим, что одна проверка из 2⁵⁰ - ошибочна. Это означает, что с вероятностью 1/10 ¹⁵ проверка объя­вит простым составное число. (Простое число никогда не будет объявлено составным при проверке.) Если по

какой-то причине понадобится большая достоверность простоты числа, уровень ошибки можно понизить. С другой стороны, если вы установите вероятность того, что число является составным, в 300 миллионов раз меньшей, чем вероятность выиграть главный приз в государственной лотерее, вы можете больше об этом не волноваться.

Обзоры недавних исследований в этой области можно найти в [1256, 206]. Другими важными работами я в-ляются [1490, 384, И, 19, 626, 651, 911].

Дата добавления: 2014-11-29