Number Theory and Group Theory

Table of Contents

Number theory studies integers and operation on them. Basics of number theory have natural application, like addition, subtraction, etc. However advanced number theory topic has been praised as a branch of pure mathematics, mathematics for itself. This does not mean the number theory is useless. Things changed dramatically in computer era.

… virtually every theorem in elementary number theory arises in a natural, motivated way in connection with the problem of making computers do high-speed numerical calculations.
Donald Knuth, Computer Scientist

It turns out that number theory is important for high speed numerical calculations and so they’re crucial for computer science. Even more, number theory is vital for the modern cryptography, which dramatically affects our life.

Algorithmic Number Theory

The fact is that the number theory is not really needed for a lot of important cryptographic applications. In particular all of the private key cryptography is based on stream ciphers, block ciphers, hash functions, etc, that can be constructed without any number theory. The number theory is going to be needed for public key cryptography but it is not needed for all of cryptography.

From a mathematician’s point of view, they are often interested in the existence of numbers with certain properties, and less interested in the algorithmic efficiency of determining whether or not some number has a given property.

From a computer scientist’s perspective, we are going to be ultimately interested in implementing cryptography. We have to take care to think about the algorithmic complexity. Efficient algorithms for various computations are critical. Of course, we are always going to be interested in asymptotic complexity, which is usually measured in terms of the input length.

Don’t get confused between the magnitude of an input and its length. For example, the input is an integer a, the magnitude of a is itself. But the length of a is the length of the binary representation, i.e. the log of the magnitude of the integer: ||a|| = log(a).

Easy problems are usually those that can be solved in polynomial time, and hard problems are those that can not be solved in polynomial time.

Quick reminder: [a mod N] is the remainder of a when divided by N. However, a = b mod N means a and b have the same remainder modulo N.

a = b mod N ⟺ [a mod N] = [b mod N]

It won’t be difficult to see that following operations of integers are efficient:

addition
subtraction
duplication, and
division with remainder.

Similarly, we can do modular addition, subtraction, multiplication and reduction, efficiently as well. However modular exponentiation, which is used all the time in cryptography, does not run in polynomial time in a naive algorithm, but with a little bit of cleverness, we can come up with an algorithm that does run in polynomial time.

Exponentiation

Consider computing a^b, the length of it will be log(a^b) = b × ||a||, i.e. the magnitude of b times the length of a. So you can see just writing down the answer can require exponential time in b, because the bits we need to computer the answer is going to be linear in the magnitude of b (rather than the length). So we don’t have any hope of computing integer exponentiation in polynomial time. Fortunately, in cryptography, we don’t need to compute exponentiation.

What we actually need to compute is modular exponentiation, [a^b mod N], the size of it will be at most N. Obviously, it does not make sense to first compute a^b and then reduce it modulo N.

An Inefficient Algorithm

A naive but still inefficient algorithm is to multiple a to the temporary answer ans for b times and reduce modulo N after every multiplication, so the value of temporary answer ans at any point during the computation is going to be in the range of 0 to N-1.

# inefficient
exp(a, b, N) {
  // assume b >= 0
  ans = 1;
  for (i=1; i<=b; i++) {
    ans = [ans * a mod N];
  }
}

This algorithm is inefficient is because the inner loop is going to be running for b times (magnitude), which is not polynomial time. We want an algorithm that runs in polynomial time in the length of b, not in the magnitude of b.

An Efficient Algorithm

Assume b = 2^k for simplicity. The preceding algorithm roughly correspond to computing a^2^k ⟹ ((a²)²...)². This will give us a much better algorithm (k-1 squarings) than the former one (2^k-1 multiplications). k is order of log(b), which means k is order of the length of b. So now we have an algorithm that runs in time linear in the length of b. We can modify this approach even when b is not a power of 2.

# efficient
exp(a, b, N) {
  // assume b >= 0
  x = a, t = 1;
  while (b > 0) {
    if (b is odd) {
      t = [t * x mod N];
      b = b - 1;
    }
    x = [x^2 mod N];
    b = b / 2;
  }
  return t;
}

This algorithm satisfies the following invariant, the correct answer is always [t x^b mod N]. An example:

2⁷          # a = 2, b = 7, t = 1
= 2⁶ * 2    # a = 2, b = 6, t = 2
= 4³ * 2    # a = 4, b = 3, t = 2
= 4² * 8    # a = 4, b = 2, t = 8
= 16 * 8    # a = 16, b = 1, t = 8
= 128       # a = 16, b = 0, t = 128

The value of b is decreased by half, the number of iteration of the inner loop is going to be about log(b), which is linear in the length of b. The overall running time of the algorithm is polynomial in the length of three inputs: a, b, and N.

Divisibility

We have to live with the situation that division is not always possible. Formal definition of divisibility: a is divisible by b (or b divides a) denoted by b | a if there is an integer k such that a = b × k. (Note in this formal notion of divisibility in number theory, we do not forbid divisibility by 0.)

Lemma: if c divides a and c divides b, the c divides a ± b.

a = c × k₁, b = c × k₂
⟹ a ± b = c × k₁ ± c × k₂ = c × (k₁ ± k₂)

Lemma: if b | a, then for any integer c we have b | (a × c).

Division with Remainder

So division is not always possible, we could generalize this notion to be applicable to all numbers a and b. Suppose b is a positive integer, the result of the division of a by b with a remainder is a pair of integers: quotient q and remainder r, such that a = q × b + r, and 0 ≤ r < b.

