Сильные простые числа
Практические соображения
В реальных приложениях генерация простых чисел происходит быстро.
(1) Сгенерируйте случайное и-битовое число/;.
(2) Установите старший и младший биты равными 1. (Старший бит гарантирует требуемую длину простого числа, а младший бит обеспечивает его нечетность.)
(3) Убедитесь, что р не делится на небольшие простые числа: 3, 5, 7, 11, и т.д. Во многих реализациях пров е-ряется делимость р на все простые числа, меньшие 256. Наиболее эффективной является проверка на д е-лимость для всех простых чисел, меньших 2000 [949]. Это может быть эффективно выполнено с помощью колеса [863].
(4) Выполните тест Rabin-Miller для некоторого случайного а. Если р проходит тест, сгенерируйте другое случайное а и повторите проверку. Выбирайте небольшие значения а для ускорения вычислений. Выполните пять тестов [651]. (Одного может показаться достаточным, но выполните пять.) Если р не проходит одной из проверок, сгенерируйте другое р и попробуйте снова.
Иначе, можно не генерировать р случайным образом каждый раз, но последовательно перебирать числа, н а-чиная со случайно выбранного до тех пор, пока не б удет найдено простое число.
Этап (3) не является обязательным, но это хорошая идея. Проверка, что случайное нечетное р не делится на 3, 5 и 7 отсекает 54 процента нечетных чисел еще до этапа (4). Проверка делимости на все простые числа, меньшие 100, убирает 76 процентов нечетных чисел, проверка делимости на все простые числа, меньшие 256, убирает 80 процентов нечетных чисел. В общем случае, доля нечетных кандидатов, которые не делятся ни на одно простое число, меньшее и, равна 1.12/1п п. Чем больше проверяемое и, тем больше предварительных вычислений нужно выполнить до теста Rabin-Miller.
Одна из реализаций этого метода на Sparc II способна находить 256-битовые простые числа в среднем за 2.8 секунды, 512-битовые простые числа - в среднем за 24.0 секунды, 768-битовые простые числа - в среднем за 2.0 минуты, а 1024-битовые простые числа - в среднем за 5.1 минуты [918].
Если п - произведение двух простых чисел, р и q, то может понадобиться использовать в качестве р и q сильные простые числа.Такие простые числа обладают рядом свойств, которые усложняют разложение пр о-изведения п определенными методами разложения на множители. Среди таких свойств были предложены [1328, 651]:
Наибольший общий делитель p -lnq -l должен быть небольшим.
Hp -l,nq -l должны иметь среди своих множителей большие простые числа, соответственно p'nq'.
Hp' -l,nq' -l должны иметь среди своих множителей большие простые числа.
Яр + 1, и q + 1 должны иметь среди своих множителей большие простые числа.
И (р - 1)/2, и (q - 1)/2 должны быть простыми [182). (Обратите внимание, при выполнении этого условия в ы-полняются и два первых.)
Насколько существенно применение именно сильных простых чисел, остается предметом продолжающихся споров. Эти свойства были разработаны, чтобы затруднить выполнение ряда старых алгоритмов разложения на множители. Однако самые быстрые алгоритмы одинаково быстры при разложении на множители любых чисел, как удовлетворяющих приведенным условиям, так и нет [831].
Я против специальной генерации сильных простых чисел. Длина простых чисел гораздо важнее их структ у-ры. Более того, сама структура уменьшает случайность чи ела и может снизить устойчивость системы.
Но все может измениться. Могут быть созданы новые методы разложения на множители, которые лучше р а-ботают с числами, обладающими определенными свойствами. В этом случае снова могут потребоваться сил ь-ные простые числа. Заглядывайте в журналы по теоретической математике.
11.6 Дискретные логарифмы в конечном поле
В качестве другой однонаправленной функции в криптографии часто используется возведение в степень по модулю. Легко вычислить:
a* mod я
Задачей, обратной возведению в степень по модулю, является поиск дискретного логарифма. А это уже н е-легкая задача:
Найти х, для которого if = b (mod n).
Например:
ЕслиЗх=15пкх117,тох = 6
Решения существуют не для всех дискретных логарифмов (помните, речь идет только о целочисленных р е-шениях). Легко заметить, что следующее уравнение не имеет решений
3х =7 (mod 13)
Еще сложнее решать эту задачу для 1024-битовых чисел.