Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

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

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

Теорема 3. Пусть [pic] - нечетное простое число, [pic]. Тогда в кольце [pic] выполняется сравнение

[pic].

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

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

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

Пример (X. Ленстра). Пусть [pic] — натуральное число, [pic]. для которого выполнены сравнения

[pic], (14) а кроме того с некоторым целым числом [pic] имеем

[pic].

(15)

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

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

[pic] или [pic].

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

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

[pic].
При [pic] это равенство означает, что [pic] при [pic], и, следовательно,
[pic]. Если же [pic], то имеем [pic] и [pic]. Этим (16) доказано.

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

Опишем схему алгоритма Адлемана - Ленстры для проверки простоты
[pic]:

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

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

среди [pic] и [pic] не делятся на квадрат простого числа;

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

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

[pic], [pic].

Рекомендуем скачать другие рефераты по теме: оценка реферата, диплом на тему.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата