在 Python 中应用俄罗斯农民乘法的程序

假设我们有四个整数 p、q、r 和 k。我们将使用一种称为俄罗斯农民乘法的方法并确定 (p + qi)^r = r + si 的值我们必须返回 r mod k 和 s mod k 的值。

所以，如果输入像 p = 3, q = 0, r = 8, k = 10000，那么输出将是 (6561, 0) 3^8 = 6561，因为 q = 0 r mod k = 6561 的值.

示例

让我们看看以下实现以获得更好的理解 -

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)