The modulo operation is the operation of calculating the rest of the Euclidean division . It is the mathematician Gauss who invented the arithmetic of congruences , in which one is interested in the remains of divisions rather than quotients. The modulo is also called the arithmetic of the clock , because all the modulo 12 numbers are placed on the hours of the clock.
Asymmetric key ciphers employ non-reversible functions that rely on modular arithmetic . The RSA encryption is based on this formula:
for x the number to be encrypted, for the two elements of the public key e and n, y the encryption of x is calculated as follows: y = xe mod n. To decrypt y, with d the private key, the forumla is applied: z = yd mod n … as if by magic, z is equal to x. We really have here an asymmetric entryption because the encryption key (here e and n) is different from the decryption key (here d and n). Of course this can only work if the numbers have properties between them: from p and q two secret primes, we get n = p x q (part of the public key) and f = (p-1)x(q-1). The we choose e (part of the public key) as first with f and compute d (private key) as the inverse of e mod f (e x d = 1 mod f).
why: we constructs with the modulo operation the set of classes of the quotient group of (Z,+) by its subgroup pZ generated by an integer p, denoted Z/pZ : its elements are the integers not divisible by p, considered modulo p, two elements being considered equivalent when their difference is a multipule of p. When p is a prime number, Z/pZ this time provided with multiplication (and deprived of zero), is a group (law of internal composition, associativity, neutral element, symmetry).
We see in this example of prime encryption numbers, magic numbers by excellence (because no formula allows to calculate the nth of them), have provided by their fundamental properties of amazing applications using the function modulo.
Click here to display the animation the psychedelic modulo