алгоритмы для модульных инверсий

Question

Я прочитал раздел о Расширенном евклидовом алгоритме и модульных инверсиях, в котором говорится, что он не только вычисляет GCD(n,m), но также a и b так, что алгоритм a*n+b*b=1; описывается следующим образом:

1. Запишите n, m и два вектора (1,0) и (0,1)
2. Разделите большее из двух чисел на меньшее - назовите это частное q
3. Вычтите q раз меньшее из большего (т.е. уменьшите большее по модулю, меньшее)

(у меня есть вопрос, если мы обозначим через qn / m, тогда n-q*m is не равно 0? потому что q = n / m; (предположим, что n> m), так зачем нужна такая операция? тогда 4 шага

4. Вычтите q раз векторсоответствует меньшему из вектора, соответствующему большему 5. Повторите шаги с 2 по 4, пока результат не станет равным нулю 6. Опубликуйте предыдущий результат как gcd (n, m)

, поэтому мой вопрос для этогоПроблема также в том, как я могу реализовать эти шаги в коде? пожалуйста, помогите мне, я не знаю, какначало и с какого момента я могу начать решать такую ​​проблему, для уточнения результата она должна выглядеть следующим образом. Примером этого алгоритма является следующее вычисление 30 ^ (- 1) (мод 53);

53           30           (1,0)                        (0,1)
53-1*30=23   30           (1,0)-1*(0,1)=(1,-1)         (0,1)
23           30-1*23=7    (1,-1)                       (0,1)-1*(1,-1)=(-1,2)
23-3*7=2      7           (1,-1)-3*(-1,2)=(4,-7)       (-1,2)
2             7-3*2=1     (4,-7)                      (-1,2)-3*(4,7)=(-13,23)
2-2*1=0       1           (4,-7)-2*(-13,23)=(30,-53)   (-13,23)

Из этого мы видим, что gcd (30,53) = 1 и, переставляя члены, мы видим, что 1 = -13 * 53 + 23 * 30, поэтому мы заключаем, что 30 ^ (- 1) = 23 (мод 53).

Answer 1

Деление должно быть целочисленным делением с усечением.Стандартный советник для gcd(a, b) с a <= b выглядит следующим образом:

 b =  a * q0 + r0
 a = r0 * q1 + r1
r0 = r1 * q2 + r2
  ...
r[N+1] = 0

Теперь rN - это требуемый GCD.Затем вы заменяете:

r[N-1] = r[N] * q[N+1]

r[N-2] = r[N-1] * q[N] + r[N]
       = (r[N] * q[N+1]) * q[N] + r[N]
       = r[N] * (q[N+1] * q[N] + 1)

r[N-3] = r[N-2] * q[N-1] + r[N-1]
       = ... <substitute> ...

Пока вы, наконец, не достигнете rN = m * a + n * b.Алгоритм, который вы описываете, сразу отслеживает данные обратного отслеживания, поэтому он немного более эффективен.

Если rN == gcd(a, b) == 1, то вы действительно нашли мультипликативную инверсию a по модулю b, а именно m: (a * m) % b == 1.