Учебное пособие.
Series: Lecture Notes in Computer Science, Vol. 3000.
Berlin, Heidelberg: Springer-Verlag, 2004. – X+147 p.
ISBN: 3-540-40344-2.
Книга посвящена алгоритмам для решения древней задачи о простоте: определить, яляется ли данное натуральное число N простым или составным. Эта задача является одной из базовых в теории чисел, и эффективные алгоритмы для её решения, то есть, алгоритмы, в которых число вычислительных шагов является полиномиальным от числа цифр N, важны для теоретической информатики и для применений в алгоритмике и криптологии.
Эта книга представляет собой самодостаточный отчет о теоретически и практически важных эффективных алгоритмах для задачи о простоте чисел, включая рандомизированные алгоритмы Соловея-Штрассена и Миллера-Рабина, появившиеся в конце 1970-ых так и недавно открытый детерминированный алгоритм Агравала, Кайяла и Саксены. Учебник написан для студентов информатики, в особенности для студентов с уклоном в криптологию и дискретную математику; также он может быть использован в качестве дополнительной литературы в соответствующих курсах или для самостоятельного изучения.
Замечание:
В Сети эта книга доступна, но у версии книги, предлагаемой здесь, имеется важное преимущество - в книге исправлено более 40 опечаток (Список опечаток). Contents: Introduction: Efficient Primality Testing.
Algorithms for the Primality Problem.
Polynomial and Superpolynomial Time Bounds.
Is PRIMES in P?
Randomized and Superpolynomial Time Algorithms for the Primality Problem.
The New Algorithm.
Finding Primes and Factoring Integers.
How to Read This Book.
Algorithms for Numbers and Their Complexity.
Notation for Algorithms on Numbers.
O-notation.
Complexity of Basic Operations on Numbers.
Fundamentals from Number Theory.
Divisibility and Greatest Common Divisor.
The Euclidean Algorithm.
Modular Arithmetic.
The Chinese Remainder Theorem.
Prime Numbers.
Basic Observations and the Sieve of Eratosthenes.
The Fundamental Theorem of Arithmetic.
Chebychev's Theorem on the Density of Prime Numbers.
Basics from Algebra: Groups, Rings, and Fields.
Groups and Subgroups.
Cyclic Groups.
Definitions, Examples, and Basic Facts.
Structure of Cyclic Groups.
Subgroups of Cyclic Groups.
Rings and Fields.
Generators in Finite Fields.
The Miller-Rabin Test.
The Fermat Test.
Nontrivial Square Roots of 1.
Error Bound for the Miller-Rabin Test.
The Solovay-Strassen Test.
Quadratic Residues.
The Jacobi Symbol.
The Law of Quadratic Reciprocity.
Primality Testing by Quadratic Residues.
More Algebra: Polynomials and Fields.
Polynomials over Rings.
Division with Remainder and Divisibility for Polynomials.
Quotients of Rings of Polynomials.
Irreducible Polynomials and Factorization.
Roots of Polynomials.
Roots of the Polynomial Xr - 1.
Deterministic Primality Testing in Polynomial Time.
The Basic Idea.
The Algorithm of Agrawal, Kayal, and Saxena.
The Running Time.
Overall Analysis.
Bound for the Smallest Witness r.
Improvements of the Complexity Bound.
The Main Theorem and the Correctness Proof.
Proof of the Main Theorem.
Preliminary Observations.
Powers of Products of Linear Terms.
A Field F and a Large Subgroup G of F*.
Completing the Proof of the Main Theorem.
Appendix.
Basics from Combinatorics.
Some Estimates.
Proof of the Quadratic Reciprocity Law.
A Lemma of Gauss.
Quadratic Reciprocity for Prime Numbers.
Quadratic Reciprocity for Odd Integers.
References.
Index.
Series: Lecture Notes in Computer Science, Vol. 3000.
Berlin, Heidelberg: Springer-Verlag, 2004. – X+147 p.
ISBN: 3-540-40344-2.
Книга посвящена алгоритмам для решения древней задачи о простоте: определить, яляется ли данное натуральное число N простым или составным. Эта задача является одной из базовых в теории чисел, и эффективные алгоритмы для её решения, то есть, алгоритмы, в которых число вычислительных шагов является полиномиальным от числа цифр N, важны для теоретической информатики и для применений в алгоритмике и криптологии.
Эта книга представляет собой самодостаточный отчет о теоретически и практически важных эффективных алгоритмах для задачи о простоте чисел, включая рандомизированные алгоритмы Соловея-Штрассена и Миллера-Рабина, появившиеся в конце 1970-ых так и недавно открытый детерминированный алгоритм Агравала, Кайяла и Саксены. Учебник написан для студентов информатики, в особенности для студентов с уклоном в криптологию и дискретную математику; также он может быть использован в качестве дополнительной литературы в соответствующих курсах или для самостоятельного изучения.
Замечание:
В Сети эта книга доступна, но у версии книги, предлагаемой здесь, имеется важное преимущество - в книге исправлено более 40 опечаток (Список опечаток). Contents: Introduction: Efficient Primality Testing.
Algorithms for the Primality Problem.
Polynomial and Superpolynomial Time Bounds.
Is PRIMES in P?
Randomized and Superpolynomial Time Algorithms for the Primality Problem.
The New Algorithm.
Finding Primes and Factoring Integers.
How to Read This Book.
Algorithms for Numbers and Their Complexity.
Notation for Algorithms on Numbers.
O-notation.
Complexity of Basic Operations on Numbers.
Fundamentals from Number Theory.
Divisibility and Greatest Common Divisor.
The Euclidean Algorithm.
Modular Arithmetic.
The Chinese Remainder Theorem.
Prime Numbers.
Basic Observations and the Sieve of Eratosthenes.
The Fundamental Theorem of Arithmetic.
Chebychev's Theorem on the Density of Prime Numbers.
Basics from Algebra: Groups, Rings, and Fields.
Groups and Subgroups.
Cyclic Groups.
Definitions, Examples, and Basic Facts.
Structure of Cyclic Groups.
Subgroups of Cyclic Groups.
Rings and Fields.
Generators in Finite Fields.
The Miller-Rabin Test.
The Fermat Test.
Nontrivial Square Roots of 1.
Error Bound for the Miller-Rabin Test.
The Solovay-Strassen Test.
Quadratic Residues.
The Jacobi Symbol.
The Law of Quadratic Reciprocity.
Primality Testing by Quadratic Residues.
More Algebra: Polynomials and Fields.
Polynomials over Rings.
Division with Remainder and Divisibility for Polynomials.
Quotients of Rings of Polynomials.
Irreducible Polynomials and Factorization.
Roots of Polynomials.
Roots of the Polynomial Xr - 1.
Deterministic Primality Testing in Polynomial Time.
The Basic Idea.
The Algorithm of Agrawal, Kayal, and Saxena.
The Running Time.
Overall Analysis.
Bound for the Smallest Witness r.
Improvements of the Complexity Bound.
The Main Theorem and the Correctness Proof.
Proof of the Main Theorem.
Preliminary Observations.
Powers of Products of Linear Terms.
A Field F and a Large Subgroup G of F*.
Completing the Proof of the Main Theorem.
Appendix.
Basics from Combinatorics.
Some Estimates.
Proof of the Quadratic Reciprocity Law.
A Lemma of Gauss.
Quadratic Reciprocity for Prime Numbers.
Quadratic Reciprocity for Odd Integers.
References.
Index.