Chapter 9Computational Number Theory9.1 The basic groupsWe let Z = {. . . , −2, −1, 0, 1, 2, . . .} denote the set of integers. We let Z+= {1, 2, . . .} denote theset of positive integers and N = {0, 1, 2, . . .} the set of non-negative integers.9.1.1 Integers mod NIf a, b are integers, not both zero, then their greatest common divisor, denoted gcd(a, b), is thelargest integer d such that d divides a and d divides b. If gcd(a, b) = 1 then we say that a and bare relatively prime. If a, N are integers with N > 0 then there are unique integers r, q s uch thata = Nq + r and 0 ≤ r < N. We call r the remainder upon division of a by N, and den ote it bya mod N. We note that the operation a mod N is defined for both negative and non-negative valuesof a, but only for positive values of N. (When a is negative, the quotient q will also be negative,but the remainder r must always be in the in dicated range 0 ≤ r < N.) If a, b are any integersand N is a positive integer, we write a ≡ b (mod N) if a mod N = b mod N. We associate to anypositive integer N the following two sets:ZN= {0, 1, . . . , N − 1}Z∗N= { i ∈ Z : 1 ≤ i ≤ N − 1 and gcd(i, N) = 1 }The first set is called the set of integers mod N. Its size is N, and it contains exactly the integersthat are possible values of a mod N as a ranges over Z. We define the Euler Phi (or totient)function ϕ: Z+→ N by ϕ(N) = |Z∗N| for all N ∈ Z+. That is, ϕ(N) is the size of the set Z∗N.9.1.2 GroupsLet G be a non-empty set, and let · be a binary operation on G. This means that for every twopoints a, b ∈ G, a value a · b is defined.Definition 9.1.1 Let G be a non-empty s et and let · denote a binary operation on G. We saythat G is a group if it has the following properties:1. Closure: For every a, b ∈ G it is the case that a · b is also in G.2 COMPUTATIONAL NUMBER THEORY2. Associativity: For every a, b, c ∈ G it is the case that (a · b) · c = a · (b · c).3. Identity: There exists an element 1 ∈ G such th at a · 1 = 1 · a = a for all a ∈ G.4. Invertibility: For every a ∈ G there exists a unique b ∈ G such that a · b = b · a = 1.The element b in the invertibility condition is referred to as the inverse of the element a, and isdenoted a−1.We n ow return to the sets we defined above and remark on their group structure. Let N be apositive integer. The operation of addition modulo N takes input any two integers a, b and returns(a + b) mod N. The operation of multiplication modulo N takes inp ut any two integers a, b andreturns ab mod N.Fact 9.1.2 Let N be a positive integer. Then ZNis a group under addition modulo N, and Z∗Nis a group under multiplication modulo N.In ZN, the identity element is 0 and the inverse of a is −a mod N = N − a. In Z∗N, the identityelement is 1 and the inverse of a is a b ∈ Z∗Nsuch that ab ≡ 1 (mod N ). In may not be obviouswhy such a b even exists, but it does. We do not prove the above fact here.In any group, we can define an exponentiation operation which associates to any a ∈ G andany integer i a group element we denote ai, defined as follows. If i = 0 then aiis defined to be 1,the identity element of the group. If i > 0 thenai= a · a · · · a| {z }i.If i is negative, then we define ai= (a−1)−i. Put another way, let j = −i, which is positive, andsetai= a−1· a−1· · · a−1| {z }j.With these definitions in place, we can manipulate exponents in the way in which we are accustomedwith ordinary numbers. Namely, identities such as the following hold for all a ∈ G and all i, j ∈ Z:ai+j= ai· aj(ai)j= aija−i= (ai)−1a−i= (a−1)i.We will use this type of manipulation frequently without explicit explanation.It is customary in group theory to call the size of a group G its order. That is, the order of agroup G is |G|, the number of elements in it. We will often make use of the following basic fact.It says that if any group element is raised to the power the order of the group, the result is theidentity element of the group.Fact 9.1.3 Let G be a group and let m = |G| be its order. Then am= 1 for all a ∈ G.This means that computation in the group indices can be d on e modulo m:Prop osition 9.1.4 Let G be a group and let m = |G| be its order. Then ai= ai mod mfor alla ∈ G and all i ∈ Z.Bellare and Rogaway 3We leave it to the reader to prove that this follows from Fact 9.1.3.Example 9.1.5 Let us work in the group Z∗21under the operation of multiplication modulo 21.The members of this group are 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20, so the order of the group ism = 12. Suppose we want to compute 586in th is group. Applying the above we have586mod 21 = 586 mod 12mod 21 = 52mod 21 = 25 mod 21 = 4 .If G is a group, a set S ⊆ G is called a subgroup if it is a group in its own r ight, under the sameoperation as that under which G is a group. If we already know that G is a group, there is a simpleway to test whether S is a subgroup: it is one if an d only if x · y−1∈ S for all x, y ∈ S. Here y−1is the inverse of y in G.Fact 9.1.6 Let G be a group and let S be a subgroup of G. Then the order of S divides the orderof G.9.2 AlgorithmsFig. 9.1 sum marizes some basic algorithms involving numbers. These algorithms are used to im-plement public-key cryptosystems, and thus their run ning time is an important concern. We beginwith a discussion about the manner in which running time is measured, and then go on to discussthe algorithms, s ome very briefly, some in more d ep th .9.2.1 Bit operations and binary lengthIn a course or text on algorithms, we learn to analyze the running time of an algorithm as a functionof the size of its inpu t. T he inputs are typically things like graphs, or arr ays, and the measureof input size might be the number of nodes in …