[Discrete Math] Modular Exponentiation

[@relvelor]

Studying for an exam and who should find as the author of this video but my own professor. Works for me.

[@prstorero]

I was just sitting here working on 4.2 homework and couldn't follow the book or solutions manual very well so I decided to search for it on KZbin. Then I remembered you made a video on it and it's the first one I watched. Very clear and concise. Future discrete math students will be very lucky when you get all of your DM1 and DM2 videos up.

[@TimFarage]

+scott johnson Thanks so much!

[@good-tn9sr]

bro i’m using the same textbook as u….

[@TimFarage]

Don't bother taking the exam tomorrow. I'm giving you an 'A' in the course because you like me.

[@darianpayma3515]

Does this still apply for tomorrow's exam?

[@robwurster8801]

Excellent! I used a table for each exponent then saw your method. Beats any I've seen. Simple, accurate and proven!

[@dreinhart1234]

Have a cryptography test tomorrow...and this video made modular exponentiation so so so clear. Thank you!!

[@giraffe558]

I come back to this video just to hear the soothing voice of Professor Farage. The way he teaches puts me into complete ecstasy. See you in class tomorrow for our exam. ;)

[@TimFarage]

Actually in Java the BigInteger class will handle integers of any size as long as they can fit in the memory. The numbers you gave in your example will be no problem using the BigInteger class. Also in any language you can write your own class that deals with integers of arbitrary size.

[@theCheug]

I have a test today and was not understanding how to do this, but now I do! thanks!!!

[@nahianafsari222]

when you try to find a video to explain modular exponentiation and come across your own professor's video lmao that's cool

[@alliesteele6282]

This is so clear, thank you!

[@TimFarage]

Thanks for the compliment. There is no fast way of doing a^b^c mod p whenever c is large.

[@jwm239]

....among my favorite practice puzzles with modular arithmetic are experiments with successive powers of two, each shown as mod 3, mod 5, mod 7, mod 9, etc., noting the cycles - and the residues that never appear as well as those that do. E.g., 2^n mod 7 is congruent only to 1, 2, or 4 for whole exponents n. Cycles of residues is 1,2,4,1,2,4,1,2,4, leading to equalities such as 2 raised to the 3n power of whole number n, minus 1, is always a multiple of 7. E.g., 7, 63, 511, 4095... Note that each number is 2^3n - 1, and to go from one to the next, start at 7, multiply by 8 each time, add 7.

[@TimFarage]

In your example of 5^2014 mod 31, you'd have about 11 rows, all with values less than the mod which is 31. Then you'd have to multiply the rows whose sum is 2014 and then do mod 31. To keep from the multiplying from getting out of hand, you can multiply the rows two at a time and do mod 31 right away which gives a value less than 31. You can repeat this so that every multiplication, keeping the arithmetic fairly simple.

[@Jdiddy1792]

Because of the laws of modular stuff. LOL Thanks man, helped!

[@TimFarage]

I'm very glad you found it helpful.

[@FTNomad]

