Devise Recursive Algorithm for x^n % m

  • Thread starter Thread starter neik
  • Start date Start date
  • Tags Tags
    Algorithm
Click For Summary

Homework Help Overview

The discussion revolves around devising a recursive algorithm to compute \( x^n \mod m \), where \( n \), \( x \), and \( m \) are positive integers. Participants are exploring the recursive relationship and the implementation details of the algorithm.

Discussion Character

  • Exploratory, Conceptual clarification, Problem interpretation

Approaches and Questions Raised

  • Some participants suggest defining a function and using recursive calls along with base cases. Others express uncertainty about starting points and the nature of recursive algorithms.

Discussion Status

The discussion includes various attempts to clarify the problem and explore the recursive nature of the algorithm. Some participants have provided hints and guidance, while others question the understanding of recursion and the problem's requirements. There is no explicit consensus on the approach yet.

Contextual Notes

Participants are navigating the boundaries of homework help, with some expressing frustration over the perceived simplicity of the problem and the requests for hints. The nature of the homework assignment and its expectations are also under discussion.

neik
Messages
15
Reaction score
0
Devise a recursive algorithm for finding [tex]x^n \bmod m[/tex] whenever n, x, and m are positive integers, based on the fact that

[tex]x^n \bmod m = (x^{n-1} \bmod m \cdot x \bmod m) \bmod m[/tex]

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

thank you
 
Last edited:
Physics news on Phys.org
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.
 
neik said:
Devise a recursive algorithm for finding [tex]x^n \bmod m[/tex] whenever n, x, and m are positive integers, based on the fact that

[tex]x^n \bmod m = (x^{n-1} \bmod m \cdot x \bmod m) \bmod m[/tex]

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

thank you
I guess that you would start with [tex]x^0 = 1[/tex] or [tex]x^1 = x \mod m[/tex]. Is this a homework problem? If so, see the first topic.
 
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! :frown:
 
Last edited:
thanks every one, i got the answer

Hurkyl said:
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! :frown:

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.
 
Last edited:
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".
 
if every were only half as perfect as you then we might not need this home work area.
 

Similar threads

Replies
3
Views
1K
Replies
8
Views
2K
  • · Replies 7 ·
Replies
7
Views
921
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 3 ·
Replies
3
Views
1K
  • · Replies 11 ·
Replies
11
Views
2K
Replies
4
Views
3K
  • · Replies 9 ·
Replies
9
Views
10K
  • · Replies 3 ·
Replies
3
Views
4K