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

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


(16)

Не уменьшая общности, можно считать, что  - простое число. Введем теперь обозначения , , где и  - нечетные числа. Из (15) и сравнения следует, что . Далее, согласно (), выполняются следующие сравнения

означающие (в силу того, что символ Якоби может равняться лишь или ), что

При k$" width="48" height="29" > это равенство означает, что при , и, следовательно,

. Если же , то имеем и . Этим () доказано.

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

Опишем (очень грубо) схему алгоритма Адлемана - Ленстры для проверки простоты :

1) выбираются различные простые числа и различные простые нечетные такие, что

а) для каждого все простые делители числа содержатся

среди и не делятся на квадрат простого числа,

б) \sqrt{N} $" width="163" height="37" >;

2) для каждой пары выбранных чисел , проводятся тесты, подобные сравнению из теоремы 3. Если не удовлетворяет какому-либо из этих тестов - оно составное. В противном случае

3) определяется не очень большое множество чисел, с которыми только и могут быть сравнимы простые делители . А именно, каждый простой делитель числа должен удовлетворять сравнению вида

4) проверяется, содержит ли найденное множество делители . Если при этом делители не обнаружены, утверждается, что  - простое число.

Если число составное, оно обязательно имеет простой делитель , меньший

Пример 2.  

Если выбрать следующие множества простых чисел

то таким способом удается проверять простоту чисел

Отметим, что в работе [] для тестирования использовались не сравнения теоремы 3, а закон взаимности для степенных вычетов и так называемые суммы Якоби. Сумма Якоби

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




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


[an error occurred while processing this directive]