Tuesday, June 30, 2009

Looking for efficient algorithm to solve x^y mod z

I am in the middle of coding and suddenly realized that I have to solve (code) x^y mod z, where x, y, and z are large integer numbers. Straight coding, that is by multiplying x by y times before performing mod with z, is inefficient.

I know that I am dealing with big integers, but my interest is in the algorithm. I am reading fast exponentiation right now, but just in case any of you know better algorithms (or libraries). I am using C language, if that's important.

3 comments:

cryptocodecg said...

big headache! :D

website dunia veteriner said...

salam luar biasa .... nice post!

Rifki said...

Is in C Support big integer ?
as i know, it just support in java.