The discrete logarithm problem
About this video
Modular (clock) arithmetic wraps numbers around a clock: 46 mod 12 is 10. Using a prime modulus like 17 and a primitive root like 3, raising 3 to an exponent is easy, but going backwards (finding the exponent that gives a result) is the discrete logarithm problem. With huge primes this one-way function becomes practically impossible to reverse.
You'll be able to
- calculate a simple mod, such as 46 mod 12.
- explain what a generator (primitive root) does.
- describe the discrete logarithm problem and why it makes a one-way function.
Key words
- modular arithmetic
- Clock arithmetic: wrap a number around a clock and see where it ends.
- modulus
- The size of the clock you wrap around, like 12 or 17.
- primitive root (generator)
- A number like 3 whose powers spread evenly around the clock of a prime modulus.
- discrete logarithm problem
- Given the result, finding the exponent the generator was raised to.
- one-way function
- A procedure that is easy to perform but hard to reverse.
Transcript
- [Voiceover] We need a numerical procedure, which is easy in one direction and hard in the other. This brings us to modular arithmetic, also known as clock arithmetic. For example, to find 46 mod 12, we could take a rope of length 46 units and rap it around a clock of 12 units, which is called the modulus, and where the rope ends is the solution.
So we say 46 mod 12 is congruent to 10, easy. Now, to make this work, we use a prime modulus, such as 17, then we find a primitive root of 17, in this case three, which has this important property that when raised to different exponents, the solution distributes uniformly around the clock.
Three is known as the generator. If we raise three to any exponent x, then the solution is equally likely to be any integer between zero and 17. Now, the reverse procedure is hard. Say, given 12, find the exponent three needs to be raised to. This is called the discrete logarithm problem.
And now we have our one-way function, easy to perform but hard to reverse. Given 12, we would have to resort to trial and error to find matching exponents. How hard is this? With small numbers it's easy, but if we use a prime modulus which is hundreds of digits long, it becomes impractical to solve.
Even if you had access to all computational power on Earth, it could take thousands of years to run through all possibilities. So the strength of a one-way function is based on the time needed to reverse it.
Video © Khan Academy, used under CC BY-NC-SA. Watch on Khan Academy. Puzzicle is not affiliated with Khan Academy.