มาทำความรู้จักกับหนึ่งในอัลกอริทึมที่คนที่ศึกษาควอนตัมคอมพิวเตอร์ต้องรู้จัก . . .
หลายคนอาจจะเคยได้ยินวลีที่ว่า “ควอนตัมคอมพิวเตอร์จะเข้ามาทำลายคริปโต”, “ควอนตัมคอมพิวเตอร์จะทำให้การเข้ารหัสนั้นไร้ประโยชน์” หรือว่าจะเป็น “ควอนตัมคอมพิวเตอร์จะเข้ามาทำลายบล็อคเชน!?” วลีที่ได้ยินเหล่านี้นั้นมาจากการเกิดขึ้นของอัลกอริทึมที่จะนำเสนอในวันนี้นั่นก็คือ Shor’s Algorithm
เกริ่นนำ
ในปี ค.ศ.1994 หรือเมื่อ 28 ปีที่แล้ว นักคณิตศาสตร์ที่ชื่อว่า “ปีเตอร์ ชอร์” ได้ทำการคิด Quantum Algorithm สำหรับใช้ในการแยกตัวประกอบของจำนวนเต็มบนเครื่อง Quantum Computer เช่น ให้จำนวนเต็ม N มาแล้วหาตัวประกอบเฉพาะของจำนวนเต็ม N โดยที่สิ่งนี้นั่นได้ถูกโยงเข้าไปเกี่ยวกับศาสตร์ของการเข้ารหัส (encryption) ซึ่งเป็นสิ่งที่ท้าทายกลไกการเข้ารหัสในยุคปัจจุบันอย่าง RSA เป็นอย่างมาก
กลไกการเข้ารหัสของ RSA
เป้าหมายของการเข้ารหัสนั้นคือ การแปลงข้อมูล (garble data) ที่ต่อให้คนที่มีข้อมูลนี้อยู่นั้นก็ไม่สามารถอ่านมันได้ โดยที่กลไกการเข้ารหัสของ RSA นั้นคือ “ผู้รับข้อมูลจะหลีกเลี่ยงที่จะบอก KEY ในการเข้ารหัสให้แก่ผู้ส่งข้อมูล แต่จะบอกผลคูณของตัวเลขซึ่งเกิดจาก KEY ไปให้ผู้ส่งข้อมูลแทน ซึ่งผู้ส่งข้อมูลเองก็ไม่สามารถรู้ได้ว่าตัวเลขนั้นคือผลคูณของอะไร แต่เอาตัวเลขนั้นไปเข้ารหัสแล้วผู้รับถอดรหัสข้อมูลได้ก็แล้วกัน ในเมื่อผู้ส่งข้อความเองยังไม่รู้ KEY ในการถอดรหัส ดังนั้นจึงไม่ต้องกลัวว่าใครจะมาขโมยข้อมูลไประหว่างทาง เพราะถ้าไม่รู้ KEY ยังไงก็ถอดรหัสไม่ได้” ดังนั้นการรักษาความลับของข้อมูลคือการที่ไม่บอกให้ใครรู้ว่า KEY ที่แท้จริงคือเลขอะไร ความยากเลยไม่ตกอยู่ที่การแยกตัวประกอบหรือการหาต้นตอของผลคูณ นี่คือหัวใจสำคัญของ RSA ฟังดูเหมือนเป็นแค่การแยกตัวประกอบธรรมดา แต่! ถ้าเป็นเลขที่มีขนาดใหญ่มากนั้นจะใช้เวลาในการแยกตัวประกอบที่นานมาก
ยกตัวอย่าง
สมมติให้หาผลคูณระหว่าง 555 * 666 (โดยไม่ใช้เครื่องคิดเลขนะครับ 😅) หลายคนอาจจะมีวิธีที่แตกต่างกัน แต่หนึ่งในนั้นคือ การแยกตัวประกอบของ 555 และ 666 ออกมาแล้วค่อยนำมาบวกกัน ซึ่งจะทำให้วิธีคิดนั้นง่ายขึ้น
แต่ถ้าเกิดโจทย์ปัญหาเป็น ให้หาค่าที่คูณกันแล้วได้ 456456 หรือ ให้หาค่า x และ y ของโจทย์: 456456 = x * y คงเป็นโจทย์ที่ยากมากขึ้นและต้องใช้เวลาที่นานมากในการหาคำตอบ (แม้จะใช้คอมพิวเตอร์ก็ตาม)
โดยที่ Algorithm บน Classical Computer ในปัจจุบันที่สามารถแยกตัวประกอบได้เร็วที่อย่าง GNFS ยังใช้เวลาถึง O( e^(1.9(n^(1/3))((logn)^2/3)) ) ที่ n คือจำนวนของ bit ที่ของจำนวนที่ต้องการแยก จะเห็นว่ายังต้องใช้ระยะเวลาที่มากพอสมควรในการแยกตัวประกอบ
แต่ใน Shor’s Algorithm จะใช้ระยะเวลาไม่เกินฟังก์ชัน Polynomial ของขนาดข้อมูล หรือใช้เวลาเป็น O ( (log N) 3) ที่จะเป็นการแก้ปัญหาการแยกตัวประกอบของจำนวนเต็มที่มีประสิทธิภาพใน Quantum Computer
ขั้นตอนของ Shor’s Algorithm
ก่อนที่จะเริ่มขั้นตอนของ Shor’s Algorithm นั้นมี Algorithm นึงที่เป็นส่วนประกอบที่สำคัญอย่างมากและทุกคนน่าจะเคยได้เรียนสมัยมัธยมแล้วนั่นก็คือ Euclid’s Algorithm ถ้าทุกคนพอรู้จักขั้นตอนของ Euclid แล้วเรามาเริ่มกันเลย !
หมายเหตุ: ตัวเลขที่จะทำการเลือกมาเพื่อใช้ในการแยกตัวประกอบนั้น
จะมีเงื่อนไข ดังนี้ 1.ไม่เป็นจำนวนเฉพาะ 2.เป็นเลขคี่ 3.ไม่อยู่ในรูป n*(n^x)
โจทย์ของเรานั้น คือการที่เราได้รับเลขตัวหนึ่ง (N) แล้วต้องการแยกตัวประกอบว่าเกิดจากตัวเลขอะไรคูณกัน เช่น 25 = 5x5 หรือ 35 = 5x7 อะไรทำนองนี้
ขั้นตอนที่ 1: ทำการ กำหนดค่า ของ N หรือตัวเลขที่เราต้องแยกตัวประกอบ (ในที่นี่จะทำการกำหนดเป็นเลขที่มีค่าน้อยเพื่อง่ายต่อการคำนวณและเห็นภาพมากยิ่งขึ้น)
กำหนด N = 15
ขั้นตอนที่ 2: ทำ การสุ่ม ตัวเลขระหว่าง 1 ถึง N (ในบางที่จะให้สุ่มระหว่าง 2 ถึง N-1) แล้วแทนเลขนั้นด้วย “k”
ทำการสุ่มเป็นเลข 7 ดังนั้นค่า k ของเราจะเท่ากับ 7 (k=7)
ขั้นตอนที่ 3: หาค่า GCD หรือ ห.ร.ม. ของ N และ k หรือ GCD(N,k) โดยที่สามารถใช้ Euclid’s Algorithm ในการหาได้ ซึ่งหากผลลัพธ์ไม่เท่ากับ 1 แสดงว่า k คือคำตอบของคุณ แล้วไม่ต้องทำขั้นตอนต่อไปแล้ว 😂 แต่หากผลลัพธ์เท่ากับ 1 ให้ทำการไปที่ขั้นตอนต่อไป
หา GCD(15,7) ซึ่งจะได้คำตอบเท่ากับ 1 ดังนั้นไปที่ขั้นตอนต่อไป
ขั้นตอนที่ 4: ให้ทำการหาคาบของฟังก์ชันนี้หรือเรียกค่านี้ว่า “r” โดยที่ดูค่าจากฟังก์ชัน f(x) = kˣ mod N ที่จะพบว่าจะเป็นแพทเทิร์นซ้ำ ๆ จนเป็นคาบ ให้หาว่าคาบของฟังก์ชันนี้มีค่าเท่าไหร่ โดยสามารถทำตามขั้นตอนได้ดังนี้
ขั้นตอนที่ 4.1: ทำการกำหนดตัวแปร q = 1 สำหรับใช้ในขั้นตอนต่อไป
ขั้นตอนที่ 4.2: หาค่า (qxk) mod N ซึ่งหากส่วนที่เหลือจากสมการเท่ากับ 1 ให้ไปขั้นตอนต่อไป หากส่วนที่เหลือจากสมการไม่เท่ากับ 1 ให้กำหนดตัวแปร q เป็นส่วนที่เหลือที่ได้รับ แล้วทำซ้ำจนกว่าจะได้ส่วนที่เหลือเท่ากับ 1 (โดยที่ค่า q ต้องไปซ้ำกัน)
จาก q = 1, k = 7, N = 1 ทำการหาค่าคาบจาก (qxk) mod N
จะเห็นว่าจะใช้จำนวนของการหาค่าส่วนที่เหลือเป็น 1 อยู่ที่ 4 ครั้ง
ดังนั้นค่าของคาบ หรือ “r” จะมีค่าเท่ากับ 4
ขั้นตอนที่ 5: หากค่า r ที่ได้เป็นเลขคี่ ให้ย้อนกลับไปที่ขั้นตอนที่ 2 แล้วเลือกค่า k ใหม่
ขั้นตอนที่ 6: ทำการกำหนดค่า “p” เท่ากับจำนวนส่วนที่เหลือของจำนวนรอบ/2 หรือ r/2 โดยที่หากค่า p+1 = N ให้ย้อนกลับไปขั้นตอนที่ 2 แล้วเลือกค่า k ใหม่
จากโจทย์จะได้ว่า ค่า p จะมีค่าเท่ากับจำนวนรอบ/2 หรือก็คือ r/2 จะได้ว่า 4/2 หรือเป็นจำนวนรอบครั้งที่สอง จะได้ค่าส่วนที่เหลือเป็น
ดังนั้นค่า p = 4 ดังนั้นทำการพิสูจน์ว่า p+1 = N หรือไม่
ซึ่ง 4+1 ≠ 15 ให้ไปขั้นตอนต่อไปเลย !
ขั้นตอนที่ 7: นี่คือขั้นตอนสุดท้ายในการหาตัวประกอบด้วย Shor’s Algorithm แล้ว !
โดยที่ตัวประกอบของ N คือ
f1 (ตัวประกอบตัวแรก) = GCD(p+1, N) และ
f2 (ตัวประกอบตัวสอง) = GCD(p-1, N)
จาก p = 4, N = 15 ดังนั้น
f1 = GCD(4+1, 15) = GCD(5, 15) = 5
f2 = GCD(4–1, 15) = GCD(3, 15) = 3
ดังนั้น ตัวประกอบของ 15 หรือ N นั้นจะมีค่าเท่ากับ 3 และ 5 นั่นเอง !
ก็จบกันไปแล้วกับขั้นตอนของ Shor’s Algorithm ที่จะเห็นว่าขั้นตอนนั้นดูไม่ยุ่งยากและน่าจะทำให้ทุกคนเข้าใจได้ไม่ยากมากเลย แถมยังสามารถหาค่าของตัวประกอบได้เร็วอีกด้วย 😍
สรุป
Shor’s Algorithm นั้นเป็นเทคนิคในการหาตัวประกอบบน Quantum Computer ที่มีประสิทธิภาพมาก ที่เป็น Algorithm ที่จะทำให้การเข้ารหัสอย่าง RSA นั้นดูง่ายมากยิ่งขึ้นบน Quantum Computer ซึ่งในอนาคตนั้นหาก Quantum Computer นั้นเป็นที่แพร่หลายมากยิ่งขึ้นและสามารถเข้ามาแทนที่ Classical Computer ได้จริง ปัญหาเข้ารหัสนั้นอาจจะเป็นสิ่งที่ทำให้เหล่า Cyber Security ต้องหาหนทางมาเพื่อป้องกันความเร็วของ Quantum Computer นี้ก็เป็นได้
โดยที่ใน Part นี้นั้นจะเป็นส่วนของการคำนวณและหลักการของ Shor’s Algorithm ที่ใน Part ต่อไปจะเป็นส่วนของ Quantum Circuit และนำหลักการนี้มาประยุกต์เข้ากับ Quantum Fourier Transform ที่จะเป็นยังไงนั้นสามารถติดตามได้ที่ Part ต่อไปเลย!
สุดท้ายนี้หากชื่นชอบโพสนี้ก็อย่าลืมแชร์และแบ่งปันความรู้ทางด้านควอนตัมต่อเนื่องให้กับคนอื่น ๆ ด้วยนะครับ ขอบคุณทุกคนที่อ่านถึงจุดนี้ครับ :)
Happy Coding & Learning Quantum 😁
Ref
อัลกอริทึมของชอร์ | Panya’s Blog: Programmer Thoughts (wordpress.com)
ขั้นตอนวิธีของชอร์ — วิกิพีเดีย (wikipedia.org)
How Quantum Computers Break Encryption | Shor’s Algorithm Explained — YouTube
