Как найти обратный модуль числа, т. Е. (% M), когда m не является простым

Question

Я искал ответ на этот вопрос, я получил различные полезные ссылки, но когда я реализовал идею, я получаю неправильный ответ.

Вот что я понял:

Если m простое, то это очень просто. Обратный модуль любого числа "а" можно рассчитать как:inverse_mod(a) = (a^(m-2))%m

но когда m не простое число, мы должны найти простые множители m, т.е. m= (p1^a1)*(p2^a2)*....*(pk^ak). Здесь p1,p2,....,pk - главные множители m, а a1,a2,....,ak - их соответствующие степени.

тогда мы должны рассчитать:

m1 = a%(p1^a1),

m2 = a%(p2^a2), 

.......

mk = a%(pk^ak)

затем мы должны объединить все эти остатки, используя теорему китайского остатка ( https://en.wikipedia.org/wiki/Chinese_remainder_theorem)

Я реализовал эту идею для m=1000 000 000, но все же я получаю неправильный ответ.

Вот мое объяснение для m=1000 000 000, который не является простым

m= (2^9)*(5^9) где 2 и 5 - главные факторы м.

пусть a - это число, для которого нужно вычислить обратное по модулю m.

m1 = a%(2^9) = a^512

m2 = a%(5^9) = a^1953125

Our answer will be = m1*e1 + m2*e2

where e1= {  1 (mod 512)

             0 (mod 1953125)
          }
  and e2= {     1 (mod 1953125)

                0 (mod 512)
           } 

Теперь, чтобы вычислить "e1" и "e 2", я использовал расширенный евклидов алгоритм. https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Кодекс это:

    void extend_euclid(lld a,lld b,lld& x,lld& y)
    {
          if(a%b==0)
          {
             x=0;
             y=1;
             return ;
          }
          extend_euclid(b,a%b,x,y);
          int tmp=x;
          x=y;
          y=tmp-(a/b)*y;
    }

Now e1= 1953125*y and e2=512*y;

So, Our final answer will be = m1*e1 + m2*e2 .

Но после всего этого я получаю неправильный ответ.

пожалуйста, объясните и укажите на любые ошибки, которые я допустил, понимая теорему об остатках в Китае.

Большое спасибо вам.

Answer 1

Обратное a по модулю m существует только если a а также m взаимно просты Если они не взаимно просты, ничто не поможет. Например: что является обратным 2 модификация 4?

2*0 = 0 mod 4
2*1 = 2 mod 4
2*2 = 0 mod 4
2*3 = 2 mod 4

Так что нет обратного.

Это действительно может быть вычислено с использованием расширенного евклидова алгоритма (хотя я не уверен, правильно ли вы это делаете), но самый простой способ, на мой взгляд, заключается в использовании теоремы Эйлера:

a^phi(m) = 1 (mod m)
a*a^(phi(m) - 1) = 1 (mod m)
=> a^(phi(m) - 1) is the invers of a (mod m)

куда phi это общая функция:

phi(x) = x * (1 - 1/f1)(1 - 1/f2)...(1 - 1/fk)
where fi > 1 is a divisor of x (not necessarily a prime divisor)

phi(36) = 36(1 - 1/2)(1 - 1/3)(1 - 1/4)(1 - 1/6)(1 - 1/9)(1 - 1/12)(1 - 1/18)(1 - 1/36)

Так что это может быть вычислено в O(sqrt n),

Возведение в степень может затем быть вычислено с использованием возведения в степень путем возведения в квадрат.

Если вы хотите прочитать о том, как вы можете использовать расширенный евклидов алгоритм, чтобы быстрее найти обратное, прочитайте это. Я не думаю, что китайская теорема об остатке может помочь здесь.

Answer 2

Я считаю, что следующая функция будет делать то, что вы хотите. Меняться от long в int при необходимости. Возвращает -1, если обратного нет, в противном случае возвращает положительное число в диапазоне [0..m),

  public static long inverse(long a, long m) { // mult. inverse of a mod m
    long r = m;
    long nr = a;
    long t = 0;
    long nt = 1;
    long tmp;
    while (nr != 0) {
      long q = r/nr;
      tmp = nt; nt = t - q*nt; t = tmp;
      tmp = nr; nr = r - q*nr; r = tmp;
    }
    if (r > 1) return -1; // no inverse
    if (t < 0) t += m;
    return t;
  }

Я не могу следовать вашему алгоритму, чтобы точно понять, что с ним не так, но у меня есть несколько общих замечаний: общая функция Эйлера вычисляется довольно медленно, в зависимости от простых факторизаций. Китайская теорема об остатках полезна во многих контекстах для комбинирования результатов модов, но в этом нет необходимости, здесь и снова усложняется эта конкретная проблема, потому что в конечном итоге вам приходится учитывать свой модуль, очень медленная операция. И быстрее реализовать GCD и модульную инверсию в цикле, чем использовать рекурсию, хотя, конечно, оба метода одинаково эффективны.

Answer 3

Если вы пытаетесь вычислить ^ (- 1) mod p ^ k для простого p, сначала вычислите ^ (- 1) mod p. Учитывая, что x такой, что ax = 1 (mod p ^ (k-1)), вы можете "поднять Hensel" --- вы ищете y между 0 и p-1, такой что a (x + yp ^ (к-1)) = 1 (мод р ^ к). Делая некоторую алгебру, вы обнаружите, что вы ищете y такой, что ayp ^ (k-1) = 1 - ax (mod p ^ k) --- т.е. ay = (1 - ax) / p ^ (k- 1) (mod p), где деление на p ^ (k-1) является точным. Вы можете решить это, используя модульное обратное для (мод p).

(В качестве альтернативы просто обратите внимание, что a ^ (p ^ (k-1) (p-1) - 1) = 1 (mod p ^ k). Я упоминаю подъем Хенселя, потому что он работает в гораздо большей общности.)