Modular Arithmetic and Other Computational Methods
MODULAR ARITHMETIC AND
OTHER COMPUTATIONAL
METHODS
Please see edition equations online at https://www.routledge. com/Behavioral-Cybersecurity-Fundamental-Principles-and-Applications-of-Personality/Patterson-Winston-Proctor/p/ book/9780367509798.
Critical to the understanding of almost all cryptographic methods is an understanding of the study of what are called “modular arithmetic systems.”
Any cryptographic method must ensure that when we perform the encryption step, we must be able to arrive back at the original or plaintext message when we perform the decryption. As an immediate consequence, this implies that representing information in computer memory cannot be interpreted as in the computer context as floating point numbers, or, in mathematical terminology, real or rational numbers. The problem that arises is that interpretation of the result of any computation in computer memory of real or rational numbers leads to an uncertainty in terms of the lowest-order bit or bits of that computation. Therefore, in general, if we were to manipulate real or rational numbers in a cryptographic computation, the fact that the lowest-order bits are indeterminate could mean that no true or exact inversion could be performed.
As a consequence, virtually all cryptosystems use the natural numbers or integers as the basis for computation. Indeed, since computations in the integers might apply an unlimited range, instead we almost always use a smaller, finite, and fully enumerable system derived from the integers that we generally refer to as “modular arithmetic.”
Z[sub(n)] or Arithmetic Modulo n
A standard definition of the integers can be written as Z = { , -2, -1, 0, 1, 2, ) with operations +, x. Of course, this set Z is
infinite, so we derive a finite variant of the integers that we refer to as the “integers modulo n,” written Z„ and defined as
Z_{n} = {0, 1, 2,...,n-l};
and if a and b g Z_{n}, a + b is defined as the remainder of a + b when divided by n, and a x b is defined as the remainder of a x b when divided by n.
A set of elements with a binary operation (such as Z_{n} with +) forms a group G = {a, b, ...} if several conditions are satisfied:
- 1. Closure: If a, b g G, so is a + b.
- 2. Identity: There is a special element called the identity, i, such that a + i = i + a = a, for all a in G.
- 3. Associativity: For all a, b, c g G, a + (b + c) = (a + b) + c.
- 4. Inverse: For all a, there exists some b (that we write b = -a) such that a + b = a + (-a) = i.
In the case of Z_{n} with the + operation, the identity is 0, and all four conditions are satisfied, so Z_{n} with addition forms a group.
In the case of Z„ with the + operation, the identity is 0, and all four conditions are satisfied, so Z„ with addition forms a group.
Let us take an example, first Z_{6}:
Addition in Z_{6}
+ |
0 |
1 |
2 |
3 |
4 |
5 |
0 |
0 |
1 |
2 |
3 |
4 |
5 |
1 |
1 |
2 |
3 |
4 |
5 |
0 |
2 |
2 |
3 |
4 |
5 |
0 |
1 |
3 |
3 |
4 |
5 |
0 |
1 |
2 |
4 |
4 |
5 |
0 |
1 |
2 |
3 |
5 |
5 |
0 |
1 |
2 |
3 |
4 |
Multiplication in Z_{6}
Now consider Z_{7}: Addition
Multiplication
X |
0 |
1 |
2 |
3 |
4 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
2 |
0 |
2 |
4 |
0 |
2 |
4 |
3 |
0 |
3 |
0 |
3 |
0 |
3 |
4 |
0 |
4 |
2 |
0 |
4 |
2 |
5 |
0 |
5 |
4 |
3 |
2 |
1 |
+ |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
0 |
2 |
2 |
3 |
4 |
5 |
6 |
0 |
1 |
3 |
3 |
4 |
5 |
6 |
0 |
1 |
2 |
4 |
4 |
5 |
6 |
0 |
1 |
2 |
3 |
5 |
5 |
6 |
0 |
1 |
2 |
3 |
4 |
OS |
OS |
0 |
1 |
2 |
3 |
4 |
5 |
X |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
2 |
0 |
2 |
4 |
6 |
1 |
3 |
5 |
3 |
0 |
3 |
6 |
2 |
5 |
1 |
4 |
4 |
0 |
4 |
1 |
5 |
2 |
6 |
3 |
5 |
0 |
5 |
3 |
1 |
6 |
4 |
2 |
6 |
0 |
6 |
5 |
4 |
3 |
2 |
1 |
What are the Differences in the Tables?
An element (in any multiplication table) has a multiplicative inverse if there is a 1 in the row corresponding to that element. Elements with multiplicative inverses in Z_{6} are 1 and 5; all nonzero elements in Z_{7} have inverses. The essential difference between 6 and 7 is that 7 is prime and 6 is not.
In general, in a modular arithmetic system based on the number n, if n is a composite number, there will always be some pair of numbers a and b less than n whose product will be 0 in the multiplication table, and in this case, neither a nor b will have an inverse in the multiplication operation in Z_{n}; if, however, the modular system is based on a prime number—let us call it p—then every nonzero element in Z_{p} will have a multiplicative inverse.
The reason, of course, is that in the case that n is composite, if you take two factors of n, a and b, greater than 1, then a x b = n, that is, a x b = 0 (mod n); then you can see from the table that neither a nor b can have a multiplicative inverse.
The result of these observations is that in the case of a prime number p, every nonzero element in the system has an inverse under multiplication. Therefore, the Z_{p} system (omitting the zero in the case of multiplication) contains two group structures, one for addition and one for multiplication. If we can add one other condition (which is indeed satisfied for all n whether prime or composite) called the distributive law relating addition and multiplication, that is a x (b + c) = a x b + a x c for all a, b, and c, then the overall modular system is considered a mathematical field.
Therefore, we can conclude that the modular systems Z_{p} are fields when p is prime, and Z„ are not fields when n is composite.
Prime numbers, again, are those with no proper divisors, for example, 2, 3, 5, ..., 13, 17, ..., 23, 29, ...
For any natural number n, call <|>(n) the Mobius <|)-function. It counts how many numbers between 1 and n are relatively prime to n—that is, have no common factors greater than 1. Clearly, if the number n is a prime, it has no factors greater than 1, so <|>(p) = (p - 1).
In general, for large numbers n, <|>(n) is infeasible to compute. We know that if the number is a prime, p, then <|>(p) = (p - 1). Also, if n is the product of only two primes p and q (n = pq), then <|>(n) = (p - 1) x (q - 1).
There is one extremely important result about the Mobius function that arises many times in cryptography. We will state this without proof, but that can be found in any elementary college algebra book.
For any n, if you construct the mod n system, and for any acn, that is relatively prime to n (alternatively, the greatest common divisor or GCD, of a and n is GCD(a, n) = 1). Then in this case, raising a to the
This is sometimes called the “little Fermat theorem.” (Please see online.)
Finite Fields
This system can also be thought of as the integers Z, Z/(p), which means in this new system, we collapse all the values that have the same remainder mod p.
We saw that if p is a prime, the system Z_{p} has the special property that all nonzero elements have multiplicative inverses; that is, for any a 0, there exists some b for which a x b = 1 (mod p). This system can also be thought of as the integers Z, Z/(p), which means in this new system, we collapse all the values that have the same remainder mod p.
Such an algebraic system mod p with addition and multiplication is called a field. In fact, such a (finite) field can be defined for all prime numbers p.
We can go a little further with finite fields. We can define the system of all polynomials Z_{p}[x] in a single variable, then Z_{p}[x]/(q(x)), where q(x) is an irreducible polynomial of degree n.
The addition and multiplication of polynomials is as usual, except that the coefficients of the polynomials in the system are always modulo p.
So, for example, in the modulo 13 system of polynomials Z_{l3}[x], if we have pl = (3x^{2} + 4x + 2) and p2 = (x^{3} + 5x^{2} + lOx + 5), then
pl + p2 = (3x^{2} + 4x + 2) + (x^{3} + 5x^{2}+10x + 5) = (x^{3} + 8x^{2} + 14x + 7) = (x^{3}+ 8x^{2} + x+ 7)(modl3);
pl x p2 = (3x^{2} + 4x + 2)x (x^{3} + 5x^{2} + lOx + 5) = 3x^{5} + (15 + 4)x^{4}
+ (1 + 20 + 3O)x^{3} + (15 + 40 +10) x^{2} + (20 + 20)x +10
= 3x^{5} +19x^{4} + 51 x^{3} + 65x^{2} + 40x +10
= 3x^{5} + 6x^{4} +12x^{3} + Ox^{2} + x + 10(mod 13).
Irreducible polynomials q(x) are like prime numbers—they cannot be factored (beyond factoring coefficients). By analogy, the system where we collapse polynomials with the same remainder mod q(x) also becomes a field, which we call GF(p, n), the Galois field. Again, p is the mod system for the coefficients, and n indicates the degree of the polynomials—once we divide by q(x), no term will remain with an exponent higher than (n - 1).
Of the GF(p, n), several of the form GF(2,n) are the key components of the current US government standard for data encryption, known as the advanced encryption standard (AES) or Rijndael.
The Main Result Concerning Galois Fields
The theory of these systems was a result developed by Evariste Galois, in the early nineteenth century, stating that all algebraic fields with a finite number of elements can be described as a GF(p, n) (including the fields Z_{p} since they can be thought of as GF(p, 1), that is, dividing by an irreducible polynomial of degree 1 [such as ax + b]).
Furthermore, all of the possible choices for a Galois field of type GF(p, n) are equivalent, and their number of elements is p^{n}.
And a bit about Galois himself: He lived in the early nineteenth century in Paris. He developed these very important results in algebra while a teenager. He was also a political radical and went to prison. Upon his release, his interest in a young woman led to a duel in which he was killed at age 21.
Matrix Algebra or Linear Algebra
A matrix or array is a set of numbers of some type (integers, rational, or real, for example) considered as a rectangular set with a certain number of rows or columns. We say that a matrix is of order m x n if it has m rows and n columns and consequently has m x n elements all together.
Here is an example of a 4 x 3 matrix A with real number values. We usually write a matrix enclosing its values in square brackets. [See “eresources: Equations and Problems” on the Website mentioned at the beginning of the chapter.]
The usual compact notation for A is [a^], where i and j enumerate the elements in the rows and columns, respectively.
Under certain conditions, the operations of the system of the matrix elements can be extended to an operation on the matrices themselves. First, regarding addition, two matrices can only be added if they have the same dimension, m x n. [See “eresources: Equations and Problems” on the Website mentioned at the beginning of the chapter.]
Matrices can also be multiplied. The conditions for being able to do this are if you have A (with m rows and n columns) and B (with n rows and p columns), then A and B can be multiplied to form a matrix C, with C having m rows and p columns. [See “eresources: Equations and Problems” on the Website mentioned at the beginning of the chapter.]
Why is this useful? On the one hand, it provides a useful and compact way of describing an array of values. But on the other hand, perhaps the best example of this notation is how we can use it to translate a system of linear equations into a single matrix equation.
In the special case where you have a set of n linear equations in n unknowns, replacing the set of equations by a single matrix equation AX = B leads to a method of solving the entire system by solving the one matrix equation. Necessarily, because there are n equations in n unknowns, the matrix A is of order n x n, also known as a square matrix (of order n).
Square matrices A have the property that in many cases an inverse A^{-1} can be found. When this is the case, then the inverse matrix can be applied to both sides of the matrix equation, yielding the solution for X. In other words, multiplying both sides by A^{-1} yields A 'AX = X = A 'B, [See “eresources: Equations and Problems” on the Website mentioned at the beginning of the chapter.]
In other words, the solution to the system of equations will result from finding A-l. The exact method for finding this can be found in any book on Linear Algebra, or also in our companion book “Behavioral Cybersecurity”, Patterson and Winston-Proctor, CRC Press. 2019.
Problems
1. Solve the equations (or indicate if there is no solution):
x-^{, =} 2(mod 15) Solution(s):
x^{2 +} x + 1 = 0. (mod 17) Solution(s):
- 2^{10} (mod 18) Solution(s):
- 3'001 (_{mo}j 4oj Solution(s):
- 2. Solve y/x = 17 (mod 29).
Solution(s):_______________________________________________________
3. Consider Z_{21} modular arithmetic, or mod 21 arithmetic. List all of the possibilities for an equation a x b = 0 (mod 21), where neither a nor b is 0 itself.
a. Create the multiplication table for Z_{15}.
b. Solve the following for Z_{l5}:
- 7x8 " _____________________
- 4-' ____________________________________________
- 6-' + (4 x 7-') __________________________________________
- 8^{2} x 4-' __________________________________________
- 3 + 8 ___________________________________
- 6 + 5 ___________________________________
- 4. Square elements in mod systems are interesting. Many nonzero elements in mod systems are not squares. Take as an example Z_{7}. Note that 1, 2, and 4 are squares, because, for example, 6^{2=} 1 (mod 7), 3^{2=}2 (mod 7), and 5^{2=}4 (mod 7). Also, you can show that 3, 5, and 6 are not squares.
- 5. Find all of the (nonzero) squares and nonsquares in mod 12 (or Z|_{2}).
Squares _______________________________________
Nonsquares _______________________________________
6. Display the calculations to find
GCD(8624,1837) =and 1837“' (mod 8624) =
Or check if it doesn’t exist
GCD(89379,21577) =and 21577-' (mod 89379) =
Or check if it doesn’t exist
GCD(438538,218655) = and 218655“' (mod 438538)=Or check if it doesn’t exist
7. Compute
a. 3 + 4 (mod 17) Solution:Or does not
exist____________________
b. 18 + 33 (mod 121) Solution:Or does not
exist____________________
c. 27 + 16 (mod 43) Solution:Or does not
exist____________________
d. 12 + 7 (mod 15) Solution:Or does not
exist____________________
- 8. Calculate the Mobius function for n = 77. Find all the elements in Z_{77} that are not relatively prime to n.
- 9. For each of x = 33,46, 49, 67, find the smallest exponent a for which x^{a}= 1 (mod n).
- 10. Multiply the following matrices (if this is possible):
- 2 3 15
- -2 4 6 0
- 1 0 5
- 2 7 1
- 6 6 2
- 3 8 3