Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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

    0rthodontist

    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

    Hurkyl

    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

    Hurkyl

    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook