| [ผู้มาเยือน (113.218.*.*)]ตอบ [จีน ] | เวลา :2024-06-24 | ขยายอัลกอริทึมของยุคลิด
อัลกอริทึมแบบยุคลิดแบบขยายหรือเรียกสั้น ๆ ว่า EXGCD โดยทั่วไปจะใช้เพื่อแก้สมการไม่แน่นอนสมการความสอดคล้องเชิงเส้นองค์ประกอบผกผันของโมดูโลและอื่น ๆ
คําหลัก: การปรากฏตัวของ x , y เป็นเช่นนั้น gcd(a,b)=ax by
พิสูจน์:
เมื่อ b=0, gcd(a,b)=a ซึ่งจุด x=1, y=0
เมื่อ b!=0,
ให้ ax1 by1=gcd(a,b)=gcd(b,a%b)=bx2 (a%b)y2
และเพราะ a%b=a-a/b*b
จากนั้น AX1 By1=Bx2 (AA/B*B)Y2
AX1 By1=Bx2 AY2-A/B*By2
AX1 By1=AY2 BX2-B*A/B*Y2
AX1 By1=AY2 B(x2-A/B*Y2)
สารละลายให้ผลลัพธ์ x1=y2 , y1=x2-a/b*y2
เพราะเมื่อ b=0 มี x, y คือชุดสุดท้ายของการแก้ปัญหา
วิธีแก้ปัญหาสําหรับแต่ละกลุ่มสามารถหาได้จากกลุ่มหลัง
ดังนั้นการแก้ปัญหาของกลุ่มแรก x , y จะต้องมีอยู่
พิสูจน์
จากหลักฐานข้างต้นจะใช้แนวทางปฏิบัติแบบเรียกซ้ําเมื่อนําไปใช้
ดําเนินการซ้ําไปยังเลเยอร์ถัดไป และส่งกลับ x=1 และ y=0 เมื่อถึงเลเยอร์สุดท้าย ซึ่งก็คือ b=0
จากนั้นตาม x=y' , y=x'-a/b/y' ( x' และ y' คือ x และ y ของเลเยอร์ถัดไป ) เพื่อให้ได้คําตอบของเลเยอร์ปัจจุบัน
คํานวณโซลูชันของเลเยอร์ปัจจุบันและส่งคืนอย่างต่อเนื่อง และสุดท้ายกลับไปที่เลเยอร์แรกเพื่อรับโซลูชันดั้งเดิม |
|
