OmaeWaMouShenDeiru's blog

little math problem :D

By OmaeWaMouShenDeiru, 10 years ago, In English

hey guys :D

I have this small math problem,

( a * b ) mod n = 1

Given a, n:

find the smallest value of 'b' that satisfies the equation above.

any Idea about how to find the answer better than linear time search.

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +22 Vote: I do not like it

http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this is the same as finding the inverse of A (mod C) right ??

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, it's the same. Wikipedia article has some examples.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    one more question please, who to choose the proper values for a, n

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ikatanic any constraints on values other than 'a' and 'n' should be co primes ??

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nope. Extended Euclidean algorithm is used to solve the equation Ax+By=GCD(A,B) and since GCD(a,n)=1 the equation a*b-k*n=1=GCD(a,n) has infinitely many solutions.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But I found this statement on some website:

          "Only the numbers coprime to C (numbers that share no prime factors with C) have a modular inverse (mod C)"

          this is for the formula above in my post.

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          You are not right. GCD(a, n) must be equal to 1, otherwise it has no solution. You can read here

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            He knows that, I just said that there is not another constraint.

            → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

(a*b) mod n = 1 means that (a*b) = k*n+1 for some integer k>=0.

a*b-k*n = 1 is an equation of the form Ax+By=C which can be solved using Extended Euclidean algorithm.

Update: When I started writing my comment I didn't see that ikatanic has commented, sorry :)

→ Reply