rayu's blog

Doubt related to Modular Multiplicative Inverse
By rayu, 12 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

»
12 years ago, hide # |
 
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
  • »
    »
    12 years ago, hide # ^ |
     
    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
»
12 years ago, hide # |
 
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
»
12 years ago, hide # |
 
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