Введение в криптографию
[an error occurred while processing this directive]

Как проверить большое число на простоту - часть 4


связывающее суммы Гаусса с суммами Якоби и позволяющее переписать сравнение теоремы 3 в терминах сумм Якоби (см. []). Так, при и соответствующее сравнение, справедливое для простых , отличных от 2, 3, 7, принимает вид

где и  - некоторый корень кубический из 1.

В 1984 г. в работе [] было внесено существенное усовершенствование в алгоритм, позволившее освободиться от требования неделимости чисел на квадраты простых чисел. В результате, например, выбрав число

и взяв равным произведению простых чисел с условием, что делится на , получим 1{,}5\cdot10^{52} $" width="97" height="33" >, что позволяет доказывать простоту чисел , записываемых сотней десятичных знаков. При этом вычисления будут проводиться в полях, порожденных корнями из 1 степеней 16, 9, 5 и 7.

Мой персональный компьютер с процессором Pentium-150, пользуясь реализацией этого алгоритма на языке UBASIC, доказал простоту записываемого 65 десятичными знаками, большего из простых чисел в примере Ривеста, Шамира и Адлемана (см. раздел ) за 8 секунд. Сравнение этих 8 секунд и 17 лет, потребовавшихся для разложения на множители предложенного в примере числа, конечно, впечатляет.

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

арифметических операций. А в предположении эта оценка сложности может быть получена при эффективно указанных и .

Next: 4.7. Как раскладывают составные

Up: 4. Алгоритмические проблемы теории

Previous: 4.5. Как строить большие

Contents:




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]