Блог пользователя rayu

Автор rayu, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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