'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

7 Алгоритм Agrawal


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

13 Алгоритм Agrawal


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


×

HTML:





Ссылка: