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.

Main content

The discrete logarithm problem

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

Want to join the conversation?

  • piceratops ultimate style avatar for user NotMyRealUsername
    What is a primitive root?
    (83 votes)
    Default Khan Academy avatar avatar for user
    • leaf orange style avatar for user Amit Kr  Chauhan
      [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)
  • leafers ultimate style avatar for user ShadowDragon7
    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?
    (35 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user patmull1170
      You can't generally exactly calculate it (especially for the big numbers), you can only test it, so generally, you can use brute force with a random picking of numbers and check whether it matches the m^e mod N ≡ c formula or you can use Euler's totient function explained later in this course helps.
      (1 vote)
  • blobby green style avatar for user Kori
    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?
    (23 votes)
    Default Khan Academy avatar avatar for user
  • hopper cool style avatar for user Florian Melzer
    Why is it so important for the frequency to be distributed evenly?
    (5 votes)
    Default Khan Academy avatar avatar for user
  • winston baby style avatar for user Markiv
    I don't understand how this works.Could you tell me how it works?
    (4 votes)
    Default Khan Academy avatar avatar for user
    • mr pink red style avatar for user Varun
      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'
      (15 votes)
  • mr pants pink style avatar for user KarlKarlJohn
    At , shouldn't he say that the solution is equally likely to be any value between 0 and 16 rather than 0 and 17?
    (6 votes)
    Default Khan Academy avatar avatar for user
  • piceratops tree style avatar for user Susan Pevensie (Icewind)
    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?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • aqualine ultimate style avatar for user alleigh76
      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).
      (4 votes)
  • aqualine seed style avatar for user raj.gollamudi
    About the modular arithmetic, does the clock have to have the modulus number of places? For example, if the question were to be 46 mod 13 (just changing an example from a previous video) would the clock have to have 13 spots instead of the normal 12?
    (3 votes)
    Default Khan Academy avatar avatar for user
  • leafers tree style avatar for user Ğļ∑лл Μ
    What is that grid in the beginning?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • aqualine seedling style avatar for user Anne C
    Not sure if anyone else had the same problem, but I think this unit would be easier to learn if the Modular Arithmetic section came before it. I found myself having to look up a lot of modular-arithmetic terms (modulus, generator, primitive root, etc.) before I could understand most of this video.
    (3 votes)
    Default Khan Academy avatar avatar for user

Video 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.