Алгоритм построения сильно простого числа

Во многих приложениях возникает необходимость строить простые числа с дополнительными условиями. Дадим следующее определение.

Определение 13.1. Мы будем называть нечетное простое число р сильно простым, если найдутся нечетные простые числа q, s и г такие, что

что равносильно равенствам.

для некоторых четных чисел г, j. а.

Как следует из ряда изложенных нами методов компрометации схемы RSA, см. раздел 10.1.1, произведение сильно простых чисел должно образовывать модуль схемы RSA.

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

В 1979 году Хью Вильямс (Hugh Williams) и Бренд Шмидт (Brend Schmid) предложили^[1] алгоритм, вариант которого мы приведем далее.

Предположим, что мы построили два простых числа г, s и хотим построить оставшиеся два простых числа р и q так, чтобы выполнялись сравнения (13.9). Для этого зафиксируем целое число а ^ 1, определим наименьшее положительное целое число х такое, что х = -(mods), и будем искать простое число q в арифметической прогрессии.

используя для этого алгоритм, аналогичный алгоритму 13.4.

Тогда, если число р = Ъщ + 1 будет простым, то оно же будет и сильно простым — это вытекает из сравнения.

Если r > y/q, то мы можем воспользоваться теоремой Лемера для доказательства простоты как числа q, так и числа р.

Если а — 1, то простое число р удовлетворяет равенству р = 2q + I. Простые числа р и г/, удовлетворяющие этому равенству, называются простыми-близнецами, и встречаются достаточно редко. Поэтому при практических вычислениях необходимо выбирать а достаточно большим.

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

для некоторых целых A, D таких, что D > А + 2а. Поскольку для выполнения условий теоремы Лсмсра нам необходимо выполнение условия q > у/p, мы получаем оценку на величину а сверху, а именно

Теперь зафиксируем некоторое значение а, обозначим.

и зафиксируем оценки на величину г. Для выполнимости условий теоремы Лемера положим.

тогда должно выполняться 5= г ^ га для некоторого действительного параметра а > 1.

Поскольку Яа ^ Я = {Is + x) r + 1 ^ яв, Для некоторого I € N, то мы получаем неравенство, которое задет ограничения сверху и снизу на размер перебираемого параметра I:

Исходя из того что перебираемый интервал не должен быть пустым, мы получим оценку сверху на параметр а. Действительно, указанный интервал не пуст при а < < ^В~^^а ? При практических вычислениях мы можем использовать значение, а = ^ .

Исходя из неравенства (13.11), получаем оценки для I

а также оценку на s сверху. Поскольку в силу построения выполнено «>х>0и!^1, то мы получаем неравенство.

откуда следует неравенство s < larjJ > которое мы будем использовать для верхней оценки s. Для нижней оценки будем использовать величину⁵ |" у/sa'.

Таким образом, для построения строго простого числа р такого, что А < р < В, и простых чисел q, r, s, участвующих в определении 13.1, необходимо выполнить следующую последовательность действий.

1. По заданным значениям А, В выбрать случайным образом четную величину а из интервала 1 < а < |Ц=.

'Нижняя граница для числа s определяется исходя из криптографических требований к конкретной системе защиты информации.

• 2. Вычислить величины ца, Чв, определяемые равенствами
• (13.10), величину, а = ~¹ и величину г_А =
• 3. Используя алгоритм 13.4, построить простые число г, s, удовлетворяющие неравенствам

• 4. Определить х = — (mod .s).
• 5. Перебирая целые значения I в интервале (13.12), вычислить простые числа

Для доказательства простоты чисел р, q достаточно использовать теорему Лемера.

Мы предлагаем читателю самостоятельно, основываясь на алгоритме 13.4, разработать детальное описание алгоритма построения сильно простого числа.

• [1] См. Williams Н.С. and Schmid В. Some remarks cocerning the MIT public-keycryptosystem // BIT. — Vol. 19. — 1979. -pp. 525−538.