Primality Testing and Integer Factorization in Public-Key Cryptography / Тестирование на простоту и факторизация в криптографии с открытым ключом
Год: 2009
Автор: Song Y. Yan / Сонг Ю. Ян
Жанр: Учебное пособие
Издательство: Springer
ISBN: 1-4419-4586-5
Серия: Advances in Information Security
Язык: Английский
Формат: PDF
Качество: Изначально компьютерное (eBook)
Количество страниц: 385
Описание:
Из Предисловия к первому изданию
Тестирование на простоту чисел и целочисленная факторизация, как указано Гауссом в его Disquisitiones Arithmeticae (статья 329) в 1801 г. - две наиболее фундаментальные задачи (как и две самых важных области исследования) в теории чисел.
С появлением современных компьютеров им (этим двум задачам) были также найдены неожиданные применениями в криптографии с открытым ключом и информационной безопасности. В этой книге мы представим различные методы/алгоритмы тестирования на простоту чисел и целочисленной факторизации и их применений в криптографии с открытым ключом и информационной безопасности. Более конкретно, мы сначала в главе 1 рассмотрим некоторые фундаментальные понятия и результаты из теории чисел. Затем, в главе 2 мы обсудим различные алгоритмы для проверки простоты чисел и генерации простых чисел, акцентируясь на вероятностном тесте Рабина-Миллера, тестах Голдвассера-Килиана и Аткина-Морейна на эллиптических кривых и детерминированном тесте Агравала-Кайяла-Саксены. В этой главе мы также затрагиваем тему генерации больших простых чисел. В главе 3 мы представим различные алгоритмы целочисленной факторизации, в частности, метод эллиптических кривых (ECM), квадратичного решета (QS) и решета числового поля (NFS). Там же мы обсудим некоторые другие вычислительные задачи, которые связаны с разложением на множители, такими как задача о квадратном корне, задача дискретного логарифмирования и задача о квадратичных вычетах. В главе 4 мы обсудим наиболее широко используемые криптографические системы, основанные на вычислительной сложности целочисленной факторизации, извлечения квадратных корней, дискретного логарифмирования, дискретных логарифмов эллиптической кривой и задач квадратичных вычетов.
Я попытался сделать эту книгу настолько автономной насколько возможно, так, чтобы она могла использоваться в качестве учебника для студентов старших курсов и аспирантов первого года обучения, или же в качестве базисного ссылочного материала в рассматриваемой области.
Из Предисловия ко второму изданию
Успех первого издания книги дал мне возможность подготовить ее второе издание. Я воспользовался этой возможностью, чтобы попытаться сделать книгу столь же обновленной и автономной насколько возможно путем включения новых разработок и результатов в этой области. Достойными внимания особенностями нового издания являются появление нескольких новых разделов и увеличение объемв книги на более, чем 100 страниц. Они включают новый раздел в главе 2 относительно сравнения вероятностного теста Рабина-Миллера, теста Аткина-Морейна на эллиптических кривых и детерминированного теста АКС, новый раздел в главе 3 по недавней работе о квантовой факторизации и новый раздел в главе 4 по постквантовой криптографии. Чтобы сделать книгу более подходящей для обучения, в конце каждого раздела были добавлены около десяти задач различного уровня сложности, суммарно всего около 300 задач; большинство из них ориентировано на исследование и сопровождается призами, предлагаемыми за их решение заинтересованными людьми или организациями в общей сумме более чем на пять миллионов долларов США.
Оглавление
Preface to the Second Edition
Preface to the First Edition
1. Number-Theoretic Preliminaries
1.1 Problems in Number Theory
1.2 Groups, Rings and Fields
1.3 Divisibility Properties
1.4 Euclid's Algorithm and Continued Fractions
1.5 Arithmetic Functions σ(n), τ(n), ϕ(n), λ(n), μ(n)
1.6 Linear Congruences
1.7 Quadratic Congruences
1.8 Primitive Roots and Power Residues
1.9 Arithmetic of Elliptic Curves
1.10 Chapter Notes and Further Reading
2. Primality Testing and Prime Generation
2.1 Computing with Numbers and Curves
2.2 Riemann ζ and Dirichlet L Functions
2.3 Rigorous Primality Tests
2.4 Compositeness and Pseudoprimality Tests
2.5 Lucas Pseudoprimality Test
2.6 Elliptic Curve Primality Tests
2.7 Superpolynomial-Time Tests
2.8 Polynomial-Time Tests
2.9 Comparison of General Purpose Primality Tests
2.10 Primality Tests for Special Numbers
2.11 Prime Number Generation
2.12 Chapter Notes and Further Reading
3. Integer Factorization and Discrete Logarithms
3.1 Introduction
3.2 Simple Factoring Methods
3.3 Elliptic Curve Method (ECM)
3.4 General Factoring Congruence
3.5 Continued FRACtion Method (CFRAC)
3.6 Quadratic Sieve (QS)
3.7 Number Field Sieve (NFS
3.8 Quantum Factoring Algorithm
3.9 Discrete Logarithms
3.10 kth Roots
3.11 Elliptic Curve Discrete Logarithms
3.12 Chapter Notes and Further Reading
4. Number-Theoretic Cryptography
4.1 Public-Key Cryptography
4.2 RSA Cryptosystem
4.3 Security and Cryptanalysis of RSA
4.4 Rabin Cryptography
4.5 Quadratic Residuosity Cryptography
4.6 Discrete Logarithm Cryptography
4.7 Elliptic Curve Cryptography
4.8 Zero-Knowledge Techniques
4.9 Deniable Authentication
4.10 Non-Factoring Based Cryptography
4.11 Chapter Notes and Further Reading
Bibliography
Index
About the Author
Простые числа в криптографии и на трекере
