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

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

Solovay-Strassen

Роберт Соловэй (Robert Solovay) и Фолькер Штрассен (Volker Strassen) разработали алгоритм вероятностной проверки простоты числа [1490]. Для проверки простоты числа p этот алгоритм использует символ Якоби:

(1)Выберите случайно число a, меньшее p.

(2)Если НОДр) (1, то p не проходит проверку и является составным.

(3)Вычислите j = a(p-1)/2 mod p

(4)Вычислите символ Якоби J( a,p).

(5)Если j Ф J(a,p), то число p наверняка не является простым.

(6)Если j = J(a,p), то вероятность того, что число p не является простым, не больше 50 процентов.

Число a, которое не показывает, что p наверняка не является простым числом, называется свидетелем. Если p - составное число, вероятность случайного числа a быть свидетелем не ниже 50 процентов. Повторите эту проверку t раз с t различными значениями a. Вероятность того, что составное число преодолеет все t проверок, не превышает 1/2t.

Lehmann

Другой, более простой тест был независимо разработан Леманном (Lehmann) [903]. Вот последовательность действий при проверке простоты числа p:

(1)Выберите случайно число a, меньшее p.

(2)Вычислите a(p-1)/2 mod p

(3)Если a(p-1)/2 Ф 1 или -1 (mod p), то p не является простым.

(4)Если a(p-1)/2 = 1 или -1 (mod p), то вероятность того, что число p не является простым, не больше 50 процентов.

И снова, вероятность того, что случайное число a будет свидетелем составной природы числа p, не меньше 50 процентов. Повторите эту проверку t раз. Если результат вычислений равен 1 или -1, но не всегда равен 1, то p является простым числом с вероятностью ошибки 1/2t.

Rabin-Miller

Повсеместно используемым является простой алгоритм, разработанный Майклом Рабином (Michael Rabin), частично основанным на идеях Гэри Миллера [1093, 1284]. По сути, это упрощенная версия алгоритма, рек о-мендованного в предложении DSS proposal [1149, 1154].

Выберите для проверки случайное число p Вычислите b - число делений p - 1 на 2 (т.е., 2b - это наибольшая степень числа 2, на которое делится p - 1). Затем вычислите m, такое что p = 1 + 2b * m.

(1)Выберите случайное число a, меньшее p.

(2)Установите j = 0 и z = am mod p

(3)Если z = 1 или если z = p - 1, то p проходит проверку и может быть простым числом.

(4)Если j > 0 и z = 1, то p не является простым числом.

(5)Установите j = j + 1. Если j < b и z( p - 1, установите z = z2 mod p и вернитесь на этап (4). Если z = p - 1, то p проходит проверку и может быть простым числом.

(6)Если j = b и z Ф p - 1, то p не является простым числом.

В этом тесте вероятность прохождения проверки составным числом убывает быстрее, чем в предыдущих. Гарантируется, что три четверти возможных значений a окажутся свидетелями. Это означает, что составное число проскользнет через t проверок с вероятностью не большей (1/4)t, где t - это число итераций. На самом деле и эти оценки слишком пессимистичны. Для большинства случайных чисел около 99.9 процентов возмо ж-

ных значений a являются свидетелями [96].

Существуют более точные оценки [417]. Для n-битового кандидата в простые числа (где n больше 100), вероятность ошибки в одном тесте меньше, чем 4n2(/2) . И для 256-битового n вероятность ошибки в шести тестах меньше, чем 1/251. Дополнительную теорию можно найти в [418].

Практические соображения

В реальных приложениях генерация простых чисел происходит быстро.

(1)Сгенерируйте случайное n-битовое число p

(2)Установите старший и младший биты равными 1. (Старший бит гарантирует требуемую длину простого числа, а младший бит обеспечивает его нечетность.)

(3)Убедитесь, что p не делится на небольшие простые числа: 3, 5, 7, 11, и т.д. Во многих реализациях пров е-ряется делимость p на все простые числа, меньшие 256. Наиболее эффективной является проверка на д е-лимость для всех простых чисел, меньших 2000 [949]. Это может быть эффективно выполнено с помощью колеса [863].

(4)Выполните тест Rabin-Miller для некоторого случайного a. Если p проходит тест, сгенерируйте другое случайное a и повторите проверку. Выбирайте небольшие значения a для ускорения вычислений. Выпо л-ните пять тестов [651]. (0дного может показаться достаточным, но выполните пять.) Если p не проходит одной из проверок, сгенерируйте другое p и попробуйте снова.

Иначе, можно не генерировать p случайным образом каждый раз, но последовательно перебирать числа, н а-чиная со случайно выбранного до тех пор, пока не б удет найдено простое число.

Этап (3) не является обязательным, но это хорошая идея. Проверка, что случайное нечетное p не делится на 3, 5 и 7 отсекает 54 процента нечетных чисел еще до этапа (4). Проверка делимости на все простые числа, меньшие 100, убирает 76 процентов нечетных чисел, проверка делимости на все простые числа, меньшие 256, убирает 80 процентов нечетных чисел. В общем случае, доля нечетных кандидатов, которые не делятся ни на одно простое число, меньшее n, равна 1.12/ln n. Чем больше проверяемое n, тем больше предварительных в ы-числений нужно выполнить до теста Rabin-Miller.

0дна из реализаций этого метода на Sparc II способна находить 256-битовые простые числа в среднем за 2.8 секунды, 512-битовые простые числа - в среднем за 24.0 секунды, 768-битовые простые числа - в среднем за 2.0 минуты, а 1024-битовые простые числа - в среднем за 5.1 минуты [918].

Сильные простые числа

Если n - произведение двух простых чисел, p и q, то может понадобиться использовать в качестве p и q сильные простые числа. Такие простые числа обладают рядом свойств, которые усложняют разложение пр о-изведения n определенными методами разложения на множители. Среди таких свойств были предложены [1328, 651]:

Наибольший общий делитель p - 1 и q - 1 должен быть небольшим.

И p - 1, и q - 1 должны иметь среди своих множителей большие простые числа, соответственно p и q. И p - 1, и q - 1 должны иметь среди своих множителей большие простые числа. И p + 1, и q + 1 должны иметь среди своих множителей большие простые числа.

И (p - 1)/2, и (q - 1)/2 должны быть простыми [182). (0братите внимание, при выполнении этого условия в ы-полняются и два первых.)

Насколько существенно применение именно сильных простых чисел, остается предметом продолжающихся споров. Эти свойства были разработаны, чтобы затруднить выполнение ряда старых алгоритмов разложения на множители. 0днако самые быстрые алгоритмы одинаково быстры при разложении на множители любых чисел, как удовлетворяющих приведенным условиям, так и нет [831].

Я против специальной генерации сильных простых чисел. Длина простых чисел гораздо важнее их структ у-ры. Более того, сама структура уменьшает случайность чи сла и может снизить устойчивость системы.

Но все может измениться. Могут быть созданы новые методы разложения на множители, которые лучше р а-ботают с числами, обладающими определенными свойствами. В этом случае снова могут потребоваться сил ь-ные простые числа. Заглядывайте в журналы по теоретической математике.

11.6 Дискретные логарифмы в конечном поле

В качестве другой однонаправленной функции в криптографии часто используется возведение в степень по модулю. Легко вычислить:

о* mod n

Задачей, обратной возведению в степень по модулю, является поиск дискретного логарифма. А это уже н е-легкая задача:

Найти x, для которого a* = b (mod n).

Например:

Если 3x = 15 mod 17, то x = 6

Решения существуют не для всех дискретных логарифмов (помните, речь идет только о целочисленных р е-шениях). Легко заметить, что следующее уравнение не имеет решений

3x =7 (mod 13)

Еще сложнее решать эту задачу для 1024-битовых чисел.

Вычисление дискретных логарифмов в конечной группе

Криптографы интересуются дискретными логарифмами следующих трех групп:

-Мультипликативная группа полей простых чисел: GF( p)

-Мультипликативная группа конечных полей степеней 2: GF(2n)

-Группы эллиптической кривой над конечными полями F: EC(F)

Безопасность многих алгоритмов с открытыми ключами основана на задаче поиска дискретных логарифмов, поэтому эта задача была глубоко изучена. Хороший подробный обзор этой проблемы и ее наилучшие решения на соответствующий момент времени можно найти в [1189, 1039]. Лучшей современной статьей на эту тему является [934].

Если p является простым числом и используется в качестве модуля, то сложность поиска дискретных лог а-рифмов в GF(p) по существу соответствует разложению на множители числа n того же размера, где n - это произведение двух простых чисел приблизительно равной длины [1378,934]. То есть:

e (1+O (1))(ln( n ))>2(ln((ln(n)))>2

Решето числового поля быстрее, оценка его эвристического времени выполнения:

e(1.923+O (1))(ln( n))X(ln((ln(n )))%

Стивен Полиг (Stephen Pohlig) и Мартин Хеллман нашли способ быстрого вычисления дискретных лог а-рифмов в GF(p) при условии, что p - 1 раскладывается на малые простые множители [1253]. По этой причине в криптографии используются только такие поля, для которых p - 1 обладает хотя бы одним большим простым множителем. Другой алгоритм [14] вычисляет дискретных логарифм со скоростью, сравнимой с разложением на множители, он был расширен на поля вида GF( pn) [716]. Этот алгоритм был подвергнут критике в [727] по ряду теоретических моментов. В других статьях [1588] можно увидеть, насколько на самом деле трудна пр о-блема в целом.

Вычисление дискретных логарифмов тесно связано с разложением на множители. Если вы можете решить проблему дискретного логарифма, то вы можете и разложить на множители. (Истинность обратного никогда не была доказана.) В настоящее время существует три метода вычисления дискретных логарифмов в поле простого числа [370, 934, 648]: линейное решето, схема целых чисел Гаусса и решето числового поля.

Предварительное, объемное вычисление для поля должно быть выполнено только один раз. Затем, быстро можно вычислять отдельные логарифмы. Это может серьезно уменьшить безопасность систем, основанных на таких полях. Важно, чтобы различные приложения использовали различные поля простых чисел. Хотя нескол ь-ко пользователей одного приложения могут применять общее поле.

В мире расширенных полей исследователями не игнорируются и GF(2 n). Алгоритм был предложен в [727]. Алгоритм Копперсмита (Coppersmith) позволяет за приемлемое время находить дискретные логарифмы в таких полях как GF(2127) и делает принципиально возможным их поиск в полях порядка GF(2 400) [368]. В его основе лежит [180]. У этого алгоритма очень велика стадия предварительных вычислений, но во всем остальном он хорош и эффективен. Реализация менее эффективной версии этого же алгоритма после семи часов предвар и-тельных вычислений тратила на нахождение каждого дискретного логарифма в поле GF(2 127) лишь несколько