Алгебра и теория чисел :: занятие 09 (20.04.2010)

Занятие 1 (20.04.2010)
Практические задачи. Проверка чисел на простоту
Лекция. (Теория) Квадратичные вычеты
Лекция. (Практика) Вероятностные тесты чисел на простоту

Занятие 1 (20.04.2010)
Проверка чисел на простоту ps pdf
mrptest.Тест Миллера-Рабинаps pdf
ssptest.Тест Соловея-Штрассенаps pdf
(Теория) Квадратичные вычеты
План лекции
  1. Квадратичные вычеты
    1. Квадратичный закон взаимности
    2. Символ Якоби, формулы для символа Якоби аналогичные формулам для символа Лежандра
  2. Цепные (непрерывные) дроби
    1. Цепные дроби, рекуррентные формулы для числителей и знаменателей дробей
    2. Число слагаемых в полиноме $[a_0; a_1; \ldots; a_n]$
    3. Теорема о том, что $[a_0; a_1; \ldots; a_{n-1}; a_n] = [a_n; a_{n-1}; \ldots; a_1; a_0]$
(Практика) Вероятностные тесты чисел на простоту
План лекции
  1. Алгоритмы проверки простоты числа
    1. Тест Ферма проверки чисел на простоту, числа Кармайкла
    2. Тест Соловея-Штрассена проверки чисел на простоту, вероятность ошибки
    3. Тест Миллера-Рабина проверки чисел на простоту
      • Формула для числа свидетелей того, что число составное
  2. Сложность задачи проверки чисел на простоту и разложения на множители
    1. Принадлежность задачи проверки чисел на простоту классам \textbf{NP} и \textbf{coNP}
    2. Принадлежность задачи разложения чисел на множители (в подходящей формулировке) классам \textbf{NP} и \textbf{coNP}