Полиномиальный алгоритм проверки простоты числа Комалёва Ольга. - презентация

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

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

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

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

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

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

7 7 Алгоритм Agrawal

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

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

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

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

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

13 13 Алгоритм Agrawal

14 14 Обозначения

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

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

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

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

19 19 Источники M.Agrawal, N.Kayal, N.Saxena «PRIMES is in P» А.Черемушкин «Лекции по арифметическим алгоритмам в криптографии» П.Ноден, К.Китте «Алгебраическая алгоритмика» Т.Кормен, Ч.Лейзерсон, Р.Ривест «Алгоритмы: построение и анализ»