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:

  1. addition
  2. subtraction
  3. duplication, and
  4. 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.


Consider computing ab, the length of it will be log(ab) = 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, [ab mod N], the size of it will be at most N. Obviously, it does not make sense to first compute ab 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 = 2k for simplicity. The preceding algorithm roughly correspond to computing a^2k โŸน ((a2)2...)2. This will give us a much better algorithm (k-1 squarings) than the former one (2k-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 xb mod N]. An example:

27          # a = 2, b = 7, t = 1
= 26 * 2    # a = 2, b = 6, t = 2
= 43 * 2    # a = 4, b = 3, t = 2
= 42 * 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.


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 ร— k1, b = c ร— k2
โŸน a ยฑ b = c ร— k1 ยฑ c ร— k2 = c ร— (k1 ยฑ k2)

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 a1 and a2 have the same remainder when divided by b if and only if a1 - a2 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:

  1. There is an identity e โˆˆ G, such that e โ—‹ g = g for g โˆˆ G.
  2. Every g โˆˆ G has an inverse h โˆˆ G such that g โ—‹ h = e.
  3. Associativity. For all f, g, h โˆˆ G, f โ—‹ (g โ—‹ h) = (f โ—‹ g) โ—‹ h.
  4. 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 additivelyWritten multiplicatively
h โ—‹ gh + gh * g
identity element e01
inverse element of g-gg-1
(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)

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

  1. 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.
  2. 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: ZN = {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.

Inverse of a[-a mod N]
Exponentiationm * a = a + ... + a mod N

Multiplication Modulo N

However, ZN = {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.

Closurea and b are invertible modulo N,
a * b is also invertible modulo N.
Inverse[a-1 mod N]
Exponentiationam = 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 gm = 1 (identity element).

Fermat’s Little Theorem

For example:

  1. For group ZN: {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).
  2. 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 gx = 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 gx = gq*m+r = (gm)q * gr = gr.

Another Corollary

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

Proof: fd(fe(g)) = (ge)d = ged = g[ed mod m] = g1 = g.

My Certificate

For more on Number Theory and Group Theory, please refer to the wonderful course here

Related Quick Recap

I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at

Don't forget to sign up newsletter, don't miss any chance to learn.

Or share what you've learned with friends!

Leave a Reply

Your email address will not be published. Required fields are marked *