rayu's blog

Doubt related to Modular Multiplicative Inverse
By rayu, 10 years ago, In English

How can I find modular multiplicative inverses of a range in linear time?

  • Vote: I like it
  • +5
  • Vote: I do not like it

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

Do you want to find a multiplicative inverse for all numbers from 1 to N — 1?

It can be easily done for a prime N, the idea should be obvious if you'll read about primitive roots modulo N.

For non-prime N the idea should also be similar.

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

    I read about primitive roots that -

    If the prime number is p, a primitive root g is a number, that when n goes from [1...p - 1], then gn mod p goes through all the numbers [1...p - 1] in some order.

    How do I utilize this further? Sorry but I am unable to really understand how to form a relation between modular inverse and primitive root.

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

      If you thought harder, you'd come up with an idea :).

      Due to Fermat's Little Theorem: .

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

if the number with respect to which you are finding the modular inverse (i.e. the 'M' in A%M is prime)you can use the Fermat's little theorem according to which the modular inverse of a number with respect to a prime number (say A and P respectively) is pow(A,P-2)

so in one for loop you may find the modular multiplicative inverses of the numbers in the range but the complexity is O(nlogp) as the power function takes log(p) time

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

http://e-maxx.ru/algo/reverse_element#4 (it's in russian but you can see the code)

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

    Can you please explain the last step before QED in the proof provided?

    What have they done after taking mod m on both sides?

    → Reply