Modular Arithmetic (Clock Arithmetic)

Modular arithmetic is a system of arithmetic for integers, where values reset to zero and begin to increase again, after reaching a certain predefined value, called the modulus (modulo). Modular arithmetic is widely used in computer science and cryptography.

Definition Let ZN be a set of all non-negative integers that are smaller than N:
    ZN = {0,1,2,...,N-1}
  • N is a positive integer,
  • if N is a prime, it will be denoted p (and the whole set as Zp).

To determine the value of an integer for a modulus N, one should divide this number by N. Its value in ZN is equal to the remainder of the division. In modular arithmetic, it is possible to define all typical operations, as in normal arithmetic. They work as one may expect. It is possible to use the same commutative, associative, and distributive laws.

Modular inversion

Integers in modular arithmetic may (but not must) have inverse numbers.

Definition The inverse of x in ZN is a number y in ZN, that satisfies the equation:
    x · y = 1 (in ZN)
  • y is denoted x-1

For example, if N is an odd number, then the inverse of 2 in ZN is (N+1)/2:
    x · (N+1)/2 = N + 1 = 1 (in ZN)

Theorem A number x is invertible in ZN if and only if the numbers x and N are relatively prime.
  • The theorem can be proved using the fact that it is possible to present the greatest common divisor of two integers as a sum of two products each of the numbers and another properly selected integer:
        a·x + b·y = gcd(x,y)

Determining inverse numbers in ZN allows solving linear equations in modular arithmetic:
    the equation:   a · x + b = 0 (in ZN)
    has the solution:   x = -b · a-1 (in ZN)

Definition The symbol Z*N denotes a set of all elements of ZN that are invertible in ZN; that means the set of numbers x that belong to ZN, and x and N are relatively prime.
  • for example for a prime number p:
        Z*p  =  Zp \ {0} = {1, 2, …, p - 1}

Calculating inverse numbers in ZN

Inverse numbers in ZN can be determined in time O(log2N) using the Euclidean algorithm, which allows to compute the greatest common divisor of two integers.

Extended Euclidean algorithm finds the coefficients of Bézout's identity, that are integer numbers a and b such that:
    a·x + b·y = gcd(x,y)

In order to receive the inverse number, one should perform the following transformations:
    a·x + b·y = 1
    b·y = 1 (in Za)
Thus, b is the inverse number of y in Za.

The numbers a and b should be calculated during each step of the Euclidean algorithm, using the received values of those numbers in previous steps and the quotients:
    ai = ai-2 - qi-1·ai-1
    bi = bi-2 - qi-1·bi-1

If algorithm's steps are numbered from 1, one should assume the following initial values of the coefficients:
    a-1 = 1
    a0 = 0
    b-1 = 0
    b0 = 1

The final values of the coefficients a and b are received in the same step when the greatest common divisor of x and y is calculated (thus, in the step with the last non-zero remainder).