สมมติว่าเราได้รับเลขจำนวนเต็มสี่ตัว p, q, r และ k เราจะใช้วิธีที่เรียกว่า Russian Peasant Multiplication method และกำหนดค่าของ (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)