Lemma: integer a₁ and a₂ have the same remainder when divided by b if and only if a₁ - a₂ is divisible by b.

Group Theory

Groups is a very fundamental and important notion both for mathematics in general and for applications to cryptography. Groups provide a way of reasoning about different objects, that share the same underlying mathematical structure.

Abelian Group

An Abelian group is a set G and a binary operation ○ defined on G, such that:

There is an identity e ∈ G, such that e ○ g = g for g ∈ G.
Every g ∈ G has an inverse h ∈ G such that g ○ h = e.
Associativity. For all f, g, h ∈ G, f ○ (g ○ h) = (f ○ g) ○ h.
Commutativity. For all g, h ∈ G, g ○ h = h ○ g.

Also the order of a finite group G is the number of elements in G. The group operation can be written additively or multiplicatively.

	Written additively	Written multiplicatively
`h ○ g`	`h + g`	`h * g`
identity element e	0	1
inverse element of g	`-g`	`g^-1`
exponentiation (repeated application of the group operation)	`m * a` (This is not a group operation applied to `m` and `a`, but group operation to the group element `a` for `m` times)	`a^m`

In terms of performing computations in groups, we are always going to implicitly assume that, for any groups in the context of cryptography:

It is possible to efficiently recognize what a group element is, and write it as a sequence of bits. It is also possible, given some sequence of bits, to tell whether or not that represents a valid group element.
Group operations can be computed efficiently (polynomial in the length of those strings). This means also that group exponentiation can be computed efficiently. Because some form of multiplication modulo N can be indeed be viewed as a group operation.

Addition Modulo N

An example of group that can be written additively: Z_N = {0, 1, ..., N-1}, which denote the set of elements 0 to N-1 under addition modulo N. In the table below a is a group element.

Identity	0
Inverse of a	`[-a mod N]`
Associativity	obvious
Commutativity	obvious
Order	N
Exponentiation	`m * a = a + ... + a mod N`

Multiplication Modulo N

However, Z_N = {0, 1, ..., N-1} is NOT a group written in the form of multiplication modulo N. The identity element is 1, but 0 won’t have an inverse, because no element in that set when multiplied by 0, is going to give us 1 (the identity). So instead we need to restrict the elements in our set.

Modular inverse is defined as this: b is invertible modulo N if there is an element b^-1, such that b * b^-1 = 1 mod N. If such b^-1 exists, it is unique modulo N. Then we could have the notion “division by b” is equivalent to the notion “multiplication by b^-1“. We can fully characterize these invertible elements by the following theorem:

Theorem: b is invertible modulo N if and only if gcd(b, N) = 1.

This also means not only can we characterize invertibility, but we can efficiently test whether a given element is invertible, and this is a consequence of the fact that gcd (great common divisor) can be computed in polynomial time.

Now if p is prime, then 1, …, p-1 are all invertible modulo p, the greatest common divisor of p and any integer less than p is going to be 1.

If N = p * q, where p and q are distinct primes, then the invertible elements modulo N are going to be the integers from 0 to N-1, that do not share a factor in common with N other than 1, i.e. that are not multiples of p or q. For example: p = 3, q = 7, in the list 1, …, 21:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
⟹ 1 2 4 5 8 10 11 13 16 17 19 20 are invertible elements (Z^*_N)

The set Z^*_N which is defined as the set of invertible elements between 1 and N-1, is indeed a group under multiplication modulo N.

Closure	a and b are invertible modulo N, a * b is also invertible modulo N.
Identity	1
Inverse	`[a^-1 mod N]`
Additivity	obvious
Commutativity	obvious
Exponentiation	a^m = a * a * … * a mod N
Order	`ϕ(N) = \| { a ∈ {1, ..., N-1} : gcd(a, N) = 1 } \|` the number of invertible elements modulo N

If N is prime, ϕ(N) = N-1. If N = p * q, where p and q are distinct primes, ϕ(N) = N-1 - (q-1) - (p-1) = (p-1)(q-1).

Fermat’s Little Theorem

Let G be a finite group of order m, then for any g ∈ G, it holds that g^m = 1 (identity element).
Fermat’s Little Theorem

For example:

For group Z_N: {0, 1, ..., N-1}, we have N * a = 0 mod N under addition modulo N, where a is a group element, and N is an integer (the order of the group).
For group Z^*_N, say: 1 2 4 5 8 10 11 13 16 17 19 20, we have a^φ(N) = 1 mod N, under multiplication modulo N, where a is a group element, and ϕ(N) is the order.of the group.

A Corollary

Let G be a finite group of order m, the for g ∈ G and integer x, it holds that g^x = g^{[x mod m]}. This can be used for efficient computation, by reducing the exponent modulo the group order before computing the exponentiation.

Proof: let x = q * m + r, then g^x = g^q*m+r = (g^m)^q * g^r = g^r.

Another Corollary

Let G be a finite group of order m, for any integer e, define f_e(g) = g^e. If gcd(e, m) = 1, then f_e is a permutation (bijection, one-to-one and onto). Moreover, if d = e^-1 mod m, then f_d is also a permutation and is the inverse of f_e.

Proof: f_d(f_e(g)) = (g^e)^d = g^ed = g^{[ed mod m]} = g¹ = g.

My Certificate

For more on Number Theory and Group Theory, please refer to the wonderful course here https://www.coursera.org/learn/cryptography

My #90 course certificate from Coursera

Related Quick Recap

Message Authentication Codes & Authenticated Encryption

I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai