Полиномиальный алгоритм проверки простоты числа

План семинара
Постановка задачи
Идея алгоритма
Полиномиальный алгоритм
Оценка времени работы алгоритма
Доказательство корректности алгоритма

Постановка задачи
Дано натуральное число n. Необходимо проверить является ли оно простым за полиномиальное время от длины числа n в бинарной форме.

План семинара
Постановка задачи
Идея алгоритма
Полиномиальный алгоритм
Оценка времени работы алгоритма
Доказательство корректности алгоритма

Основная идея алгоритма
Лемма 1.1.

План семинара
Постановка задачи
Идея алгоритма
Полиномиальный алгоритм
Оценка времени работы алгоритма
Доказательство корректности алгоритма

Алгоритм Agrawal

План семинара
Постановка задачи
Идея алгоритма
Полиномиальный алгоритм
Оценка времени работы алгоритма
Доказательство корректности алгоритма

Время работы алгоритма
Лемма 2.1.
Лемма 2.2.

Время работы алгоритма
Лемма 2.3.
Доказательство:
Шаг 1:
Шаг 2-3:
Шаг 4:
Шаг 5:
Так как каждая проверка равенства требует
умножений полиномов степени с
коэффициентами размером .

Время работы алгоритма
Лемма 3.2.(Фоуври)
Лемма 3.3.

План семинара
Постановка задачи
Идея алгоритма
Полиномиальный алгоритм
Оценка времени работы алгоритма
Доказательство корректности алгоритма

Алгоритм Agrawal

Обозначения

Доказательство корректности
Теорема 3.1.
Лемма 3.2.

Доказательство корректности
Определение 3.3.
Лемма 3.4.

Доказательство корректности
Лемма 3.5.(Hendric Lenstra Jr.)
Лемма 3.6.
Лемма 3.7.

Если не запомните ничего другого
Существует полиномиальный алгоритм проверки простоты числа
Идея алгоритма:
Доказано, что алгоритм работает корректно и за время