1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursive algorithm

  1. Jan 29, 2006 #1
    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 dont know where to start :frown:

    thank you
    Last edited: Jan 29, 2006
  2. jcsd
  3. Jan 29, 2006 #2


    User Avatar
    Science Advisor

    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.
  4. Jan 30, 2006 #3
    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.
  5. Jan 30, 2006 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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: Jan 30, 2006
  6. Jan 30, 2006 #5
    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
  7. Jan 31, 2006 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I took you literally when you said "I don't know where to start".
  8. Jan 31, 2006 #7
    if every were only half as perfect as you then we might not need this home work area.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Recursive algorithm
  1. Recursive Limit (Replies: 6)

  2. Recursive function (Replies: 1)

  3. Recursive Serieses (Replies: 2)

  4. Convergence Recursive (Replies: 6)

  5. Recursive Definition (Replies: 2)