36 / 62
36
นิตยสาร สสวท.
เฉพาะสองจำ
�นวนที่เป็นตัวประกอบของจำ
�นวนเต็มจำ
�นวนหนึ่ง
ที่เลือก ในการสร้างและทำ
�ความเข้าใจระบบดังกล่าว จะต้องมี
ความรู้ทางคณิตศาสตร์ต่อไปนี้
พื้นฐานทางคณิตศาสตร์ที่ต้องใช้
คณิตศาสตร์ที่ต้องใช้ในการทำ
�ความเข้าใจเรื่องการเข้าและ
ถอดรหัสลับที่จะกล่าวในที่นี้ ได้แก่ การหาตัวหารร่วมมากของ
จำ
�นวนเต็มบวกสองจำ
�นวน ความรู้เรื่องออยเลอร์ฟีฟังก์ชัน และ
ความรู้เรื่องจำ
�นวนเต็ม มอดุโล n พร้อมทั้งทฤษฎีบทที่เกี่ยวข้อง
บางทฤษฎี
ขั้นตอนวิธียุคลิด (Euclidean Algorithm)
ถ้า x และ y
เป็นจำ
�นวนเต็มบวกสองจำ
�นวนที่ไม่ใช่ 0 พร้อมกันแล้ว เราจะ
แทนตัวหารร่วมมากของ x และ y ด้วย gcd (x, y) เราอาจหา
ตัวหารร่วมมาก โดยใช้วิธีแยกตัวประกอบเหมือนที่เคยเรียนใน
ระดับมัธยมก็ได้ เช่น การหาตัวหารร่วมมาก ของ 420 และ 90
เราแยกตัวประกอบของ 420 และ 90 ดังนี้
420 = 2
2
× 3×5×7 และ
90 = 2×3
2
×5
ดังนั้น ตัวหารร่วมมากของ 420 และ 90 คือ 2×3×5 = 30 กล่าวคือ
gcd (90, 420) = 30 นอกเหนือจากวิธีการแยกตัวประกอบแล้ว
ขั้นตอนวิธียุคลิดเป็นกระบวนการสำ
�หรับหาตัวหารร่วมมากของ
จำ
�นวนสองจำ
�นวนที่ใช้ความรู้พื้นฐานเรื่องการหารยาว ในการ
หารยาวเราจะได้ผลหารและเศษ ใช้วิธีหารยาวซ้ำ
�กันไปเรื่อย ๆ
จนกว่าจะได้เศษเป็นศูนย์ ดังนี้
ในแต่ละขั้นตอน เราหารตัวหารในขั้นตอนก่อนหน้านั้นด้วย
เศษ ซึ่งจะทำ
�ให้เศษมีค่าเล็กลงตามลำ
�ดับ ในที่สุดต้องมีค่าเป็น
ศูนย์ กล่าวคือ y > r
1
> r
2
> r
3
> … ≥ 0 ถ้า r
t
เป็นเศษตัว
สุดท้ายที่ไม่ใช่ศูนย์แล้ว gcd (x, y) = r
t
เรียกขั้นตอนการหาตัว
หารร่วมมาก โดยวิธีนี้ว่า ขั้นตอนวิธียุคลิด
ตัวอย่าง 1
จงหา gcd (420, 90)
(1)
420 = 4 . 90 + 60 หาร x = 420 ด้วย y = 90
ได้ผลลัพธ์ q
1
= 4 และเศษ r
1
= 60
(2)
90 = 1 . 60 + 30 หาร y = 90 ด้วย r
1
= 60
ได้ผลลัพธ์ q
2
= 1 และเศษ r
2
= 30
(3)
60 = 2 . 30 หาร r
1
= 60 ด้วย r
2
= 30
ได้ผลลัพธ์ q
3
= 2 และเศษ r
3
= 0
แสดงว่า gcd (420, 90) = 30 = r
2
ซึ่งเป็นเศษตัวสุดท้ายที่
ไม่ใช่ศูนย์ ซึ่งตรงกับค่าที่หาได้ด้วยวิธีแยกตัวประกอบ
จากขั้นตอน (2) ข้างบนนี้ ถ้าเราเขียน 30 ใหม่ แล้วแทนค่า
ย้อนกลับขึ้นไปเรื่อยจะได้
เราได้ 30 = 5 . 90 – 1 . 420
ในกรณีทั่วไป ถ้า gcd (x, y) = d แล้ว เราสามารถเขียน
d ในรูป ax + by = d โดยที่ a และ b คือจำ
�นวนเต็มบาง
จำ
�นวน เรียก d ที่เขียนในรูปแบบนี้ว่า รูปการรวมเชิงเส้นของ
x และ y ในตัวอย่าง 1 จะเห็นว่า gcd (420, 90) = 30 และ
30 = 5 . 90 – 1 . 420 ในที่นี้ a = 5 และ b = –1 ในกรณี
เฉพาะ ถ้า gcd (x, y) = 1 แล้วเราย่อมหา a และ b ซึ่งทำ
�ให้
ax + by = 1 ได้เสมอ
ตัวอย่าง 2
จงหา gcd (192, 7)
(1)
192 = 27 . 7 + 3 หาร x = 192 ด้วย y = 7
ได้ผลลัพธ์ q
1
= 27 และเศษ r
1
= 3
(2)
7 = 2 . 3 + 1 หาร y = 7 ด้วย r
1
= 3
ได้ผลลัพธ์ q
2
= 2 และเศษ r
2
= 1
(3)
3 = 3 . 1 หาร r
1
= 3 ด้วย r
2
= 1
ได้ผลลัพธ์ q
3
= 3 และเศษ r
3
= 0
แสดงว่า gcd (192, 7) = 1 = r
2
ซึ่งเป็นเศษตัวสุดท้ายที่
ไม่ใช่ศูนย์
30 =
=
=
=
=
=
90
90
90
(90
(1
–
–
–
+
+
–
–
+
–
–
1 . 60
1 . (420
1 . 420
4 . 90)
4) . 90
1 . 420
4 . 90)
4 . 9 0
1 . 420
1 . 420
x
y
r
1
r
t
– 2
r
t-1
=
=
=
=
=
q
1
y + r
1
q
2
r
1
+ r
2
q
3
r
2
+ r
3
q
t
r
t
– 1
+ r
t
q
t+1
r
t
หาร x
หาร y
หาร r
1
หาร r
t –2
หาร r
t –1
ด้วย y
ด้วย r
1
ด้วย r
2
ด้วย r
t – 1
ด้วย r
t
ได้ผลลัพธ์ q
1
ได้ผลลัพธ์ q
2
ได้ผลลัพธ์ q
3
ได้ผลลัพธ์ q
t
ได้ผลลัพธ์ q
t+1
และเศษ r
1
และเศษ r
2
และเศษ r
3
และเศษ r
t
และเศษเป็นศูนย์
5 . 90