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

2^k = n in Z/p

  1. Jan 15, 2008 #1


    User Avatar
    Science Advisor
    Homework Helper

    Is there a good algorithm for determining for what values of k [itex]2^k=n[/itex] in [itex]\mathbb{Z}/p[/itex]? I expect the number of solutions for k to be either 0 or a number dividing p-1, but beyond that I have nothing but brute force. Suggestions?

    I think this is a fairly basic question, but I can't think of an answer. Can someone point me in the right direction?
  2. jcsd
  3. Jan 16, 2008 #2
    If you look this up on the Sloan table A001918, it will give you least primitative roots, if you also obtain a list that orders the primes. In this case, for example prime(35) = 149, and has 2 as a primitative root. Thus, there is always a solution to 2^k==n Mod 149. But beyond that the matter is much more difficult. Solving 2^k==50 Mod 149, I find somehow that 2^30==-5 Mod 149, and thus 2^61==50 Mod 149.

    But, you probably know all this already. So, no, I don't think any kind of easy answer is available, since if it was, why bother to even compile primitative roots?
    Last edited: Jan 16, 2008
  4. Jan 17, 2008 #3
    dear CRGreathouse
    have a look at the wikipedia pages on "discrete logarithm" and "hidden subgroup problem". Short answer: it is a hard problem.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook