Author : Brian Raiter
Page : << Previous 2 Next >>
in modulus arithmetic would be expressed as:
27 = 3 (mod 12),
or, in words:
27 is congruent to 3, modulo 12.
(Though note that mathematicians actually use a three-barred version of the equal sign to indicate congruency.) In this case, 12 is the modulus that we are working under, and the equation simply tells us that, under a modulus of 12, 27 and 3 are considered to be the same number. Likewise:
11 + 16 = 3 (mod 12)
reads as:
11 plus 16 is congruent to 3, modulo 12.
Modulus arithmetic is sometimes called clockface arithmetic -- if it's currently 11 o'clock, then 16 hours later it will be 3 o'clock. (Of course, the analogy is less perfect when the modulus is something other than 12.)
An important feature of modulus arithmetic is that you can replace the terms of an addition operation with congruent values, and still get the right answer:
16 = 4 (mod 12), therefore
11 + 16 = 11 + 4 = 3 (mod 12).
Another example:
9835 = 7 (mod 12), and
1176 = 0 (mod 12), therefore
9835 + 1176 = 7 + 0 = 7 (mod 12).
Even better, this trick also works with multiplication:
9835 * 1176 = 7 * 0 = 0 (mod 12)
(and, if we check, we will see that, yes, 9835 * 1176 is 11565960, and 11565960 = 0 (mod 12)).
If our modulus was 10, then modulus arithmetic would be equivalent to ignoring all but the last digit in our numbers:
37 = 7 (mod 10),
287 + 482 = 9 (mod 10), and
895 * 9836 = 0 (mod 10).
And, in a sense, a C program does all of its calculations in modulus arithmetic. Since integer calculations in C are permitted to overflow, the high bits silently falling off into the bit bucket, a C program using 32-bit integers is really doing all of its arithmetic modulo 2^32.
As you might imagine, some calculations that are time-consuming and produce huge numbers become trivial in modulus arithmetic. The ability to reduce values to their remainders before doing the actual calculation keeps the calculations from getting out of hand.
Background, Part III: The Fundamental Theorem of Algebra
The Fundamental Theorem of Algebra states that for every number, there is exactly one way to factor that number into primes -- and vice versa: every selection of primes multiplies into a different number. For example:
1176 = 2 * 2 * 2 * 3 * 7 * 7, or
1176 = 2^3 * 3^1 * 7^2.
It is guaranteed that there is no other way to break 1176 into prime factors. And, certainly, any time you take three 2s, two 7s, and a three, you're always going to get 1176 when you multiply them together. The Fundamental Theorem of Algebra assures us that both these things are true for every number.
(By the way, this is one of the reasons that 1 is not considered to be a prime number: if it were, then each number would have an infinite number of prime factorizations, all differing by how many 1s were included. Instead, 1 is considered to have no prime factors at all, and we say that a number is prime if it has exactly one prime factor -- namely itself.)
Put another way, the Fundamental Theorem of Algebra states that the set of all numbers and the set of all selections of prime numbers are "isomorphic" -- there is a perfect one-to-one mapping between the two. A number is therefore defined by its prime factorization.
Background, Part IV: Relatively Prime Numbers
The greatest common divisor (abbreviated GCD) of two numbers is the largest number that evenly divides into both of them. For example:
GCD(15, 10) = 5,
GCD(18, 10) = 2,
GCD(21, 10) = 1, and
GCD(170, 102) = 34.
Or, another way to look at it is to say that the GCD is the intersection of the two numbers' set of prime factors:
GCD((2^3 * 3^1 * 7^2), (2^2 * 5^1 * 7^3)) = 2^2 * 7^2, so
GCD(1176, 6860) = 196.
When two numbers have no common factors, their GCD will be 1, and the two numbers are said to be relatively prime (or coprime). For example, we can see in our list up above that 21 and 10 are relatively prime.
Since a prime number has no factors besides itself, clearly a prime number is relatively prime to every other number. And the same can be said of the number 1.
Okay. Enough background material. Let's get to the good stuff.
Euler's Totient Function
Euler's Totient Function is denoted by the Greek letter phi, and is defined as follows:
phi(N) = how many numbers between 1 and N - 1 which are relatively prime to N.
Thus:
phi(4) = 2 (1 and 3 are relatively prime to 4),
phi(5) = 4 (1, 2, 3, and 4 are relatively prime to 5),
phi(6) = 2 (1 and 5 are relatively prime to 6),
phi(7) = 6 (1, 2, 3, 4, 5, and 6 are relatively prime to 7),
phi(8) = 4 (1, 3, 5, and 7 are relatively prime to 8), and
phi(9) = 6 (1, 2, 4, 5, 7, and 8 are relatively prime to 9).
Here is the same definition expressed as C code:
phi = 1;
for (i = 2 ; i < N ; ++i)
if (gcd(i, N) == 1)
++phi;
(By the way, notice that phi(1) is specially defined to be 1.)
It should be easy to see that phi(N) will be N - 1 whenever N is prime. Somewhat less obvious is the useful fact that phi(N) is also easy to calculate when N has exactly two different prime factors:
phi(P * Q) = (P - 1) * (Q - 1), if P and Q are prime.
(The proof of this fact is left as an exercise for the reader.) Thus, for example:
phi(15) = 2 * 4 = 8 (1, 2, 4, 7, 8, 11, 13, and 14).
The two prime factors cannot be the same number for this to work, and in fact you can see above that phi(9) does not equal 4.
Euler's Totient Theorem
This theorem is one of the important keys to the RSA algorithm:
If GCD(T, R) = 1 and T < R, then T^(phi(R)) = 1 (mod R).
Or, in words:
If T and R are relatively prime, with T being the smaller number, then when we multiply T with itself phi(R) times and divide the result by R, the remainder will always be 1.
We can test this theorem on some smaller numbers for which we have already calculated the totient. Using 5 for T and 6 for R, we get:
phi(6) = (2 - 1) * (3 - 1) = 1 * 2 = 2, so
5^(phi(6)) = 5^2 = 25, and
25 = 24 + 1 = 6 * 4 + 1, therefore
25 = 1 (mod 6).
Using 2 for T and 15 for R, we have:
phi(15) = (3 - 1) * (5 - 1) = 2 * 4 = 8, so
2^(phi(15)) = 2^8 = 256, and
256 = 255 + 1 = 17 * 15 + 1, therefore
256 = 1 (mod 15).
Variations on a Theme
Here again is the equation of Euler's Totient Theorem:
T^(phi(R)) = 1 (mod R)
(remembering that T < R, and T and R are relatively prime). Thanks to the way that modulus arithmetic works on multiplication, we can easily see that:
T^(phi(R)) * T^(phi(R)) = 1 * 1 (mod R),
which can be rewritten, using the laws of exponents, as:
T^(phi(R) + phi(R)) = 1 * 1 (mod R),
or:
T^(2 * phi(R)) = 1 (mod R).
If we ran through this sequence again, we would get:
T^(3 * phi(R)) = 1 (mod R).
Clearly, we could keep doing this as many times as we like. So, we can expand on Euler's Totient Theorem, and state a more general corollary:
If GCD(T, R) = 1 and T < R,
Page : << Previous 2 Next >>