i want to touch an important point of this algorithm. When u go inverse, you changing NEXT SUB numbers and ONLY in parenthesis. Look upper eq, sub again[ 11=1(6)+5 goes 5=11-1(6) ] and put eq in the parenthesis. 1 = 6 - 1(5) --->> 1 = 6 - 1( 11-1(6) ) distrubute ( - ) and simplify 1= 6 - 11 + (6) -->> 1= 2(6)-11
Glad it helped. I have other related videos...modular arithmetic made easy, modular exponentiation made easy, euler's theorem made easy, fermat's little theorem made easy and RSA code made easy.
I still don't quite understand what the gcd has to do with finding the modular inverse, but I have been racking my brains for hours now trying to understand this, and you're the only one who gave a nice concise answer and helped me with my homework, so thank you.
0:44 3000 = 15(197) + 45 3000 div 197 = 15 3000 mod 197 = 3000 - (197 *15) = 45 2:05 Left side of video 6 = 1(5) + 1 (solve for 1) 6 -1(5) = 1 1 = 6 - 1(5) (just switched sides, now it looks like the top right) Now get rid of the 5 from this equation So we work with the 2nd last equation on the left side 11 = 1(6) + 5 5 = 11 - 1(6) Now plug into [5 = 11 - 1(6)] into [1 = 6 - 1(5)] 1 = 6 - 1(5) 1 = 6 - 1(-1(6) +11) 1 = 6 +6 - 11 1 = 2(6) - 11 Repeat the process one more time Use the 3rd last equation on the left side and isolate 6 17 = 1(11) + 6 17 - 1(11) = 6 6 = 17 - 1(11) [re-expressed the equation] Plug [6 = 17 - 1(11) ] into the 2nd equation on the right side [1 = 2(6) - 11 ] 1 = 2(6) - 11 1 = 2(17 -1(11)) - 11 1 = 2(17) -2(11) - 11 let a = 11 1 = 2(17) -2a - a 1 = 2(17) -3a 1 = 2(17) - 3(11) Hopefully, that helps, that was too much mental arithmetic going on for me 🤣😭
Holy shit dude. You are a fucking genius , never thought there was an algorithm to calculate the modular inverse for such a large number. Would have used 3 years ago to simplify cryptographic calculation. but yeah , i can use it now as well.
You have done a mistake on the 3rd Step of Extended Euclidean GCD Solution .... it is not -3(11) ... The Step is as follows : Equation available : 1 = 2X6 - 1X11 Step 3 to sub : 6 =17 -1X11 1 = 2X( 17 - 1X11 ) - 1X11 . Now Simplify : 1 = 2X17 - 1X11 - 1X11 1 = 2X17 - 2 X 11 .....How come - 3X11 get in your 3rd Step ???
snoop dogg The usual method for explaining how calculators do trigonometry is that they use Taylor series. I explain this in the video Taylor series made easy. But I think you are correct is saying that small calculators actually use something like the Cordic algorithm.
Thanks. Lots of related videos in my university mathematics playlist, my corona help - discrete mathematics playlist and my corona help - euler's theorem playlist.
@@shloksand2926 I have a video intro proof fermat's last theorem. I can do a bit more on elliptic curves and modular forms. That's about as far as I'll go.
This isn't working for me for some reason. I'm trying to find the inverse of 5 (mod 16) which using Euclid's becomes 16 = 3(5) + 1. The actual inverse is 13 but I don't see how to get 13 from that.
Glad you worked it out. It's a common mistake to get thrown by a negative. Other related videos on modular arithmetic, modular exponentiation, fermat's little theorem, Euler's theorem and RSA code on my channel.
Am i missing something or does this simply not work for 4^-1 mod 999? You get 83(4) + 3, but 83 mod 3 is zero. The GCD of 4 and 999 is definitely one though.
Is it any different to find the multiplicative inverse of 3000 modulo 197, i get the wrong number when i try this with a bigger number modulo a smaller one
Hello, I'm trying to find the modular inverse of 7 mod 120 and I get 17 which is I think wrong. I think it should be 103. But using the extended eucledian algorithm, I get 17. Is that correct?
It is easy to check if either is correct. 7 x 17 is equivalent to -1 mod 120. So 17 is not the inverse. On the other hand 7 x 103 = 721 = 1 mod 120. So the answer is 103. You must be doing something wrong with the extended Euclidean algorithm. Hope that helps.
how are the expressions 1=(triple equation) 533(197)(mod3000) and 197d=1mod3000 the same???? That's what I don't understand. 1mod3000 is just 1. Not 197*533
When I write 197d = 1 mod 3000 I really should have written 197d=1 (mod 3000). And also they should have a three line `equal sign' not the normal two lines. But what this means is that 197d is equal to a number that has a remainder of 1 when divided by 3000. If 197d=1 (mod 3000) and 197(533)=1 (mod 3000) then the value of d between 1 and 3000 is 533. Hope that helps.
im sorry lol but how can anyone say this is a good explanation?? he just says substitute this line with this line?? like which part do i substitute with what lol
Sorry you couldn't understand. There are of course other videos that might be better for you. Otherwise.... You are probably getting stuck around the 2 min mark. On the right hand side I show my workings to express 1 as the difference between multiples of 3000 and 197. From the last line on the left I have 6=1(5)+1. This means that 1=6-1(5). So I write that on the right. Now I want to get rid of that multiple of 5. To do that I look at the second last line on the left. This is 11=1(6)+5. This means that 5=11-1(6). So I can replace 5 in the first line on the right with 11-1(6). So then I get 1=6-1(11-1(6)). This means 1=2(6)-1(11), which is 2nd line on the right. Next I want to replace 2(6). To do this I use the 3rd last line on the left. This continues until I get to the last line on the right side.
You have done a mistake on the 3rd Step of Extended Euclidean GCD Solution .... it is not -3(11) ... The Step is as follows : Equation available : 1 = 2X6 - 1X11 Step 3 to sub : 6 =17 -1X11 1 = 2X( 17 - 1X11 ) - 1X11 . Now Simplify : 1 = 2X17 - 1X11 - 1X11 1 = 2X17 - 2 X 11 .....How come - 3X11 get in your 3rd Step ???
You have done a mistake on the 3rd Step of Extended Euclidean GCD Solution .... it is not -3(11) ... The Step is as follows : Equation available : 1 = 2X6 - 1X11 Step 3 to sub : 6 =17 -1X11 1 = 2X( 17 - 1X11 ) - 1X11 . Now Simplify : 1 = 2X17 - 1X11 - 1X11 1 = 2X17 - 2 X 11 .....How come - 3X11 get in your 3rd Step ???
