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

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


Следующая функция, определенная на множестве целых чисел,

является характером по модулю и порядок этого характера равен . Сумма

называется суммой Гаусса. Формулируемая ниже теорема 3 представляет собой аналог малой теоремы Ферма, используемый в алгоритме Адлемана - Ленстры.

Теорема 5.   Пусть  - нечетное простое число, . Тогда в кольце

выполняется сравнение

Если при каких-либо числах сравнение из теоремы 3 нарушается, можно утверждать, что составное число. В противном случае, если сравнение выполняется, оно дает некоторую информацию о возможных простых делителях числа . Собрав такую информацию для различных , в конце концов удается установить, что имеет лишь один простой делитель и является простым.

В случае легко проверить, что сравнение из теоремы 3 равносильно хорошо известному в элементарной теории чисел сравнению

(13)

где  - так называемый символ Якоби. Хорошо известно также, что последнее сравнение выполняется не только для простых , но и для любых целых , взаимно простых с . Заметим также, что для вычисления символа Якоби существует быстрый алгоритм, основанный на законе взаимности Гаусса и, в некотором смысле, подобный алгоритму Евклида вычисления наибольшего общего делителя. Следующий пример показывает, каким образом выполнимость нескольких сравнений типа () дает некоторую информацию о возможных простых делителях числа .

Пример 1.   (Х. Ленстра). Пусть  - натуральное число, , для которого выполнены сравнения

(14)

а кроме того с некоторым целым числом имеем

(15)

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

Докажем, что из выполнимости (14-15) следует, что каждый делитель числа удовлетворяет одному из сравнений




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


[an error occurred while processing this directive]