If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

# The discrete logarithm problem

A mathematical lock using modular arithmetic. Created by Brit Cruise.

## Want to join the conversation?

• • [Power Moduli] : Let m denote a positive integer and a any positive integer such that (a, m) = 1. Let h be the smallest positive integer such that a^h = 1 (mod m). We say that the order of a modulo m is h, or that a belongs to the exponent h modulo m. (NZM, p.97)

Lemma : If a has order h(mod m), then the positive integers k such that a^k = 1 (mod m) are precisely those for which h divides k.

Corollary : If (a, m) = 1, then the order of a modulo m divides phi(m).

Definition : If g belongs to the exponent phi(m) modulo m, then g is called a primitive root modulo m.

In other words, If (g, m) = 1, and g^{phi(m)} (mod m) = 1, then g is called a primitive root of m.

*Moreover, if m has a primitive root, then it has exactly (phi(phi) m) of them.
(1 vote)
• How do you find primitive roots of numbers? Especially prime numbers. I don't understand how Brit got 3 from 17. Could someone help me? • Is there any way the concept of a primitive root could be explained in much simpler terms? It got slipped into this video pretty casually and completely flummoxed me, but every time I try to look it up somewhere I just get more confused. The explanation given here has the same effect; I'm lost in the very first sentence. What is the most absolutely basic definition of a primitive root? • Why is it so important for the frequency to be distributed evenly? • I don't understand how this works.Could you tell me how it works? • Basically, the problem with your ordinary One Time Pad is that it's difficult to secretly transfer a key. Since Eve is always watching, she will see Alice and Bob exchange key numbers to their One Time Pad encryptions, and she will be able to make a copy and decode all your messages. What you need is something like the colors shown in the last video: Colors are easy to mix, but not so easy to take apart. Math usually isn't like that. In math, if you add two numbers, and Eve knows one of them (the public key), she can easily subtract it from the bigger number (private and public mix) and get the number that Bob and Alice want to keep secret. Modular arithmetic is like paint. You can easily find the answer to a modular equation, but if you know the answer to a modular equation, you can't find the numbers that were used in the equation. This is why modular arithmetic works in the exchange system.

Does that help? Or did you not understand the math itself?

PS: I interpreted the "how" as 'you can do the math, but you can't understand how it works to transfer messages'
• At , shouldn't he say that the solution is equally likely to be any value between 0 and 16 rather than 0 and 17? • Is there a way to do modular arithmetic on a calculator, or would Alice and Bob each need to find a clock of p units and a rope of x units and do it by hand? • Some calculators have a built-in mod function (the calculator on a Windows computer does, just switch it to scientific mode). It's also a fundamental operation in programming, so if you have any sort of compiler, you can write a simple program to do it (Python's command line makes a great calculator, since it's instant, and the basics can be learned quickly).

On a calculator, I believe it's usually just written as "mod." In programming, it's either mod or '%,' depending on the language (% is more common), so 22 mod 4 would be 22%4 (which gives you 2). To do it by hand, you'd do this:
22/4 = 5... (ignore everything after the decimal point)
4*5 = 20
22-20 = 2
(or you could just say 22/4 = 5 R 2, and the answer is the remainder--that's probably easier, but I'm so used to using it in programming that I automatically think of it the long way).

By definition, x mod n cannot be greater than n-1 (a remainder of n would really be a remainder of 0). •  