Section 4.5 Why modular arithmetic matters
ΒΆβThe polynomial x^5-x+2 has no integer rootsβ. (See Exercise 9.6.4)
βThe curve x^3=y^2-7 has no lattice pointsβ. (See Fact 15.3.3.)
Subsection 4.5.1 Starting to see further
ΒΆIn order to accomplish all these goals, we will take some time learning how to do such computations. Here are two generic practical rules for using modular arithmetic.First off, always first reduce modulo n\text{,} then do your arithmetic (add, multiply, exponentiate). We have seen lots of examples of this.
Secondly, always use the most convenient residue (recall Definition 4.4.6) of a number modulo n\text{.}
Example 4.5.1.
For example, to add [22]+[21] modulo 23 it might be smarter to use the residues -1\in[22] and -2\in [21]\text{.} The answer [-3] is of course the same as [22+21]=[43]=[20] modulo 23\text{.}
xxxxxxxxxx
mod(22,23)+mod(21,23)==mod(-3,23)
Sage note 4.5.2. Checking equality.
Use the double equals sign ==
to check if two numerical expressions are equal, not just =
(which assigns a value to a variable).
Example 4.5.3.
Let's calculate 4^{20} (mod 6). First we will use least nonnegative residues; write the justification for each step in the margin if you have a print copy!
On the other hand, we can avoid using numbers of absolute value bigger than five if we carefully select least absolute residues where appropriate! Recall that 4\equiv -2 (mod 6):
Example 4.5.4.
Just to make sure you get this, on your own compare
The second pair is quite different from the first pair.
Subsection 4.5.2 Taking powers
ΒΆAs one example of how modular arithmetic might matter a bit, let's examine the following algorithm for taking ridiculously high powers of numbers (modulo n). We first need the following interesting fact.Fact 4.5.5.
For any integer a\text{:}
a^{2^1}=a^2
a^{2^2}=(a^2)^2
a^{2^3}=(a^{2^2})^2
In general,
That is to say, each βpower of a to a power of 2β is the square of the previous βpower of a to the previous power of 2β.
Proof.
What does \(a^{2^n}\) even mean? By definition,
so \(a^{2^n}\) is the same as
Example 4.5.6.
In this case, it will be easier to do examples before stating the algorithm. To compute x^{20}\text{,} first we see that 16 is the highest power of 2 less than 20\text{.}
Compute x^2 modulo n\text{.}
Square that for (x^2)^2=x^{2^2}=x^4 (modulo n).
Then square twice more for x^{2^3}=x^8 and x^{2^4}=x^{16}\text{;} we reduce modulo n at each point.
Now write x^{20} as x to a sum of powers of 2;
Then do this final multiplication modulo n as well. You might want to try it to see you get the same thing.
Example 4.5.7.
Now let's get really explicit, and calculate 2^{23} (mod 11). First,
Then get the powers of 2 needed:
So we get, as a computation one can do completely without a calculator,
xxxxxxxxxx
mod(2,11)^23
Algorithm 4.5.8.
In general, we can compute x^k modulo n\text{:}
Write the exponent k=\sum_{i=1}^{\ell} k_i 2^i\text{,} where each k_i=0 or 1\text{.} (This is called the binary representation of k\text{.})
Compute x^2\text{,} x^4\text{,} x^8\text{,} and so forth as above, each time reducing modulo n\text{.}
Multiply \prod_{i=1}^{\ell} x^{k_i 2^i} together as in the examples above. Obviously, if k_i=0 (such as for i=3 in the x^{20} example) you skip it, as it just contributes one to the product.
Remark 4.5.9.
Those interested in efficiency should note that this requires roughly two times the number of binary digits of your number operations, or about 2\log_2 (n) operations, as opposed to normal powers which might require n operations; in addition, you only deal with numbers at most size n^2\text{,} as opposed to gigantic ones, when you mod out after each step, so it requires very little memory.