You are much much better than my cryptography teacher. He would have taken atleast 2 hours to explain this simple concept. Thanks Emily for this great lecture.
You always wanted your Euclidean Algorithm in the form a x b + c. So you start off by using the 43 and the 17 that are in the question. 17 goes into 43 two times with 9 remainder. Therefore 43 = 17 x 2 + 9. Hope that helps.
I have a doubt from elgmmal when recoving the key I got key value as 7 and when taking inverse for key value it gets 11. I still couldn't understand how it goes?.... it says the concept follows extended euclidean algorithm help me
I have a doubt from elgmmal when recoving the key I got key value as 7 and when taking inverse for key value it gets 11. I still couldn't understand how it goes?.... it says the concept follows extended euclidean algorithm... help me
Al Amin When working mod 43, your answer has to be between 0 and 42. In this example, the answer is -5, which is equivalent to 38 (mod 43). You couldn't say the answer is 37, because it has to be a multiple of 43 (ie. you just add or subtract x lots of 43 until you get a number between 0 and 42). -5 (mod43) and 38 (mod43) is also equivalent to 81 (mod43), 124 (mod 43), -48 (mod 43), -91 (mod 43) etc, because when you add or subtract multiples of 43, the answer is always 38. I hope this helps!
Perhaps another way to obtain the "38" is to recall that q*43 = 0 (mod 43) for any integer "q" as she did in the video when she set 2*43 = 0 (mod 43). So adding on both sides of equation 1 = 2*43 +(-5)*17 the term 17*43 = 0 (mod 43) we obtain 1+17*43 = 1+0 = 2*43+(-5)*17 + 43*17= 0+(43-5)*17 = 38*17. So we get the desired result 38*17 = 1 (mod 43).
Your explanation is different from my textbook but I like your way of finding out the solution. Some UA-cam makers use so much fancy technology into their video that I get annoyed. Your video is good and just right to the point. Thank you.
For hand computation, using modular arithmetic is 5-10x faster than using the extended Euclidean algorithm. 17x ≡ 1 mod 43. I want to add a multiple of 43 to 1 so that the sum is a multiple of 17. That way I can divide by 17 to solve for x. Since 43 ≡ 9 mod 17, and 1 + -2 * 9 = -17, it follows that 17x ≡ 1 - 2*43 ≡ -85 (mod 43). Dividing both sides by 17 then gives x ≡ -5 mod 43.
First of all, thank you very much for the explanation (it sure has helped me in figuring out inverse). But I do have a question. Most of the time I do the subtract part that you do in the ending (the - 5 mod 38 bit).. but I have come across a few examples where this is not needed.. and I cannot explain why. I have an example here (where I have to find the inverse of 12 mod 3079): 3079 = 12 x 256 + 7 12 = 7 x 1 + 5 7 = 5 x 1 + 2 5 = 2 x 2 +1 ________________________ 1 = 5 - 2 x 2 Sub. 2 = 7 - 5 1 = 5 - (7 - 5) x 2 1 = 5 - 7 + 5 x 2 1 = 3 x 5 - 7 x 2 Sub. 5 = 12 - 7 1 = 3 x (12 - 7) - 7 x 2 1 = 3 x 12 - 7 + 7 x 2 1 = 3 x 12 - 7 x 5 Sub. 7 = 3079 - 12 x 256 1 = 3 x 12 - (3079 - 12 x 256) x 5 1 = 3 x 12 - 3079 + 12 x 256 x 5 1 = 1283 x 12 - 3079 x 5 Apparently, 1283 is already the inverse of 12 and substraction is not needed. Could you give me a good example so I can see when I do need to do the substraction and in which situations I do not have to do that step? Thanks a bunch, Emily! And thanks again for the vid, been very helpful.
Abantu bezibalo bayathanda ukusiqhumisa amakhanda ngamabomu ugcine ungasizakalanga. Ngiyabonga Dadewethu. That's Zulu, which translates to Mathematicians are so condescending, thank you so much for this simple explanation my sister.
AHHH finally one video that made me snap! Thank you for taking your time and explaining step by step what you do! I'm curious about one thing: What is your field of study?
Why would you add this many equations man? This is extremly frustrating. Just make the equation simple instead of adding more equations like 1 = 9 - (17-9) 1 = 9 - 17+9 1 = 2 x 9 - 17 It's ridiculous. I don't understand how people are commenting ah thank you made this easier. Just make it simple.
First, I would like to say that the explanation is great and the video really helped me with solving my problem, since I've been surfing throughout the internet for the past hour or so searching for a decent and clear explanation of how to do this :D I have a question, though - in this case 1 is on the right side, what if it were to be 3 or any other number? As in, for example, 17x congruent to 3 (mod 43) (doesn't matter, if this exists or not, I'm just giving it as an example to explain what I want to say, because I find no other way of saying it xD), so does that mean that the gcd of 17 and 43 has to be 3?
Good question! The number on the right can be any number. Because when you take 17 across to the right side you get (in your example) x = 3/17 (mod 43). Another way of writing this is x = 1/17 multiplied by 3 (mod 43). So you work out the 1/17 (mod 43) bit, which in the video equals 38. Then you multiply 38 by 3, which equals 114. 114 mod 43 is 28. Therefore 17x = 3 (mod 43) equals 28. The gcd always has to be 1, no matter what number is on the right side of the equation.
At the very beginning x = 1/17 mod 43, so your final answer should be 1/17 Note 17^-1 is 1/17 so, 1 = -5 * 17 1/17 = -5 Then because you have a negative number you subtract from 43, 43-5 = 38 Note if you got +5, then the answer is 5.
Yeah, when you finish the extended euclidean algorithm, you'll get something being multiplied by the mod number (which you can cross out) and something multiplied by the inverse number (which is the answer). The answer was -5, but it has to be between 0 and 42. So -5 + 43 = 38
@@Jdiddy1792 I have a doubt from elgmmal when recoving the key I got key value as 7 and when taking inverse for key value it gets 11. I still couldn't understand how it goes?.... it says the concept follows extended euclidean algorithm help me
@@lifeandprimes I have a doubt from elgmmal when recoving the key I got key value as 7 and when taking inverse for key value it gets 11. I still couldn't understand how it goes?.... it says the concept follows extended euclidean algorithm help me
Hi Emily! Thanks for making this video, I found it really helpful while studying for a discrete math exam. I had a question: how did you orient your camera to capture this? I was trying to make a math video but I was getting stuck how to set up the camera.
how did i get from call of duty to this?
+callofduty fanboy999 The words "EA" and "mod" exist in the video description And those words are also related to video games :)
@@raymondpang3896 wow mad!!
@@raymondpang3896 Nerdiest man ever!!
its a curse (goodluck you are heading towards some fun times)
@@raymondpang3896 I wanted to upvote but didnt want to make it 70
I know this video is from 7 years ago but it is insanely helpful. Answered a lot of uncertainties! If you ever see this, thank you a lot.
The most clear explanation of this topic on UA-cam! Thank you very much.
not saying much XD
I'm not going to say that my professor doesn't know how to explain or teach, but the way you did it was beautiful. Thank you a lot Emily.
You are much much better than my cryptography teacher.
He would have taken atleast 2 hours to explain this simple concept.
Thanks Emily for this great lecture.
In 5 minutes you taught me more than my professor could do in 5 hours. Thanks :)
same!
hope someone will teach you the past form of teach
In one min
ua-cam.com/video/kf5sAn_UT-w/v-deo.html
you moron you can't even learn the english language correctly, let alone discrete mathematics. fuck you, ruined my day just like that.
Doomlad me??
You always wanted your Euclidean Algorithm in the form a x b + c. So you start off by using the 43 and the 17 that are in the question. 17 goes into 43 two times with 9 remainder. Therefore 43 = 17 x 2 + 9.
Hope that helps.
Because it's mod 43, you want your final answer to be mod 43 as well (ie. between 0 and 42).
So it's -5 + 43 = 38.
My teacher is a shit!🙂 X'cuse me Lady,, can you come to my college 😒
i love you for that
Can you solve 80-¹(mod 171)
My teacher is not good like you
12/10/21 hope you'll notice this ma'am
@@kyletanyente6149 8 yrs ago lol good luck
you just destroyed my professor's whole career in 5 minutes and 59 seconds
You just taught me a 4 hour math lecture in 6 minutes. Thank you very much.
In such a short time, you explained it very well. I was surfing all over the Internet and couldn't find a proper one. Thanks a lot...!!!
Probably the best explanation I have ever seen. Well done!
this legit dissolved my worries so quickly. incredibly satisfying, thanks
I have a doubt from elgmmal when recoving the key I got key value as 7 and when taking inverse for key value it gets 11. I still couldn't understand how it goes?.... it says the concept follows extended euclidean algorithm help me
Thank you Emily for such a clear explanation through an example. Helped me in preparing for the Cryptography exam.
I have a doubt from elgmmal when recoving the key I got key value as 7 and when taking inverse for key value it gets 11. I still couldn't understand how it goes?.... it says the concept follows extended euclidean algorithm... help me
Durga R did you get it?
I've been like 3 hours trying to find a good tutorial about this. I love you
Even our P. HD professor can not teach like this. Teaching is a art 🎨. And you have it. Congrats
Great explanation, clear and concise. That was a massive help studding for my end of semester exams!
this was a godsend, THANK YOU
Al Amin When working mod 43, your answer has to be between 0 and 42. In this example, the answer is -5, which is equivalent to 38 (mod 43). You couldn't say the answer is 37, because it has to be a multiple of 43 (ie. you just add or subtract x lots of 43 until you get a number between 0 and 42).
-5 (mod43) and 38 (mod43) is also equivalent to 81 (mod43), 124 (mod 43), -48 (mod 43), -91 (mod 43) etc, because when you add or subtract multiples of 43, the answer is always 38.
I hope this helps!
How come 38 is obtained ,plz show ???
43-5
Perhaps another way to obtain the "38" is to recall that q*43 = 0 (mod 43) for any integer "q" as she did in the video when she set 2*43 = 0 (mod 43). So adding on both sides of equation 1 = 2*43 +(-5)*17 the term 17*43 = 0 (mod 43) we obtain 1+17*43 = 1+0 = 2*43+(-5)*17 + 43*17= 0+(43-5)*17 = 38*17. So we get the desired result 38*17 = 1 (mod 43).
Think of it as -5 + 43 =38 since you can’t have a negative remainder
I'm glad that videos like this exist on UA-cam.
Your explanation is different from my textbook but I like your way of finding out the solution. Some UA-cam makers use so much fancy technology into their video that I get annoyed. Your video is good and just right to the point. Thank you.
thank you, you have explained what i have been trying to understand for weeks in a few minutes.
by far the best explanation on modular inverse! thank you so much
Thank you. Im in a 6 week discrete math class and im really not understanding things because the professor just flies by everything. This helps!
Lovely voice, clear explanation. Thanks!
After watching your video twice, I finally understood this. Tysm!
This is a great video. The process is long, but you explained everything so perfectly. Thank you.
This is the best explanation I have came by thus far. Thank you friend.
Talented, brilliant, incredible, amazing, show stopping, spectacular, never the same, totally unique
saved my life
For hand computation, using modular arithmetic is 5-10x faster than using the extended Euclidean algorithm. 17x ≡ 1 mod 43. I want to add a multiple of 43 to 1 so that the sum is a multiple of 17. That way I can divide by 17 to solve for x. Since 43 ≡ 9 mod 17, and 1 + -2 * 9 = -17, it follows that 17x ≡ 1 - 2*43 ≡ -85 (mod 43). Dividing both sides by 17 then gives x ≡ -5 mod 43.
And how would you do that if you have d ≡ (1/65537) (mod 7275919392).
The best and most easy explanation so far! Kudos to you! Thank you for bringing the red color as well
So helpful it was 7 years ago wao what a simple explanation..:) Why did youstop making videos they are very helpful to students.
Very helpful video and a fit voice. Win win.
This is worth 10 points on my tuesday exam, thank you so much
yo...I love u maa g....ur stupendous ... thanks a lot for the explanation.....hv been scavenging youtube for over an hr till
I found yours🥰
You should make more videos like this Emily, seriously.
i have a crypto exam in a couple days. thank you so much
brilliant explanation! And love the voice, very soothing!
First of all, thank you very much for the explanation (it sure has helped me in figuring out inverse). But I do have a question. Most of the time I do the subtract part that you do in the ending (the - 5 mod 38 bit).. but I have come across a few examples where this is not needed.. and I cannot explain why. I have an example here (where I have to find the inverse of 12 mod 3079):
3079 = 12 x 256 + 7
12 = 7 x 1 + 5
7 = 5 x 1 + 2
5 = 2 x 2 +1
________________________
1 = 5 - 2 x 2
Sub. 2 = 7 - 5
1 = 5 - (7 - 5) x 2
1 = 5 - 7 + 5 x 2
1 = 3 x 5 - 7 x 2
Sub. 5 = 12 - 7
1 = 3 x (12 - 7) - 7 x 2
1 = 3 x 12 - 7 + 7 x 2
1 = 3 x 12 - 7 x 5
Sub. 7 = 3079 - 12 x 256
1 = 3 x 12 - (3079 - 12 x 256) x 5
1 = 3 x 12 - 3079 + 12 x 256 x 5
1 = 1283 x 12 - 3079 x 5
Apparently, 1283 is already the inverse of 12 and substraction is not needed. Could you give me a good example so I can see when I do need to do the substraction and in which situations I do not have to do that step?
Thanks a bunch, Emily! And thanks again for the vid, been very helpful.
Abantu bezibalo bayathanda ukusiqhumisa amakhanda ngamabomu ugcine ungasizakalanga. Ngiyabonga Dadewethu. That's Zulu, which translates to Mathematicians are so condescending, thank you so much for this simple explanation my sister.
I just spent two weeks on this. Thank you.
I like your hand writing. Perfect video!
I love the sound the pen makes
Damn with this video the Bezout theorem makes sense too and now i understood this algorithm helps to understand that too :))
Thank you very much, miss Emily!
I just watched your video and instantly was able to solve it on my own. I hope you have a great day!
YOU'RE A LIFE SAVER!
i like the way you hold the pen.
such a clear explanation Emily. Thank you
Thank you so much. It helped me top my cryptography exam.
Thank you for such a straightforward explanation! This was really helpful👍
Thanks for the explanation...I must say you are a great teacher
Awesome tutorial. Thank you mam.
YOU SAVED MY LIFE !!!!!! I LOVE YOU AND THANK YOU !!! 🙌🏾🙌🏾🙌🏾
Omg thank you so much, I was struggling with this for so long!!!
Awesome tutorial mam. Thank you
This helped me. I wasn't after a wikipedia-like explanation so this was ideal.
great ...today is my cryptography paper ..u done a reat job for me ...best wishes
Nice video! Helped me in my course assignment.
i didnt understand why u got 38
This was the explanation I needed to clarify the final step and it all makes sense now :) thanks a lot :)
Thank you! you really helped me solve my question
Thanks a lot! Your video explanation really helped for my exam preparation.
Brilliantly explained! Helped me out a lot with my assignment, much thanks
thank you, everything is clear now
AHHH finally one video that made me snap!
Thank you for taking your time and explaining step by step what you do!
I'm curious about one thing: What is your field of study?
I'm studying a bachelor of teaching and a bachelor of science with a major in mathematical modelling and a minor in biological chemistry.
yo this video is crazzzzy helpful! so blessseddddd!!!!!
thanks, I was confused about negative answer.
I love you and sending you corona-proof hugs from Turkey
Why would you add this many equations man? This is extremly frustrating. Just make the equation simple instead of adding more equations like
1 = 9 - (17-9)
1 = 9 - 17+9
1 = 2 x 9 - 17
It's ridiculous. I don't understand how people are commenting ah thank you made this easier. Just make it simple.
I do that so I don’t make any mistakes. It makes it easier for me. I’m sorry that you are frustrated, I hope you have a better day tomorrow.
best explanation ever
What a wonderful video! How nicely explained!
Thank you
Thank you Emily Scott, you are an angel...
why didn't i watched this when i was in college . thanks :-)
the best famous person ı've ever seen. thanks for my midterm.
Such a great explanation, thank you so much ,much needed it.keep it up like this
You litterally saved me from a catrophe
Ahhh thankyou smm!!
U saved my time & brain.
Wonderful! Thanks so much for the help!
I don't understand the rule you have applied to get -5 in that simplification
Very helpful and easy to understand. Thanks!
A short, sharp and very well explained tutorial. Thank you! :)
thanks a lot , I was confused with the minus answer you subtract and got the inverse .
MANN I LIKE THE WAY SHE HOLDS PEN!! :)
Modulo of a negative number (-x) is given by
(-x)%M = M - (x % M)
(-5)%43 = 43 - 5mod43 = 38
Thank me later :)
Thank yoooooou I repeated it many times because of this 38
First, I would like to say that the explanation is great and the video really helped me with solving my problem, since I've been surfing throughout the internet for the past hour or so searching for a decent and clear explanation of how to do this :D
I have a question, though - in this case 1 is on the right side, what if it were to be 3 or any other number? As in, for example, 17x congruent to 3 (mod 43) (doesn't matter, if this exists or not, I'm just giving it as an example to explain what I want to say, because I find no other way of saying it xD), so does that mean that the gcd of 17 and 43 has to be 3?
Good question!
The number on the right can be any number. Because when you take 17 across to the right side you get (in your example) x = 3/17 (mod 43).
Another way of writing this is x = 1/17 multiplied by 3 (mod 43).
So you work out the 1/17 (mod 43) bit, which in the video equals 38. Then you multiply 38 by 3, which equals 114. 114 mod 43 is 28.
Therefore 17x = 3 (mod 43) equals 28.
The gcd always has to be 1, no matter what number is on the right side of the equation.
Emily Scott Thanks! Your video helped me shitton for my exam on Thursday! : ))))
What happened in that last step? where's 17 go and where did 38 come from?
At the very beginning x = 1/17 mod 43, so your final answer should be 1/17
Note 17^-1 is 1/17
so,
1 = -5 * 17
1/17 = -5
Then because you have a negative number you subtract from 43,
43-5 = 38
Note if you got +5, then the answer is 5.
Yeah, when you finish the extended euclidean algorithm, you'll get something being multiplied by the mod number (which you can cross out) and something multiplied by the inverse number (which is the answer).
The answer was -5, but it has to be between 0 and 42.
So -5 + 43 = 38
@@Jdiddy1792 I have a doubt from elgmmal when recoving the key I got key value as 7 and when taking inverse for key value it gets 11. I still couldn't understand how it goes?.... it says the concept follows extended euclidean algorithm help me
@@lifeandprimes I have a doubt from elgmmal when recoving the key I got key value as 7 and when taking inverse for key value it gets 11. I still couldn't understand how it goes?.... it says the concept follows extended euclidean algorithm help me
nice voice, simple explanation... subscribed
Very helpful. Thanks
Thank you Emily Scott this was a great help!
very good tutorial, thanks
top notch. thank youuuuuuuuuuu very much
Thank you Emily Jane..Keep up the good work
I love you!!!! You are the BEST!!!
Your voice is so sweet :)
THIS IS NOT HOW YOU WRITE AN X!
Hi Emily! Thanks for making this video, I found it really helpful while studying for a discrete math exam.
I had a question: how did you orient your camera to capture this? I was trying to make a math video but I was getting stuck how to set up the camera.
Hahah I used the super professional method of balancing my iphone over the edge of a big stack of books.
Thank you for making this video! Very helpful.
like a diamond in the sky !
thanks a lot.
thank you a lot for this brief video!
:)
You explained well ! Thank you .