You had me at 1:52 and I super grateful you worked it out at 5:38 [I hate it when people hand wave it at those points. Great video, Thanks!

[@robbybolo9088]

WOW thanks! Perfect explanation and demonstration.

[@TimFarage]

Yes, mod is the remainder. For instance to compute 20 mod 3, you divide 3 into 20, which gives 6 with a remainder of 2. Therefore, 20 mod 3 = 6.

[@TimFarage]

You're right, no one knows 5^32 off the top of their head. But if you follow the algorithm I show in the video you can calculate,say, 5^32 mod 7 without even using a calculator. And very quickly as well. The secret is that when you raise a number to a power mod N, the fact that you are taking the modulus allows for the fast algorithm I give to work.

[@TimFarage]

I'm glad it helped, Connor.

[@ScotMatson]

Clear explanation. Few audio issues that I would have edited, wearing headphones was not fun. But helpful none the less, thanks.

[@tehcno007]

at first by looking at your handwriting i thought i am watching a lame video...but when i watched the whole viideo i realised how nice it was...Thankyou!

[@Alexanderkermani]

I'm glad you put this material up! It's such a helpful method. You're way better than the guy that I got stuck teaching me.. My professor's a total jerk, and if it wasn't for the anonymity of the internet I would be pretty apprehensive about saying that! Odds being what they are, he won't even stumble across your video, though.

[@AbhiRichardson]

thanks tim, it really helped me out

[@markosl428]

what a genius explanation.

[@987Slayer]

Thanks for the video! It's helped a lot in my cryptography class!

[@TimFarage]

@opreese Unfortunately, it doesn't apply to multiplying any two integers, although it does apply to raising an integer to an integer power even without mods, although the numbers can get big fast. Have fun computing a 1 billion digit number!

[@Sapphiamur]

perfect explanation, thank you so much!

[@khaleda2052]

Thanks for the upload. I am struggling to find a simplified form for this: (g^a)^b mod p, where g, a, b and p are integer numbers. So, is the simplified form like this (g^ab mod p)?

[@frecklle2022]

I was sitting trying to learn this bullshit for 4 fucking hours, i then came across this video, learnt a wayyyyy easier method in 9 minutes and now know how to do it, my life is now changed, Tim Farage, I love you, how can I send you a gift?

[@TimFarage]

Thank you so much for your kind words.

[@TimFarage]

You're quite welcome. I'm glad to be of service.

[@sherryperez501]

Thank you!

[@dotcore1150]

great explanation .

[@Tigran4]

20 mod 3 = 2, you can also think of it this way, what's the biggest multiple of 3 that less than or equal to 20, in this case it's 18. Then you can subtract 18 from 20 and you get 2.

[@ashappleby169]

Awesome video professor!

[@naushadamin2118]

hi, I found your video very useful however i came across a question 234 ^ 345 mod 456. would their be an easier way to do this or would you suggest to use the same method, thanks

[@TimFarage]

You would use the same algorithm, but you write a program to do it.

[@naushadamin2118]

thank you

[@TimFarage]

+Mr. Gaunt, there's an equation that will be helpful: B^N mod M = (B mod M)^N mod M If we apply this to your problem, we get: 4726^5237 mod 13 = (4726 mod 13)^5237 mod 13 = 7^5237 mod 13 Using this equation, you can now do this by hand or on paper: 7^1 mod 13 = 7 7^2 mod 13 = 10 7^4 mod 13 = 10^2 mod 13 = 9 7^8 mod 13 = 9^2 mod 13 = 3 Etc. Since the result you get is always less than the mod, which is 13, squaring it and doing mod 13 can be done in your head or on paper. Are you worried how many steps it will take to get to your exponent of 5237? Don't be. It will take about log2( 5237 ) steps which is only about 13 steps!

[@TimFarage]

+Mr. Gaunt, you're very welcome.

[@OmniscientTroll]

Well if a is coprime with p and b is coprime with the totient of p, then you can do it pretty quickly using euler's formula.

[@MrLearner19]

Very good!, I have a question, if one of the intermediate operations during the process get 1 as the result, can we still apply this technique? Thank you!

[@TimFarage]

As soon as you get a 1, you will always get a 1, so you need not do any more rows of computations.

[@MrLearner19]

Tim Farage Hi!, thanks for your answer, I was performing this specific operation: (3 ^ 32) mod 17, and I got 1. Then I would say that (3 ^ 64)mod 17 is equal to (1^2) mod 17 = 1, but it isn't. It is 14. Then, Probably I am doing something wrong.. I will check it out later to see what is going on. If you can give me some light on it it would be great, thank you!

[@MrLearner19]

Sorry, I just realized what was wrong, I was using Matlab without taking care of the size of the numbers I was working with, my apologizes, thank you!

[@drippy3080]

amazing video.

[@TimFarage]

Very kind!

[@reubenwilliammpembe667]

you are the best Sir!!! Thank you

[@TimFarage]

The algorithm I gave will work for odd exponents. Try it and you'll see.

[@opreese]

Thanks for the explanation. If possible, does this idea follow thru for a fast multiplication process? I am attempting to multiply two very large numbers each being apx 500 mil digits resulting in a 1 gig digit number. Been using gmp library but ran out of ram so I need to think of another method that is comparably fast.

[@nicholasbuscombe3623]

I understand that but how would you do 10^241 mod(13)... I'm a tad lost on that one...

[@johndoe121213]

another way to simplify 5^40 mod7 is to take the totient of 7 which is 6 and take 40 mod 6 which is 4 . now you have 5^4 mod 7 then you do the squaring 5^1 mod7 = 5 5^2 =25 mod 7=4 (5^2)^2 = 4^2 =16 mod7 = 2

[@TimFarage]

You can do it the same way: 40^1 mod 65 = 40 40^2 mod 65 = 40^2 mod 65 = 40 (coincidentally, we'll get 40 every time) 40^4 mod 65 = 40^2 mod 65 = 40 40^8 mod 65 = 40^2 mod 65 = 40 40^16 mod 65 = 40^2 mod 65 = 40 40^32 mod 65 = 40^2 mod 65 = 40 40^64 mod 65 = 40^2 mod 65 = 40 So the answer is 40.

[@jaleelwilliams136]

does this work for ANY AND ALL numbers?

[@drWebDude]

Thank you sir! Very well explained.

[@hamsinisankaran2435]

Amazing !! Thanks a lot sir !

[@hardikmodhace]

Thank You sir for the great explanation..in a simple manner.Thank you very much :-)

[@queenieginlaglaganon8113]

Thank you so much.. great help..

[@TimFarage]

You're welcome!

[@angeliquaserenity5009]

OK. Here is where I am getting stuck with your example: How is it that you can get a remainder of 5 from 5/7 [5 mod 7]? I can see how you can get a remainder from 7/5. However, when I work out 5/7 I am always getting a number in the tenths digit instead of the ones digit. As far as I know you cannot get a remainder if you have a number in the ones digit as the quotient. Maybe I am missing something here.

[@ahmedgalalramzy]

The integer below 5 that you can divide by 7 is 0.. so the quotient is 0 and the remainder is 5. I hope this is clear enough

[@ReinePoukou]

Best explanation

[@TimFarage]

Glad to have helped. Wouldn't want you to have lost your *ss.

[@2927challenger]

Thanks so much !

[@TimFarage]

Please ignore the above comment. It was made by a current student of mine who was "trying" to be funny. (It was an inside joke). The bottom line is the he will get an 'F' in my course :).

[@TimFarage]

Basically, you'd use my algorithm to calculate 5 ^ 4 mod 7 and get that answer. Then you'd use my algorithm to calculate 4 ^ 2 mod 7. If the answers are the same then you know that 5 ^ 4 mod 7 = 4 ^ 2 mod 7. Of course, these numbers are so small, you can do this by hand. So 5 ^ 4 mod 7 = 625 mod 7. To get this divide 625 by 7 and get the remainder. Here the remainder is 2. Now do 4 ^ 2 mod 7 = 16 mod 7 which is also 2. Therefore, 5 ^ 4 mod 7 = 4 ^ 2 mod 7.

[@casdegroot9543]

im kinda stuck with 12^7 mod 35, could you help me out here (im not supposed to use a calc)

[@TimFarage]

Do it this way: 12^1 mod 35 = 12 12^2 mod 35 = 144 mod 35 = 4 12^4 mod 35 = 4^2 mod 35 = 16 mod 35 = 16 Note that the exponents add to 7, so to get the answer we multiply the RHS values mod 35: 12 * 4 * 16 mod 35 = 48 * 16 mod 35 = (48 mod 35) * (16 mod 35) mod 35 = (This is true because the mod of the product is the product of the mods) 13 * 16 mod 35 = 208 mod 35 = 33

[@sanketsawantsnk]

+Tim Farage thankyou so much for such a wonderful explaination sir. What if we have x^9modz or x^11modz ? How are the exponents going to add up to 9 or 11 ? Could you please explain with a small example sir?

[@c.mooreass630]

Yoda modulus Luke = Butt-pals. Vader modulus Luke= Incest. Jaba modulus Leia= Hotttt!

[@tapuroy2288]

thank u sir.

[@goksgk77]

hey dude i have a question for u what if u have 5 (2014 degree) mod 31??! u said it repeat but ur degree was not so big.. what if we have repeating of our number like u had 2 and 4 what algoritam then we should use ?!

[@timothyy7]

So "mod" is the remainder???

[@kapybara_park]

Does anyone know why this video has so many dislikes? Would it be about the quality of the video, or the content? Just asking since I found this video VERY helpful, but my paranoia is getting to me. Thanks. :)

[@MasterChiefFloyd]

I don't know if you'll see this since I'm seven months late in answering but the most likely answer is that some of Professor Farage's students do not like him for whatever reason and they go to his public content to down vote his public content. I am basing this theory off of the facts that Professor Farage: 1) Is very vocal about his beliefs on a wide range of subject matter in class 2) He has a relatively large online presence and he shares information about where to find his public posts with his classes 3) He typically uses a small number of tests for grades with no graded homework; this means that, although the tests are not particularly difficult, doing poorly on one test can make achieving a high grade in the course unlikely. This video has been up for seven years and as of right now has 64 dislikes; this is just over nine dislikes per year and under 5 dislikes per semester. Seeing as how he teaches at least four classes a semester it would not be difficult to find four to five disgruntled students with enough time on their hands to go down vote his content each semester. While every video on KZbin has at least a handful of random dislikes, it is plausible that this informative and concise educational video has a disproportionate amount of dislikes due to a handful of spiteful students. Aside from that I see at least one negative comment about the readability of his writing in the video. I have a test in his class in six hours and really should not be spending time typing this thorough explanation.

[@jamesmp7105]

Many Thanks

[@tlangimongwe6059]

What happened at 6:20? I don't get that

[@griffo780]

Thank you very much! So easy

[@anjaneyasharma322]

5^2 mod 7 =4 easy to understand But 5^1 mod 7 = 1 very difficult

[@lukushendrix]

How would I do 29^6431 mod 9 ? I'm stuck

[@denis5555]

Answer: 5. To check it. -> www.mtholyoke.edu/courses/quenell/s2003/ma139/js/powermod.html By the way, this is one of the best videos I've seen. And I saw many on this subject. It helps us to tackle the problem without the theorems with primes.

[@lukushendrix]

Thanks, that was one of our problems from my college Discrete math class :/

[@TimFarage]

That was a very nice coincidence. I'm glad it helped.

[@jwm239]

....starting with 29^1 thru 29^9, that will reveal a cycle of residues, then note the difference between 6431 and the exponent such that it is a multiple of the periodic cycle length (in this case, 9). To begin: 29 mod 9 == 2, 29^2 mod 9 == 4, 29^3 mod 9 = 8, 29^4 mod 9 = 7, 29^5 mod 9 = 5. wait...aha! 6431 minus 5 is 6426, a multiple of 9....! and now, it is very easy to finish up!

[@TimFarage]

I'm glad you recognized me. For the rest of you, I am the Ghost of Christmas Past.

[@pawel86able]

GUYS !!! I really need a help ! HOW WILL YOU DO IT FOR ODD EXPONENT ???? Cheers!

[@ms.appleshowtocookthatshow2207]

Perrrrfectttt

[@TimFarage]

Yes, 1 is correct.

[@JohanBjornborg]

Fantastic video. Thanks Tim. Also, does anyone know how to extend this to a double exponential? eg, a^b^c mod p?

[@lmafo4utube]

You have saved another person's *ss as well!

[@mandimorgan8279]

LLLLOLLLLs... Frogs are totally awesome.

[@AsadNaeemRana]

good video Thanks :)

[@lilfredd1393]

why 40??

[@EmperorCesar]

You saved my ass.

[@mitkogurbanski3136]

Thanks for upload sir...it helped me a lot :D Thumbs Up :D

[@sabdulhussain7163]

Aj morning Ka last no kitna hoga

[@ChristianvonSchleicher]

ALMOST AS INTERESTING AS FROGS!!!

[@disciplinenepal5081]

good from nepal

[@mathematicalcoffee2750]

Annnnnnnnd discrete math final in 3, 2, 1....

[@chukkiriyan]

Why do you sound so familiar?? Oh wait...

[@tachyonwolf]

Mouse handwriting XD I think he needs a tablet yes I agree. :p

[@austinreed7889]

Explain the darn thing you kept using words I do t understand

[@shadesvengeance]

l

[@terriblast8076]

NExt time write well.. unreadable hahaha

[@programefalas2011]

Thank you!

[@NeoChromer]

why 40???