Devise Recursive Algorithm for x^n % m

  • Thread starter neik
  • Start date
  • Tags
    Algorithm
In summary, the conversation discusses devising a recursive algorithm for finding x^n \bmod m, based on the given fact. The suggested approach is to define a function and use two ordinary mods and a recursive call. The conversation also includes a reminder about a possible base case and a question about understanding recursive algorithms. The person asking for hints expresses gratitude for the help and clarifies their intention to not ask for the answer directly. The conversation ends with a comment about perfection and the purpose of the homework area.
  • #1
neik
15
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
  • #2
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
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.
 
  • #4
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:
  • #5
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:
  • #6
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".
 
  • #7
if every were only half as perfect as you then we might not need this home work area.
 

1. What is a recursive algorithm?

A recursive algorithm is an algorithm that calls itself repeatedly until a base case is reached. This allows for solving complex problems by breaking them down into smaller, simpler instances.

2. How does a recursive algorithm for x^n % m work?

The recursive algorithm for x^n % m works by repeatedly squaring x until n is reduced to 0. Each time x is squared, it is multiplied by the remainder of the previous step mod m. This process is repeated until n is reduced to 0, at which point the final result is the remainder of the last step mod m.

3. What is the base case for this recursive algorithm?

The base case for this recursive algorithm is when n is equal to 0. In this case, the algorithm stops recursing and returns the remainder of the last step mod m as the final result.

4. How efficient is this recursive algorithm?

This recursive algorithm is quite efficient, as it only requires O(log n) time complexity. This is because each time the algorithm recurses, n is divided by 2, resulting in a logarithmic time complexity.

5. What are the potential applications of this recursive algorithm?

This recursive algorithm can be used in various applications, such as cryptography, computing large powers, and modular arithmetic. It can also be applied in any situation where a large number needs to be raised to a power and the remainder is needed when divided by another number.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
737
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
897
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
13
Views
682
Replies
5
Views
272
  • Calculus and Beyond Homework Help
Replies
8
Views
119
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
7K
Back
Top