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.

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.

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)

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)

Calculating inverse numbers in ZN

Inverse numbers in ZN can be determined in time O(log2N) using the , 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).

To find the greatest common divisor of two numbers a and b (where a > b) using the Euclidean algorithm, one should divide a by b, and write the result as a quotient and a remainder:
a / b = q1 + r1

Then, one should perform next division, in which b fulfils the role of a and r1 fulfils the role of b:
b / r1 = q2 + r2

The steps should be repeated analogously:
r1 / r2 = q3 + r3
… …
until receiving the remainder that equals to zero.

The last non-zero remainder is the greatest common divisor of numbers a and b.

It can be proved that the Euclidean algorithm works in time that is proportional to the size of the bigger number: O(log2a).