Modular Arithmetic: Applications In Real Life
Modular Arithmetic: Applications In Real Life
Modular arithmetic is made use of in number theory, group theory, ring theory, knot theory, abstract algebra, computer algebra, cryptography, computer science, chemistry and the visual and musical arts. It is one of the bases of number theory, covering nearly every facet of its study, and makes available major instances for group theory, ring theory and abstract algebra.
Modular arithmetic is frequently used to compute checksums that are used within identifiers. International Bank Account Numbers (IBANs), for instance, make use of modulo 97 arithmetic to obtain user input errors in bank account numbers. In cryptography, modular arithmetic unswervingly underpins public key systems like RSA and Diffie-Hellman, in addition to making available finite fields which trigger elliptic curves, and is used in a variety of symmetric key algorithms which includes AES, IDEA, and RC4.
In computer algebra, modular arithmetic is mainly used to limit the size of integer coefficients in midway calculations and data. It is made use of in polynomial factorization, a problem for which every known effective algorithms make use of modular arithmetic. It is being made use of by the most effective implementations of polynomial greatest common divisor, precise linear algebra and Gröbner basis algorithms over the integers and the rational numbers.
In computer science, modular arithmetic is frequently applied in bitwise operations and other operations involving fixed-width, cyclic data structures. The modulo operation, as carried out in various programming languages and calculators, is an application of modular arithmetic that is being frequently made use of. XOR is the sum of 2 bits, modulo 2.
In chemistry, the last digit of the CAS registry number (a number which is specific for every chemical compound) is a check digit, which is calculated by using the last digit of the first two parts of the CAS registry number multiplied by 1, the next digit multiplied by 2, the next digit multiplied by 3 and so on, adding all these up and computing the sum modulo 10.
In music, arithmetic modulo 12 is being made use of in the consideration of the system of twelve-tone equal temperament, where octave and enharmonic equivalency takes place (that is, pitches in a 1∶2 or 2∶1 ratio are equivalent, and C-sharp is taken to be equivalent as D-flat).
The method of casting out nines provides a quick check of decimal arithmetic calculations carried out by hand. It is based on modular arithmetic modulo 9, and particularly on the significant property that 10 ≡ 1 (mod 9).
Arithmetic modulo 7 is made use of in algorithms that determine the day of the week for a given date. In particular, Zeller's congruence and the doomsday algorithm make significant use of modulo-7 arithmetic.
More commonly, modular arithmetic as well has application in disciplines like law ( like in apportionment), economics, (as in the game theory) and other areas of the social sciences, where proportional division and allocation of resources plays a major role as part of the analysis.
Calculation complication
Since modular arithmetic has such a broad range of applications, it is crucial to know how hard it is to compute a system of congruences. A linear system of congruences can be solved in polynomial time with a type of Gaussian elimination. Algorithms, like Montgomery reduction, is as well present to permit simple arithmetic operations, like multiplication and exponentiation modulo n, to be carried out effectively on large numbers. Computing a system of non-linear modular arithmetic equations is NP-complete
Example implementations
Below are two realistically fast C functions for carrying out modular multiplication on unsigned integers not bigger than 63 bits, without overflow of the temporary operations. An algorithmic way to compute a * b (mod m):
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
uint64_t d = 0, mp2 = m >> 1;
int i;
if (a >= m) a %= m;
if (b >= m) b %= m;
for (i = 0; i < 64; ++i)
{
d = (d > mp2) ? (d << 1) - m : d << 1;
if (a & 0x8000000000000000ULL)
d += b;
if (d > m) d -= m;
a <= 1;
}
return d%m;
}
On computer architectures where an extended precision format with at least 64 bits of mantissa is available (like the long double type of most x86 C compilers), the following routine is faster than any algorithmic solution, by employing the trick that, by hardware, floating-point multiplication leads to the most crucial bits of the product kept, while integer multiplication leads to the smallest significant bits kept:
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
long double x;
uint64_t c;
int64_t r;
if (a >= m) a %= m;
if (b >= m) b %= m;
x = a;
c = x * b / m;
r = (int64_t)(a * b - c * m) % (int64_t)m;
return r < 0 ? r + m : r;
}
Congruence relation
Modular arithmetic can be carried out mathematically by introducing a congruence relation on the integers that is compatible with the operations on integers: addition, subtraction, and multiplication. For a positive integer n, two integers a and b are said to be congruent modulo n, written:
a≅n(mod n,)
if their difference a − b is an integer multiple of n (or n divides a − b). The number n is known as the modulus of the congruence.
For instance,
38≅14(mod 12)
Due to the fact that 38 − 14 = 24, which is a multiple of 12.
The same rule holds for negative values:
-8≅7(mmod 5)
2≅-3(mod 5)
-3≅-8(mod 5)
In the same way, a≅b(mod n) can as well be thought of as asserting that the remainders of the division of both a and b by n are the same. For example:
38≅14(mod 12)
Due to the fact that both 38 and 14 possess the same remainder 2 when divided by 12. It is as well the case that 38-14=24is an integer multiple of 12, which agrees with the earlier definition of the congruence relation.
Note: Due to the fact that it is common to consider a lot of congruence relations for various moduli at the same time, the modulus is integrated in the notation. Despite the ternary notation, the congruence relation for a given modulus is binary. This would have been clearer if the notation a ≅n b had been made use of, rather than the common traditional notation.
The characteristics that make this relation a congruence relation (with respect to addition, subtraction, and multiplication) are as follows.
If
a1≅b1(mod n)
and
a2≅b2(mod n)
then:
a1+a2≅b2+b2
a1-a2≅b2-b2
It ought to be observed that the above two properties would still hold if the theory were expanded to include all real numbers, that is if a1, a2, b1, b2, n were not essentially all integers. The next property, though, would fail if these variables were not all integers:
Remainders
The notion of modular arithmetic is connected to that of the remainder in Euclidean division. The operation of finding the remainder is occasionally known as the modulo operation, and represented with "mod" used as an infix operator. For instance, the remainder of the division of 14 by 12 is represented by 14 mod 12; as this remainder is 2, we have 14 mod 12 = 2.
The congruence, shown by "≡" followed by "mod" between parentheses, shows that the operator "mod", applied to both members, produces an equivalent result. That is
is equivalent to
a mod n = B mod n
The basic property of multiplication in modular arithmetic may as a result be written
(a mod n) (B mod n) ≅ab (mod n)
or, in the same vein,
In computer science, it is the remainder operator that is normally shown by either "%" like in C, C++, Java, JavaScript, Perl and Python) or "mod" (for instance, in Pascal, BASIC, SQL, Haskell, ABAP), with exceptions like Excel. These operators are mainly pronounced as "mod", but it is particularly a remainder that is calculated (since in C++ a negative number will be returned if the first argument is negative, and in Python a negative number will be returned if the second argument is negative). The function modulo rather than mod, as in 38 ≡ 14 (modulo 12) is occasionally made use of to indicate the common residue instead of a remainder as in Ruby.
Functional representation of the remainder operation
The remainder operation can be represented with the use of the floor function. If b ≅ a (mod n), where n > 0, then if the remainder b is calculated
where is the largest integer less than or equal to , then
If instead a remainder b in the range −n ≤ b < 0 is needed, or we can say that if a is negative
Residue systems
Every residue class modulo n may be represented by any one of its members, even though we normally represent each residue class by the smallest nonnegative integer which belongs to that class (since this is the actual remainder which results from division). Observe that any two members of varying residue classes modulo n are incongruent modulo n. In addition, every integer belongs to one and only one residue class modulo n.
The set of integers {0, 1, 2, ..., n - 1} is known as the least residue system modulo n. Any set of n integers, no two of which are congruent modulo n, is known as a complete residue system modulo n.
It is evident that the least residue system is a complete residue system, and that a complete residue system is merely a set made up mainly of one representative of every residue class modulo n. The least residue system modulo 4 is {0, 1, 2, 3}. A few other complete residue systems modulo 4 are:
{1,2,3,4}
{13,14,15,16}
{-2,-1,0,1}
{-13,4,17,18}
{-5,0,6,21}
{27,32,37,42}
A few sets which are not complete residue systems modulo 4 are:
{-5,0,6,22} since 6 is congruent to 22 modulo 4.
{5,15} due to the fact that a complete residue system modulo 4 ought to possess precisely 4 incongruent residue classes.
Reduced residue systems
Any set of φ(n) integers that are comparatively prime to n and that are jointly incongruent modulo n, where φ(n) represents Euler's totient function, is known as a reduced residue system modulo n. The example above, {5,15} is an example of a reduced residue system modulo 4.
Congruence classes
As you would obtain in any congruence relation, congruence modulo n is an equivalence relation, and the equivalence class of the integer a. This set, made up of the integers congruent to a modulo n, is known as the congruence class or residue class or merely residue of the integer a, modulo n. When the modulus n is made known from the context, that residue may as well be represented.
The set of all congruence classes of the integers for a modulus n is called the set of integers modulo n, The notation is, nevertheless, not recommended because it can be confused with the set of n-adic integers. The set is defined as follows
1 comment
Great
Post a Comment