Primality testing for beginners
""How can you tell whether a number is prime? What if the number has hundreds or thousands of digits? This question may seem abstract or irrelevant, but in fact, primality tests are performed every time we make a secure online transaction. In 2002, Agrawal, Kayal, and Saxena answered a long-standing open question in this context by presenting a deterministic test (the AKS algorithm) with polynomial running time that checks whether a number is prime or not. What is more, their methods are essent…
Read More ↓Title Statements
- Full title :Primality testing for beginners / Lasse Rempe-Gillen, Rebecca Waldecker.
Summary
""How can you tell whether a number is prime? What if the number has hundreds or thousands of digits? This question may seem abstract or irrelevant, but in fact, primality tests are performed every time we make a secure online transaction. In 2002, Agrawal, Kayal, and Saxena answered a long-standing open question in this context by presenting a deterministic test (the AKS algorithm) with polynomial running time that checks whether a number is prime or not. What is more, their methods are essentially elementary, providing us with a unique opportunity to give a complete explanation of a current mathematical breakthrough to a wide audience.""--Publisher's description.
Read More ↓Edition Statements
- Publication Date:2014
Publication Statements
- Publisher(s):American mathematical Society
- Place of Publication:Providence, Rhode Island
- Language:eng
- Publication Date:2014
Notes
Translation of: Primzahltests für Einsteiger : Zahlentheorie - Algorithmik - Kryptographie.
The Physical Object
- Description:xii, 244 pages ; : 22 cm.
Edition Identifiers
- ISBN:9780821898833, 0821898833
- oclc:ocn855858285
- LC Classification:QA241
- Dewey Decimal:512.7/2
Table of Contents
ch. 1 Natural numbers and primes -- 1.1. The natural numbers -- 1.2. Divisibility and primes -- 1.3. Prime factor decomposition -- 1.4. The Euclidean algorithm -- 1.5. The Sieve of Eratosthenes -- 1.6. There are infinitely many primes -- Further reading -- ch. 2 Algorithms and complexity -- 2.1. Algorithms -- 2.2. Decidable and undecidable problems -- 2.3.Complexity of algorithms and the class P -- 2.4. The class NP -- 2.5. Randomized algorithms -- Further reading -- ch. 3 Foundations of number theory -- 3.1. Modular arithmetic -- 3.2. Fermat's Little Theorem -- 3.3.A first primality test -- 3.4. Polynomials -- 3.5. Polynomials and modular arithmetic -- Further reading -- ch. 4 Prime numbers and cryptography -- 4.1. Cryptography -- 4.2. RSA -- 4.3. Distribution of primes -- 4.4. Proof of the weak prime number theorem -- 4.5. Randomized primality tests -- Further reading -- ch. 5 The starting point: Fermat for polynomials -- 5.1.A generalization of Fermat's Theorem -- 5.2. The idea of the AKS algorithm -- 5.3. The Agrawal-Biswas test -- ch. 6 The theorem of Agrawal, Kayal, and Saxena -- 6.1. Statement of the theorem -- 6.2. The idea of the proof -- 6.3. The number of polynomials in…
Read More ↓Subjects
Writers
More from this Series
No reviews yet. Be the first to rate this work.
Related Works
more →
Advances in applied analysis
Number Theory Meets Wireless Communications
Kvant selecta: algebra and analysis, 2
Analytic number theory
Files & Downloads
-
Primality testing for beginners -- (.pdf)
PDF · 1.8 MB · updated -
Notices of the American Mathematical Society -- (…
PDF · 47.5 MB · updated -
Notices of the American Mathematical Society -- (…
PDF · 87.8 MB · updated
Rate & Review