मान लीजिए हमें चार पूर्णांक 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)