Multiplication, Powers, and Logarithms
For this lab, we will look more closely at how clock numbers behave under multiplication.
It turns out that prime numbers are especially nice in this regard; so in this lab will only consider clock numbers modulo a prime number p.
The discrete logarithm problem that we begin to study here is fundamental to modern cryptography.
In a subsequent lab, we will look at the same problem for other number systems, such as the clock numbers modulo the composite number n=pq.
|sweep r ||× ||1 ||
Notice how in the "Multiplicative View", successive powers proceed at uniform speed around the circle, while the picture in the "Additive View" is not as predictable.
|all r ||× ||1 ||
This displays the set of all powers of z (which you choose). What are the possible sets of powers, for different z? How does this depend on the modulus p? Record your observations for group discussion.
|all z ||× ||1 ||
Set r to a variety of powers. Record your observations on the set of squares, cubes, etc., for group discussion. As you vary the modulus p, be sure in each case to check the (p-1)'st and p'th powers. Compare with what the set of squares, cubes, etc., looks like in the ordinary integers.
Compare your observations on the way that sets of powers vary with z and p. Focusing on the "Multiplicative View", how does this relate to the sets of multiples in the clock numbers modulo p-1? (The basic fact this lab is trying to convince you of is that multiplication of non-zero clock numbers modulo p works exactly like addition of clock numbers modulo p-1.)
Notice that in every case (when the modulus p is prime), there are numbers whose powers fill out the the entire set of non-zero numbers.
(The complete explanation is beyond the scope of this course.)
Discuss how this allows us to develop logarithms in this number system [more explanation and background needed!].
How many clock numbers are squares, cubes, fourth powers, ...? What is the pattern, and how do you explain it?
What is special about the (p-1)'st and p'th powers?
(The answer to this last question is called Fermat's Little Theorem.)
The Woodrow Wilson Leadership Program in Mathematics
The Woodrow Wilson National Fellowship Foundation
CN 5281, Princeton NJ 08543-5281