Devise Recursive Algorithm for x^n % m

[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 don't know where to start

thank you

 

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

 

[ramsey2879]

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 don't know where to start

thank you

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.

 

[Hurkyl]

can anyone give me some hints? i don't know where to start

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!

 

[neik]

thanks every one, i got the answer

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!

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

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

 

[Hurkyl]

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

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

 

[neik]

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