पायथन में रूसी किसान गुणन को लागू करने का कार्यक्रम

मान लीजिए हमें चार पूर्णांक संख्याएँ 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 के समान हो, तो
  • रिटर्न सॉल्व ((p*p - q*q) mod k, 2*p*q mod k, r/2, k)
• अन्यथा,
  • एक जोड़ी (pr, qr) =हल करें(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)