পাইথনে রাশিয়ান কৃষক গুণ প্রয়োগ করার প্রোগ্রাম

ধরুন আমাদের চারটি পূর্ণসংখ্যা দেওয়া হল 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, r mod k =6561 এর q =0 মান হিসাবে .

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• যদি 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)