NTIC Some Theory Behind Cryptography

Chapter 12 Some Theory Behind Cryptography

Cryptography is fun in and of itself. However, there are powerful theoretical issues at play throughout – as evidenced by the ever-increasing number of publications in this area.

🔗

Certainly we can only touch on basic questions in this text, but the reader will be gratified to see how much variety there is even thus restricted. We pick two of the many theoretical questions to address.

How do we find all these big primes, anyway?
How can we be sure it's not so easy to break the codes – such as by factoring big numbers?

🔗

Summary: An Introduction to Cryptography

There are many mathematical issues that arise in analyzing even these basic cryptographic systems – especially ones dealing with primes and composites.

Two impractical, but historically important, sources of new prime numbers are Fermat primes and Mersenne primes.
The road to modern primality testing starts with the notion of Pseudoprimes. It isn't the end of the road, because we still have prime impostors in Subsection 12.2.2.
Hence we dig further into Miller's test for base $a$ , which comes from our observations of how powers work in modular arithmetic.
Finally, in Section 12.4 we see a modern, probabilistic primality test .
Factoring is very important in testing the security of cryptography. We examine some very basic techniques, including The Fermat factorization algorithm.
We see just a bit of more modern methods in Section 12.6, which should prepare you for more advanced ideas.

As always, there are Exercises to practice, but also to understand the theory better.