Quick Math Question for you guru's

[MrScott81]

I need to know a good way to compute the following without actually doing the math. I know there is a cool trick you can use without having to compute values, but I can't remember!
(x^y) mod m

This is easy for small numbers, but for stuff like 20^105 % 48 it becomes ugly.
Can someone help? Thanks!
Scott

 

[shuan24]

hmm... can't say i've ever heard of that one.

 

[Gibson486]

Originally posted by: MrScott81
I need to know a good way to compute the following without actually doing the math. I know there is a cool trick you can use without having to compute values, but I can't remember!
(x^y) mod m

This is easy for small numbers, but for stuff like 20^105 % 48 it becomes ugly.
Can someone help? Thanks!
Scott

so, you want the first few digits of the remainder?

 

[Gunslinger08]

http://www.google.com/search?q...;ie=utf-8&oe=utf-8

 

[MrScott81]

Originally posted by: Gibson486

Originally posted by: MrScott81
I need to know a good way to compute the following without actually doing the math. I know there is a cool trick you can use without having to compute values, but I can't remember!
(x^y) mod m

This is easy for small numbers, but for stuff like 20^105 % 48 it becomes ugly.
Can someone help? Thanks!
Scott

so, you want the first few digits of the remainder?

No I need to compute x to the power of y modulo m.

Originally posted by: joshsquall
http://www.google.com/search?q...;ie=utf-8&oe=utf-8

Thanks, but this is for a computer program, so I can't hardcode stuff

Anyone else?? I know I learned this before!

 

[notfred]

Use the appropriate library:

C++
Perl
Java
etc...

Or, just use floating point numbers. Then just do ( x ** y ) % m or whatever.

 

[BullsOnParade]

n'mind i can't figure this out

 

[DAGTA]

Are you doing something dealing with encryption? Either way, many encryption algorithms use math similar to this and have very efficient algorithms for said math. It's been a few years so I don't recall the names of the specific algorithm but I know I used it while working with the Jacobi algorithm, so mabye a search on Jacobi will turn up something helpful for you.

 

[TuxDave]

Here's one identity... dunno what you can do with this.

x^y%m

let k = x%m

k^y%m=x^y%m

 

[MrScott81]

yep, this is for encryption.....
thanks TuxDave, that's exactly the formula I couldn't remember!!