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

How can I find a x such that the order of 2 mod x is n?

  1. Jan 20, 2014 #1
    Is there an algorithm which, given n, returns an integer x such that 2 has order n modulo x (i.e, 2^n = 1 mod x and n is the smallest positive solution)? Is there any such algorithm which runs faster than factoring n?
     
  2. jcsd
  3. Jan 20, 2014 #2

    jgens

    User Avatar
    Gold Member

    How about x = 2n-1?
     
  4. Jan 20, 2014 #3
    Well... this is much simpler than I expected :redface:
    I guess I should have thought a bit more before posting that... I was convinced this would involve some advanced math and big time complexity.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How can I find a x such that the order of 2 mod x is n?
  1. Solving x^{n}+a=mod(b) (Replies: 8)

Loading...