Ключевые понятия
Indq(x)
Введем некоторое число
. Пусть
— его первообразный корень. Тогда должно выполняться следующее условие:
,
где
.
Замечание: В качестве
выбираем наименьшее неотрицательное число.
Сумма Якоби
Суммой Якоби называют сумму следующего вида:
,
где суммирование идет по всем наборам классов смежности для
в
, кроме тех, что равны
.
Ключевые леммы
Основные леммы[2], используемые при доказательстве корректности алгоритма:
Лемма 2.
Пусть
и имеет порядок
в группе
. Возьмем
. Так же
где
— многочлен в
для каждого
. Будем считать, что идеалы
Если
является простым делителем
, тогда в
:
и каждое
, делимое на некоторый простой идеал из
, лежит над
Лемма 4.
Если
, тогда
Лемма 5.
Выберем
такие, что
. Для
положим:
то есть
или
.
Тогда
Лемма 6.[3].
Для всех
Лемма 7.
Если
, то существуют такие
что
и
где
— обратный элемент к
Лемма (Извлечения).
Пусть
— идеалы в
такие, что
и пусть
сопряженные простые идеалы, делящие
соответственно. Пускай существует такое
что
. Тогда для любого
выполняется:
и следовательно
Идея алгоритма
Если
является составным числом, то оно имеет некий делитель
. Для проверки на простоту ищем это
.
Если нам известны значения
для каждой пары
, то по китайской теореме об остатках мы можем найти
. Каждая пара
выбирается следующим образом:
, а
— простое Евклидово число относительно
такое, что
В алгоритме перебираются все возможные значения
для всех
, исходя из того, что известно только одно
Алгоритм
- Ввод: целое число n > 1.
A. Шаг подготовки
1. Вычисляем наименьшее положительное число
свободное от квадратов, такое что:
.
Определим множество «начальных» простых чисел, являющиеся делителями
. Назовем
Евклидовым простым числом, если
простое и
2. Проверим — делится ли
на любое «начальное» или Евклидово простое число. Если делитель найдется, причем не равный
. Тогда объявляем
составным и прерываем алгоритм. Иначе вычислим наименьший положительный первообразный корень
для каждого Евклидового простого числа
.
3. Для каждого «начального» простого числа
найдем числа
такие, что:
,
,
Для
примем
.
4. Для каждого «начального» и Евклидового простых чисел, таких что
зафиксируем простой идеал:
,
где
принадлежит
,а
— корень из единицы.
Вычислим сумму Якоби
если
,
если
B. Шаг вычислений
1. Для каждого «начального» простого числа
найдем НОД в
для
и набора
, где
пробегает все значения Евклидовых простых чисел, причем
, а
пробегает по всем значениям из Gal
. Тогда либо выносим решение о том, что
составное, либо строим надлежащий идеал
в кольце
, а также находим числа
и
,
такие, что:
,
или некоторое из
, где
2. Для каждого «начального» простого числа
сделаем следующее: если для некоторого
, тогда возьмем
. В этом ключе построим числа
для всех
,
и такие, что:
Если же для всех
, примем
.
C. Шаг объединения результатов
Проделаем шаги 1-4 для всех натуральных
1. Для каждого
вычислим по китайской теореме об остатках вычислим числа
:
при всевозможных
, что
. Так же положим, что
2. Для каждого
посчитаем наименьшее целое, положительное число
3. Используя Китайскую теорему об остатках, вычислим наименьшее положительное число
такое, что
для каждого
4. Если
, тогда объявляем
составным. Иначе переходим к следующему
5. Объявляем
простым.