Finding Solutions for 2^k=n in $\mathbb{Z}/p$: Suggestions?

[CRGreathouse]

Is there a good algorithm for determining for what values of k 2^k=n in \mathbb{Z}/p? 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?

 

[robert Ihnot]

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?

 

[dalle]

Is there a good algorithm for determining for what values of k 2^k=n in \mathbb{Z}/p? 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?

dear CRGreathouse
have a look at the wikipedia pages on "discrete logarithm" and "hidden subgroup problem". Short answer: it is a hard problem.