Modular Exponentiation

Shows how to do a modular exponentiation, sometimes called a power mod. For instance, 3^100 mod 7 is a power mod.

Category:

Education

Tags:

• Math
• Discrete
• Modular
• Exponentiation
• Power
• Mods

[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.

[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!

[timfarage]

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

[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]

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

[asdi744]

good video Thanks :)

[chukkiriyan]

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

[laurasparta99]

If this is without a calculator who the heck knows 5^32 off the top of their heads?!?! no one!!!!

[pramesh501]

thax foh this video..was helpful..

[2927challenger]

Thanks so much !

[TheDearNightmare]

This was very helpful, the example in my book is very bad, but it makes sense after seeing someone do it. Not too hard after all, thanks