Pythonでロシアの農民の乗算を適用するプログラム

4つの整数p、q、r、およびkが与えられているとします。ロシア農民乗算法と呼ばれる方法を使用して、（p + q.i）^ r =r+s.iの値を決定します。 rmodkとsmodkの値を返す必要があります。

したがって、入力がp =3、q =0、r =8、k =10000の場合、r mod k=6561のq=0値として、出力は（6561、0）3 ^ 8=6561になります。 。

これを解決するには、次の手順に従います-

• rが0と同じ場合、
  • 1を返す
• それ以外の場合、rが1と同じ場合、
  • （p mod k、q mod k）を含むペアを返します
• それ以外の場合、r mod 2が0と同じ場合、
  • returnsolve（（p * p-q * q）mod k、2 * p * q mod k、r / 2、k）
• それ以外の場合、
  • ペア（pr、qr）=solve（p、q、r-1、k）
  • （（p * pr --q * qr）mod k、（p * qr + q * pr）mod k）を含むペアを返します

例

理解を深めるために、次の実装を見てみましょう-

def solve(p, q, r, k):
   if r == 0:
      return 1
   elif r == 1:
      return (p % k, q % k)
   elif r % 2 == 0:
      return solve((p*p - q*q) % k, 2*p*q % k, r/2, k)
   else:
      (pr, qr) = solve(p, q, r-1, k)
      return ((p * pr - q * qr) % k, (p * qr + q * pr) % k)

print(solve(3, 0, 8, 10000))

入力

3, 0, 8, 10000

出力

(6561, 0)