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

Содержание

Слайд 2

План семинара

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

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

Слайд 3

Постановка задачи

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

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

Слайд 4

План семинара

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

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

Слайд 5

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

Лемма 1.1.

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

Слайд 6

План семинара

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

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

Слайд 7

Алгоритм Agrawal

Алгоритм Agrawal

Слайд 8

План семинара

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

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

Слайд 9

Время работы алгоритма

Лемма 2.1.
Лемма 2.2.

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

Слайд 10

Время работы алгоритма

Лемма 2.3.
Доказательство:
Шаг 1:
Шаг 2-3:
Шаг 4:
Шаг 5:
Так как каждая проверка

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

Слайд 11

Время работы алгоритма

Лемма 3.2.(Фоуври)
Лемма 3.3.

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

Слайд 12

План семинара

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

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

Слайд 13

Алгоритм Agrawal

Алгоритм Agrawal

Слайд 14

Обозначения

Обозначения

Слайд 15

Доказательство корректности

Теорема 3.1.
Лемма 3.2.

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

Слайд 16

Доказательство корректности

Определение 3.3.
Лемма 3.4.

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

Слайд 17

Доказательство корректности

Лемма 3.5.(Hendric Lenstra Jr.)
Лемма 3.6.
Лемма 3.7.

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

Слайд 18

Если не запомните ничего другого

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

Если не запомните ничего другого Существует полиномиальный алгоритм проверки простоты числа Идея
алгоритм работает корректно и за время
Имя файла: Полиномиальный-алгоритм-проверки-простоты-числа.pptx
Количество просмотров: 161
Количество скачиваний: 0