Skip to main content

Posts

Showing posts from June, 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.