Lecture on number theory and cryptography

This book is devoted to the relationship between number theory and cryptography. It is not necessary to know algebra and number theory to understand the problems discussed in it. Here you can find definitions of all necessary concepts and proofs of many simple assertions. The lecture is conducted in an accessible and interesting way, with many well-chosen examples. At the end of each chapter there are exercises to check the acquired messages, and at the end of the book - correct answers to them.

Table of Contents

Preface
Preface to the second edition
From the translator

Chapter 1. Several issues of elementary number theory

1.1. Estimate the time of performing arithmetic operations
1.2. Divisibility and Euclid's algorithm
1.3. congruences
1.4. Applications to the problem of decomposition into factors

Chapter 2. Finite bodies and square residues

2.1. The bodies are over
2.2. Square residues and the law of reciprocity

Chapter 3. Cryptography

3.1. Simple cryptographic systems
3.2. Cipher matrices

Chapter 4. Public keys

4.1. The idea of systems with a public key
4.2. RSA system
4.3. Discrete logarithm
4.4. Packing the backpack
4.5. Reports on zero knowledge and indistinguishable messages

Chapter 5. Prime numbers and distribution on factors

5.1. Numbers pseudo-first
5.2. Method p
5.3. Fermat factoring method and distribution base
5.4. Factorization using chain fractions
5.5. Square screen method

Chapter 6. Elliptic curves

6.1. Basic concepts
6.2. Cryptographic systems that use elliptic curves
6.3. The test of primacy in which elliptic curves are used
6.4. Decomposition into factors using elliptic curves

Answers to exercises
Index