Chapter 6. Number Theory

6.1 Introduction

Problems such as factorization or primality of large integers, root extraction, solution to simultaneous equations modulo different moduli, etc., are among the frequently used ingredients in modern cryptography. They are also fascinating topics in the theory of numbers. In this chapter we study some basic facts and algorithms in number theory, which have important relevance to modern cryptography.

6.1.1 Chapter Outline

§6.2 introduces the basic notions and operations of congruences and residue classes. §6.3 introduces Euler’s phi function. §6.4 shows a unified view of the theorems of Fermat, Euler and Lagrange. §6.5 introduces the notion of quadratic residues. §6.6 introduces algorithms for computing ...

Get Modern Cryptography: Theory and Practice now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.