Recursive algorithm

1. Jan 29, 2006

neik

Devise a recursive algorithm for finding $$x^n \bmod m$$ whenever n, x, and m are positive integers, based on the fact that

$$x^n \bmod m = (x^{n-1} \bmod m \cdot x \bmod m) \bmod m$$

can anyone give me some hints? i dont know where to start

thank you

Last edited: Jan 29, 2006
2. Jan 29, 2006

0rthodontist

Well, it's pretty much given to you. Define a function

powermod(x, n, m)

Inside this function you will use 2 ordinary mods and a recursive call to powermod. Don't forget a base case.

3. Jan 30, 2006

ramsey2879

I guess that you would start with $$x^0 = 1$$ or $$x^1 = x \mod m$$. Is this a homework problem? If so, see the first topic.

4. Jan 30, 2006

Hurkyl

Staff Emeritus
I hate to ask, but do you even know what a recursive algorithm is? This is a fill-in-the-blanks type problem... and you've been handed almost the entire answer!

Last edited: Jan 30, 2006
5. Jan 30, 2006

neik

thanks every one, i got the answer

thats why i have to ask 'coz its too good to be true.
i dont think this question hurts you, does it?

its not your fault if you dont understand the question; but it is if you dont know how to ask. Besides, i only ask for hint and not the answer.

Last edited: Jan 30, 2006
6. Jan 31, 2006

Hurkyl

Staff Emeritus
I took you literally when you said "I don't know where to start".

7. Jan 31, 2006

neik

if every were only half as perfect as you then we might not need this home work area.