Lecture Notes in Computer Science - Dietzfelbinger M. / Дицфельбингер М. - Primality Testing in Polynomial Time / Полиномиальный тест на простоту [2004, PDF, ENG]

6 августа 2002, статья с заголовком "Простые находятся в P" М. Агравала, Н. Кайяла и Н. Саксены, появилась на веб-сайте индийского Технологического института в Канпуре, Индия. В этой статье было показано, что "задача простоты чисел" имеет "детерминированный алгоритм", который выполняется в "полиномиальное время".
Определение, является ли данное число N простым или нет является задачей, которая была известна с древних времен и неизменно привлекала математиков в течение многих столетий. Но только 20-й век с появлением криптографических систем, в которых напрямую использовались большие простые числа, вывел ее в плоскость практики, чтобы надежно различать простые и составные числа большого размера.
Достаточно быстро появились алгоритмы, решающие задачу очень эффективно и качественно для всех практических применений, и доказуемо обладающие временем выполнения, полиномиальым от количества цифр входного числа N.
Единственный недостаток этих алгоритмов - то, что они используют "рандомизацию" – это означает, что компьютер, на котором выполняется алгоритм, совершает некие случайные эксперименты в рамках работы алгоритма, и есть небольшой шанс, что результат на выходе алгоритма может быть неправильным, или же время выполнения алгоритма может зависеть от длины входа (количества цифр числа N) не полиномиально. Существование алгоритма, который бы выполнялся бы без элементов рандомизации, решал задачу безошибочно и имел полиномиальное время выполнения, было знаменитой открытой проблемой в теории сложности в течение многих десятилетий, когда статья Агравала, Кайяла и Саксены прогремела в Интернете. Новость об этом удивительном результате распространилась очень быстро по всему миру среди ученых, занимающихся теорией вычислений, криптологией и теорией чисел; в эти дни она даже попалала на полосы массовых изданий, что было довольно необычно для темы из теоретической информатики.
Фактически же, изменилось не многое. В криптографических приложениях быстрые рандомизированные алгоритмы тестирования простоты чисел продолжают использоваться, так как они более скоростные, и ошибка (в определении простого числа) может быть снижена до столь малой величины, что это становится не важным для практическоего применения. Новый алгоритм не в состояни помочь быстро факторизовать числа и не обрушивает никакую криптографическую систему. Однако, новый алгоритм очень важен и из-за его долгой истории и из-за методов, используемых в решении.
Как это часто бывает в сфере теоретико-числовых алгоритмов, формулировка детерминированного теста простоты весьма компактна и использует только простейшие базовые процедуры. Его анализ является немного более сложным, но удивительно - он обходится небольшим набором методов и фактов, входящих в вводные курсы алгебры и теории чисел. С одной стороны, это вызывает философский вопрос, возможно ли и другие важные открытые проблемы в теоретической информатике решть с использованием только базовых методов. С другой стороны, это открывает редкую возможность для читателей без специализированной математической подготовки полностью понять доказательство нового и важного результата.
Главная цель данного текста - провести читателя по всему пути от определений фундаментальных понятий теории чисел и алгебры до полного понимания нового алгоритма и доказательства его корректности и временнóго анализа, подробно освещая все промежуточные шаги. Конечно, читатель все же должен пройти весь путь, который местами может быть трудным; от него требуется определенная базовая математическая подготовка и, конечно, хорошая настойчивость.
Для контраста и чтобы дать введение в некоторые практические релевантные тесты простоты для полного неофита в этой области, также описаны и проанализированы два классических теста простоты чисел, а именно, "тест Миллера-Рабина" и "тест Соловея-Штрассена". Для этого в книгу включен весь необходимый математический материал для этих алгоритмов и их анализа
Я надеюсь, что этот текст сделает тему тестирования простоты чисел и в особенности замечательный результат Агравала, Кайала и Саксены немного доступнее для интересующихся студентов, изучающих информатику, криптологию или математику.

