Main content
Computer science
Course: Computer science > Unit 2
Lesson 4: Modern cryptography- The fundamental theorem of arithmetic
- Public key cryptography: What is it?
- The discrete logarithm problem
- Diffie-hellman key exchange
- RSA encryption: Step 1
- RSA encryption: Step 2
- RSA encryption: Step 3
- Time Complexity (Exploration)
- Euler's totient function
- Euler Totient Exploration
- RSA encryption: Step 4
- What should we learn next?
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
The discrete logarithm problem
A mathematical lock using modular arithmetic. Created by Brit Cruise.
Want to join the conversation?
What is a primitive root?(82 votes)
[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?(35 votes)
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 them^e mod N ≡ cformula or you can use Euler's totient function explained later in this course helps.(1 vote)
- 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)
I'll work on an extra explanation on this concept, we have the ability to embed text articles now it will be no problem!(8 votes)
0:51Why is it so important for the frequency to be distributed evenly?(5 votes)
I don't understand how this works.Could you tell me how it works?(4 votes)- 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)
At1:00, 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)
That's right, but it would be even more correct to say "any value between 1 and 16", since 3 and 17 are relatively prime. Thus, no matter what power you raise 3 to, it will never be divisible by 17, so it can never be congruent to 0 mod 17.(2 votes)
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)
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)
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)
Yes. When you havep mod nyou haven-1cyclic positions.(1 vote)
What is that grid in the beginning?(1 vote)
It looks like a grid (to show the ulum spiral) from a earlier episode. Possibly a editing mistake?(5 votes)
if there is a pattern of primes, wouldn't there also be a pattern of composite numbers? Thanks!(3 votes)
0:51
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.