The discrete logarithm problem | Journey into cryptography | Computer Science | Khan Academy

A mathematical lock using modular arithmetic
Watch the next lesson: www.khanacademy.org/computing...
Missed the previous lesson? www.khanacademy.org/computing...
Computer Science on Khan Academy: Learn select topics from computer science - algorithms (how we solve common problems in computer science and measure the efficiency of our solutions), cryptography (how we protect secret information), and information theory (how we encode and compress information).
About Khan Academy: Khan Academy is a nonprofit with a mission to provide a free, world-class education for anyone, anywhere. We believe learners of all ages should have unlimited access to free educational content they can master at their own pace. We use intelligent software, deep data analytics and intuitive user interfaces to help students and teachers around the world. Our resources cover preschool through early college education, including math, biology, chemistry, physics, economics, finance, history, grammar and more. We offer free personalized SAT test prep in partnership with the test developer, the College Board. Khan Academy has been translated into dozens of languages, and 100 million people use our platform worldwide every year. For more information, visit www.khanacademy.org, join us on Facebook or follow us on Twitter at @khanacademy. And remember, you can learn anything.
For free. For everyone. Forever. #YouCanLearnAnything
Subscribe to Khan Academy’s Computer Science channel: / channel
Subscribe to Khan Academy: kzbin.info_...

[@random4573]

You know ..this the first time I actually leaned about what a discrete logarithm is

[@InebriatedEscapist]

Great introduction to the DLP.

[@derekdj6790]

Excellent explanation!

[@yacinefloret1039]

thank you so much you make it so easy to understand !

[@redtedredeemer6877]

hey just a quick question, why 3^29 at 1:28 rather than 3^13? Surely you'd want it to be the lowest value so it wasn't a one to many function you were solving? Or is it just a number plucked from the sky for illustrative purposes?

[@ayusuf101]

Pied Piper's network cracked it.

[@JoshY01]

Nice!!

[@MateussCelioBR]

great video, what is the first music name?

[@ameliasundman2388]

The ominous music in the background behind the clock at the end made me laugh. Thank you.

[@erlendlangseth4672]

What is the music?

[@renegade5942]

this video scared the shit out of me

[@victorzaak]

hahahame too. you will understand it better if you search for readable material.the video is too fast paced

[@renegade5942]

@@victorzaak i was refering to the song he is using and the way he moves objects in the video xDD

[@gemilaguinaldo6723]

this is the problem piper net solved!

[@PvblivsAelivs]

Seventeen is a bad modulus -- and not just because it is small. It's (p-1) value consists entirely of very small factors (in this case, all 2's.) By raising the base and the target value to the eighth power, we can immediately see the last bit in the correct exponent. And we can keep stripping off bits. Sure, we're still doing trial and error. But we vastly reduce the number of trials at each stage. A better prime modulus would be 23. The shortcut then wouldn't work, because you need the 11 trials when you hit the prime factor of 11.

[@OleTange]

"If you have access to all computational power on earth, it could take 1000s of years" But ONLY if we assume computers do not get faster. If we, on the other hand, assume that computers become twice as powerful every year, then it is much less. Testing 2^256 options then takes in the order of 200 years.

[@evenprime1658]

meh... that assumption is a bit too much... because the time needed does not increase linearly to the size of the input.. its non-polynomial (that is why its likely in a category higher than NP problems) and also if computers get 2x powerful every year.. the fastest computer would be getting faster every (to some extent maybe they are but really they would have to get exponentially faster) , i guess that assumption can only be reasonable if we are talking about out consumer grade computers, not super or quantum computers. The fastest computers arent really getting major upgrades every year :/ i would really like P vs. NP solved before i die.. But always hope is there for some major break through that allows us to take a shortcut :(

[@prithvib8662]

For those who don't know, this mathematical problem is the basis for the RSA algorithm. Peter Shor (creator of Shor's algorithm) showed that this problem, the discrete logarithm problem, could be solved efficiently on a quantum computer. Which means a functioning quantum computer can crack the RSA algorithm. EDIT: disregard this comment, the RSA algorithm actually relies on the prime factorization problem, not the discrete logarithm problem.

[@williamwiener8783]

RSA depends on the integer factorization problem, not the discrete logarithm problem

[@prithvib8662]

@@williamwiener8783 ah it seems you are correct. I've updated my comment. Thanks!

[@davidt01]

​@@williamwiener8783 But the two are closely related. If you could efficiently solve the discrete logarithm function you could crack RSA.