Crypto-IT

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 Z_N be a set of all non-negative integers that are smaller than N:
Z_N = {0,1,2,...,N-1}

where:

N is a positive integer,
if N is a prime, it will be denoted p (and the whole set as Z_p).

To determine the value of an integer for a modulus N, one should divide this number by N. Its value in Z_N 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 Z_N is a number y in Z_N, that satisfies the equation:
x · y = 1 (in Z_N)

where:

y is denoted x^-1

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

Theorem A number x is invertible in Z_N 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 Z_N allows solving linear equations in modular arithmetic:
the equation: a · x + b = 0 (in Z_N)
has the solution: x = -b · a^-1 (in Z_N)

Definition The symbol Z^*_N denotes a set of all elements of Z_N that are invertible in Z_N; that means the set of numbers x that belong to Z_N, and x and N are relatively prime.

for example for a prime number p:
Z^*_p = Z_p \ {0} = {1, 2, …, p - 1}

Calculating inverse numbers in Z_N

Inverse numbers in Z_N can be determined in time O(log₂N) 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 Z_a)
Thus, b is the inverse number of y in Z_a.

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:
a_i = a_i-2 - q_i-1·a_i-1
b_i = b_i-2 - q_i-1·b_i-1

If algorithm's steps are numbered from 1, one should assume the following initial values of the coefficients:
    a_-1 = 1
    a₀ = 0
    b_-1 = 0
    b₀ = 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).

Date: 2020-03-09