**Student Mathematical Library**

Volume: 70;
2014;
244 pp;
Softcover

MSC: Primary 11;

Print ISBN: 978-0-8218-9883-3

Product Code: STML/70

List Price: $45.00

Individual Price: $36.00

**Electronic ISBN: 978-1-4704-1445-0
Product Code: STML/70.E**

List Price: $45.00

Individual Price: $36.00

#### You may also like

#### Supplemental Materials

# Primality Testing for Beginners

Share this page
*Lasse Rempe-Gillen; Rebecca Waldecker*

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.

Rempe-Gillen and Waldecker introduce the aspects of number theory,
algorithm theory, and cryptography that are relevant for the AKS
algorithm and explain in detail why and how this test works. This book
is specifically designed to make the reader familiar with the
background that is necessary to appreciate the AKS algorithm and
begins at a level that is suitable for secondary school students,
teachers, and interested amateurs. Throughout the book, the reader
becomes involved in the topic by means of numerous exercises.

#### Table of Contents

# Table of Contents

## Primality Testing for Beginners

- Cover Cover11 free
- Title page iii4 free
- Contents vii8 free
- Preface xi12 free
- Introduction 114 free
- Part I. Foundations 1124 free
- Natural numbers and primes 1326
- Algorithms and complexity 4356
- Foundations of number theory 8396
- Prime numbers and cryptography 129142
- Part II. The AKS algorithm 151164
- The starting point: Fermat for polynomials 153166
- The theorem for Agrawal, Kayal, and Saxena 169182
- The algorithm 183196
- Open questions 193206
- Solutions and comments to important exercises 207220
- Bibliography 233246
- List of symbols 237250
- Index 239252 free
- Back Cover Back Cover1258

#### Readership

Undergraduate students interested in number theory, cryptography, and computer science.