8.5. Метод Гордона построения сильных простых чисел

Суть метода Гордона построения сильного простого числа заключается в следующем.

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

2. Строим простое число аналогично построению числа.

3. С помощью метода пробных делений и тестов на простоту аналогично пункту 1, строим простое число , перебираяв промежутке.

4. Вычисляем . Чтобы не возводить в степень, это удобно сделать с помощью китайской теоремы об остатках, т.к.и.

Потребуем, чтобы искомое число удовлетворяло тем же условиям:и.

5. Если число – нечетное, то присваиваем, иначе, полагаем.

6. Строим – ближайшее простое число, сравнимое с нечетным числомпо модулю, т.е. тестируем на простоту числа вида,, пока не найдется простое число (либо сработают ограничения реализации).

Алгоритм основан наследующей теореме.

Теорема (Гордон). Если – нечетные простые числа, то простое числоудовлетворяет условиямитогда и только тогда, когда оно представимо в виде, где– нечетное число из пары.

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

1. Строим исходное псевдослучайное простое число , размером, скажем, в 6 битов. Выбираем псевдослучайно шестибитовое число:. В промежуткеопределяем простое число.

2. Строим случайное простое число , аналогично построению числа. Пусть. В промежуткеопределяем простое число.

3. Строим простое число , перебираяв промежутке. Получаем.

4. Вычисляем , решая с помощью китайской теоремы об остатках систему:,.

Используя расширенный алгоритм Эвклида, получим соотношение

, откуда: ,.

Следовательно,

.

5. Число – четное, поэтому полагаем.

6. Строим простое число, сравнимое с по модулю 2773, тестируя на простоту числа вида. При, получаем соответственно: 5075, 10621, 11167, 21713.

Лишь последнее число является простым. Его разрядность значительно превосходит разрядность исходного числа , что нежелательно, поскольку, например, для криптосистемы RSA требуется построение сильных простых чисел заданной разрядности.

При большой разрядности чисел, используемых в вычислениях, количество сильных простых велико, поэтому указанный выше недостаток проявляется в существенно меньшей мере.

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

Вопросы к главе 8

1. Чем отличаются детерминированный и вероятностный тест на простоту?

2. Какое свойство вероятностных тестов позволяет использовать их для практических приложений?

3. Тесты каких типов, как правило, используются для выбора параметров криптосистемы RSA?

4. Тесты каких типов, как правило, используются для выбора параметров криптосистемы Ель Гамаля?

5. Какое сравнение называется сравнением Ферма?

6. Какие числа называются псевдопростыми?

7. Какие числа называются числами Кармайкла?

8. В чем заключается тест Ферма на простоту и какой его недостаток?

9. Какое сравнение называется соотношением Эйлера?

10. Какие числа называются эйлеровыми псевдопростыми?

11. Существуют ли числа, являющиеся эйлеровыми псевдопростыми по любому основанию?

12. В чем заключается тест Соловея-Штрассена на простоту и какова вероятность ошибки при тестировании числа по разным основаниям?

13. Какие числа составляют множество квадратных корней из единицы по простому модулю?

14. Можно ли утверждать, что количество множество квадратных корней из единицы по составному модулю не меньше трех?

15. В чем заключается тест Рабина-Миллера на простоту и какова вероятность ошибки при тестировании числа по разным основаниям?

16. Какое число называется сильным псевдопростым по заданному основанию и для каких целей применяется метод Гордона?

17. Каковы общие требования, выдвигаемые к параметрам криптосистемы RSA?

18. Каково определение сильных простых чисел?