Chapter 04 - Number Theory and Cryptography

Number Theory and Cryptography

The part of mathematics devoted to the study of the set of integers and their properties is known as number theory.

Divisibility and Modular Arithmetic

Division of an integer by a positive integer produces a quotient and a remainder.

Division

• Definition : If and are integers with , we say that divides if there is an integer such that (or equivalently, if is an integer). When divides we say that is a factor or divisor of , and that is a multiple of . The notation denotes that divides . We write when does not divide .
• Theorem : Let and be integers, where . Then (I) if and , then ; (II) if , then for all integers ; (III) if and , then .

The Division Algorithm

• THE DIVISION ALGORITHM : Let be an integer and a positive integer. Then there are unique integers and , with such that .

In the equality given in the division algorithm, is called the divisor, is called the dividend, is called the quotient, and is called the remainder. This notation is used to express the quotient and remainder:

• div mod .

Modular Arithmetic

• Definition : If and are integers and is a positive integer, then is congruent to modulo if divides . We use the notation (mod ) to indicate that is congruent to modulo m. We say that (mod ) is a congruence and that is its modulus (plural moduli). If and are not congruent modulo , we write (mod ).
• Theorem : Let and be integers, and let be a positive integer. Then (mod ) if and only if mod mod .

The great German mathematician Karl F. Gauss developed the concept of congruences at the end of the eighteenth century. The notion of congruences has played an important role in the development of number theory.

• Theorem : Let be a positive integer. The integers and are congruent modulo if and only if there is an integer such that .

The set of all integers congruent to an integer modulo is called the congruence class of modulo . Furthermore, we will show that there are pairwise disjoint equivalence classes modulo and that the union of these equivalence classes is the set of integers.

• Theorem : Let be a positive integer. If (mod ) and (mod ), then (mod ) and (mod ).
• Corollary : Let be a positive integer and let and be integers. Then

Arithmetic Modulo

We can define arithmetic operations on , the set of non-negative integers less than , that is, the set . In particular, we define addition of these integers, denoted by by where the addition on the right-hand side of this equation is the ordinary addition of integers, and we define multiplication of these integers, denoted by bywhere the multiplication on the right-hand side of this equation is the ordinary multiplication of integers. The operations and are called addition and multiplication modulo m and when we use these operations, we are said to be doing arithmetic modulo m.

Integer Representations and Algorithms

Representations of Integers

In everyday life we use decimal notation to express integers. In decimal notation, an integer is written as a sum of the form where is an integer with for .

• Theorem (Base expansion of ) : Let be an integer greater than 1. Then if is a positive integer, it can be expressed uniquely in the form where is a non-negative integer, are non-negative integers less than , and .

Base Conversion

First, divide by to obtain a quotient and remainder, that is, . The remainder, , is the rightmost digit in the base expansion of . Next, divide by to obtain . We see that is the second digit from the right in the base expansion of . Continue this process, successively dividing the quotients by , obtaining additional base digits as the remainders. This process terminates when we obtain a quotient equal to zero. It produces the base digits of from the right to the left.

• Algorithm : Constructing Base Expansions procedure base expansion(: positive integers with ) while mod div return () { is the expansion of }

Algorithms for Integer Operations

The algorithms for performing operations with integers using their binary expansions are extremely important in computer arithmetic.

Addition Algorithm

• Algorithm : Addition of Integers. procedure add( : positive integers) { and are and respectively} for to return {the binary expansion of the sum is }

Multiplication Algorithm

• Algorithm : Multiplication of Integers. procedure multiply( : positive integers) { and are and respectively} for to if then shifted places else are partial products for to return { is the value of }

Algorithm for and

• Algorithm : Computing div and mod. procedure division algorithm( : integer, : positive integer) while if and then return { is the quotient, is the remainder}

Modular Exponentiation

In cryptography it is important to be able to find mod efficiently without using an excessive amount of memory, where and are large integers. It is impractical to first compute and then find its remainder when divided by , because can be a huge number and we will need a huge amount of computer memory to store such numbers. To motivate the fast modular exponentiation algorithm, we illustrate its basic idea. We will explain how to use the binary expansion of , say to compute . First, note that This shows that to compute , we need only compute the values of . Once we have these values, we multiply the terms in this list, where . This gives us .

• Algorithm : Fast Modular Exponentiation. procedure modular exponentiation(: integer, : positive integers) mod for to if then mod mod return { equals mod }

Primes and Greatest Common Divisors

