在Python中实现俄罗斯农民乘法的程序

假设给我们四个整数p，q，r和k。我们将使用一种称为俄罗斯农民乘法方法的方法，并确定值(p + q.i)^r = r + s.i。我们必须返回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。

为了解决这个问题，我们将按照以下步骤进行：

• 如果r与0相同，则
  • 返回1
• 否则，当r等于1时，那么
  • 返回一对包含(p mod k，q mod k)的值
• 否则，当r mod 2与0相同时，那么
  • 返回solve((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)