1. Introduction: Efficient Primality Testing
1.1 Algorithms for the Primality Problem
1.2 Polynomial and Superpolynomial Time Bounds
1.3 Is PRIMES in P?
1.4 Randomized and Superpolynomial Time Algorithms for the Primality Problem
1.5 The New Algorithm
1.6 Finding Primes and Factoring Integers
1.7 How to Read This Book
2. Algorithms for Numbers and Their Complexity
2.1 Notation for Algorithms on Numbers
2.2 O-notation
2.3 Complexity of Basic Operations on Numbers
3. Fundamentals from Number Theory
3.1 Divisibility and Greatest Common Divisor
3.2 The Euclidean Algorithm
3.3 Modular Arithmetic
3.4 The Chinese Remainder Theorem
3.5 Prime Numbers
3.5.1 Basic Observations and the Sieve of Eratosthenes
3.5.2 The Fundamental Theorem of Arithmetic
3.6 Chebychev's Theorem on the Density of Prime Numbers
4. Basics from Algebra: Groups, Rings, and Fields
4.1 Groups and Subgroups
4.2 Cyclic Groups
4.2.1 Definitions, Examples, and Basic Facts
4.2.2 Structure of Cyclic Groups
4.2.3 Subgroups of Cyclic Groups
4.3 Rings and Fields
4.4 Generators in Finite Fields
5. The Miller-Rabin Test
5.1 The Fermat Test
5.2 Nontrivial Square Roots of 1
5.3 Error Bound for the Miller-Rabin Test
6. The Solovay-Strassen Test
6.1 Quadratic Residues
6.2 The Jacobi Symbol
6.3 The Law of Quadratic Reciprocity
6.4 Primality Testing by Quadratic Residues
7. More Algebra: Polynomials and Fields
7.1 Polynomials over Rings
7.2 Division with Remainder and Divisibility for Polynomials ....
7.3 Quotients of Rings of Polynomials
7.4 Irreducible Polynomials and Factorization
7.5 Roots of Polynomials
7.6 Roots of the Polynomial Xr - 1
8. Deterministic Primality Testing in Polynomial Time
8.1 The Basic Idea
8.2 The Algorithm of Agrawal, Kayal, and Saxena
8.3 The Running Time
8.3.1 Overall Analysis
8.3.2 Bound for the Smallest Witness r
8.3.3 Improvements of the Complexity Bound
8.4 The Main Theorem and the Correctness Proof
8.5 Proof of the Main Theorem
8.5.1 Preliminary Observations
8.5.2 Powers of Products of Linear Terms
8.5.3 A Field F and a Large Subgroup G of F*
8.5.4 Completing the Proof of the Main Theorem
A. Appendix
A.1 Basics from Combinatorics
A.2 Some Estimates
A.3 Proof of the Quadratic Reciprocity Law
A.3.1 A Lemma of Gauss
A.3.2 Quadratic Reciprocity for Prime Numbers
A.3.3 Quadratic Reciprocity for Odd Integers
References
Index

Минеев М.П., Чубариков В.Н. Лекции по арифметическим вопросам криптографии
Глухов М.М. и др. Введение в теоретико-числовые методы криптографии
Крэндалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспекты
Василенко О.Н. Теоретико-числовые алгоритмы в криптографии
Crandall R., Pomerance C. Prime Numbers: A Computational Perspective
Маховенко Е.Б. Теоретико-числовые методы в криптографии
Song Y. Yan Primality Testing and Integer Factorization in Public-Key Cryptography
Ишмухаметов Ш.Т. Методы факторизации натуральных чисел
Bressoud D.M. Factorization and Primality Testing
Riesel H. Prime Numbers and Computer Methods for Factorization
Черемушкин А.В. Лекции по арифметическим алгоритмам в криптографии
Ростовцев А., Маховенко Е. Теоретическая криптография
Коутинхо С. Введение в теорию чисел. Алгоритм RSA
Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. 1-е изд.