Primes have become essential in modern cryptographic systems, and we will develop some of their properties important in cryptography. For example, finding large primes is essential in modern cryptography. The length of time required to factor large integers into their prime factors is the basis for the strength of some important modern cryptographic systems.

Primes

• Definition : An integer greater than is called prime if the only positive factors of are and . A positive integer that is greater than 1 and is not prime is called composite.

An integer is composite if and only if there exists an integer such that and .

• Theorem : The Fundamental Theorem Of Arithmetic Every integer greater than 1 can be written uniquely as a prime or as the product of two or more primes, where the prime factors are written in order of non-decreasing size.
• Theorem : If is a composite integer, then has a prime divisor less than or equal to .

Because there are infinitely many primes, given any positive integer there are primes greater than this integer. For almost all the last 300 years, the largest prime known has been an integer of the special form where is also prime. Such primes are called Mersenne primes. The reason that the largest known prime has usually been a Mersenne prime is that there is an extremely efficient test, known as the Lucas-Lehmer test, for determining whether is prime.

• Theorem : The Prime Number Theorem The ratio of the number of primes not exceeding , and approaches as grows without bound. (Here is the natural logarithm of .)

Greatest Common Divisors and Least Common Multiples

• Definition : Let and be integers, not both zero. The largest integer such that and is called the greatest common divisor of and . The greatest common divisor of and is denoted by gcd.
• Definition : The integers and are relatively prime if their greatest common divisor is .
• Definition : The integers are pairwise relatively prime if gcd whenever .

Another way to find the greatest common divisor of two positive integers is to use the prime factorizations of these integers. Suppose that the prime factorizations of the positive integers and are where each exponent is a non-negative integer, and where all primes occurring in the prime factorization of either or are included in both factorizations, with zero exponents if necessary. Then gcd is given by where represents the minimum of the two numbers and .

• Definition : The least common multiple of the positive integers and is the smallest positive integer that is divisible by both and . The least common multiple of and is denoted by lcm.
• Theorem : Let and be positive integers. Then .

The greatest common divisor of two integers and can be expressed in the form where and are integers. In other words, gcd can be expressed as a linear combination with integer coefficients of and .

• **Bézout’s Theorem : If and are positive integers, then there exist integers and such that gcd.
• Definition : If and are positive integers, then integers and such that gcd are called Bézout Coefficients of and . Also, the equation gcd is called Bézout’s Identity.
• Theorem : Let be a positive integer and let and be integers. If (mod ) and gcd then (mod ).

Solving Congruences

Linear Congruences

A congruence of the form (mod ), where is a positive integer, and are integers, and is a variable, is called a linear congruence.

• Theorem : If and are relatively prime integers and then an inverse of modulo exists. Furthermore, this inverse is unique modulo . (That is, there is a unique positive integer less than that is an inverse of modulo and every other inverse of modulo m is congruent to modulo .)

• Theorem : The Chinese Remainder Theorem Let be pairwise relatively prime positive integers greater than one and arbitrary integers. Then the system has a unique solution modulo . (There is a solution with and all other solutions are congruent modulo to this solution.)

Fermat’s Little Theorem

• Theorem : Fermat’s Little Theorem If is prime and is an integer not divisible by , then (mod ). Furthermore, for every integer we have (mod ).
• Definition : Let be a positive integer. If is a composite positive integer, and (mod ), then is called a pseudo-prime to the base .
• Definition : A composite integer that satisfies the congruence (mod ) for all positive integers with gcd is called a Carmichael number.

Primitive Roots and Discrete Logarithms

In the set of positive real numbers, if and we say that is the logarithm of to the base .

• Definition : A primitive root modulo a prime is an integer in such that every nonzero element of is a power of .
• Definition : Suppose that is a prime, is a primitive root modulo , and is an integer between and inclusive. If mod and we say that is the discrete logarithm of modulo to the base and we write (where the prime is understood).

Applications Of Congruences

Hashing Functions

A hashing function assigns memory location to the record that has as its key. One of the most common is the function mod where is the number of available memory locations. Hashing functions should be easily evaluated so that files can be quickly located. The hashing function mod meets this requirement; to find , we need only compute the remainder when is divided by . Furthermore, the hashing function should be onto, so that all memory locations are possible. The function mod also satisfies this property.

Pseudo-random Numbers

The numbers generated by systematic methods are not truly random, they are called pseudorandom numbers. The most commonly used procedure for generating pseudorandom numbers is the linear congruential method. We choose four integers: the modulus , multiplier , increment , and seed , with and We generate a sequence of pseudorandom numbers {}, with for all , by successively using the recursively defined function mod .