อัลกอริทึมลูน ระบบตรวจสอบความถูกต้องของหมายเลขระบุตัวตน

อัลกอริทึมลูน (Luhn algorithm) หรือที่รู้จักในชื่อ สูตรลูน (Luhn formula) หรือ Modulus 10 (mod 10) เป็นสูตรคำนวณตัวเลขตรวจสอบ (Check Digit) แบบง่ายที่ใช้เพื่อตรวจสอบความถูกต้องของหมายเลขระบุตัวตนประเภทต่างๆ พัฒนาโดย Hans Peter Luhn นักวิทยาศาสตร์จากบริษัท IBM โดยมีวัตถุประสงค์หลักเพื่อให้คอมพิวเตอร์สามารถตรวจสอบข้อผิดพลาดที่เกิดจากการป้อนข้อมูลโดยมนุษย์ได้อย่างรวดเร็ว

อัลกอริทึมนี้เป็นสมบัติสาธารณะ (Public Domain) และมีการใช้งานอย่างแพร่หลายในปัจจุบัน โดยมีการกำหนดมาตรฐานใน ISO/IEC 7812-1 อย่างไรก็ตาม อัลกอริทึมลูนไม่ได้ถูกออกแบบมาเพื่อเป็นฟังก์ชันแฮชที่มีความปลอดภัยทางวิทยาการรหัสลับ (Cryptographically secure hash function) แต่ถูกสร้างขึ้นเพื่อป้องกันข้อผิดพลาดที่เกิดขึ้นโดยไม่ตั้งใจ เช่น การพิมพ์ผิด ไม่ใช่เพื่อป้องกันการโจมตีโดยผู้ไม่หวังดี

กลไกการทำงานของอัลกอริทึม

การคำนวณตัวเลขตรวจสอบ (Check Digit) มีขั้นตอนดังนี้:

1. แยกตัวเลขตรวจสอบ: หากหมายเลขนั้นมีตัวเลขตรวจสอบอยู่แล้ว ให้ตัดออกเพื่อให้เหลือเพียงส่วนข้อมูลหลัก (Payload)
2. การคูณสอง: เริ่มจากขวาสุดของส่วนข้อมูลหลัก แล้วทำการคูณสองให้กับตัวเลขในตำแหน่งคี่ (เมื่อนับจากขวาไปซ้าย) หรือทุกๆ ตัวเลขตัวที่สองเมื่อนับจากซ้ายในกรณีที่ทราบความยาวที่แน่นอน
3. การจัดการผลคูณ: หากผลคูณของตัวเลขใดมีค่าเกิน 9 ให้ลบออกด้วย 9 (ซึ่งมีค่าเท่ากับการนำเลขหลักหน่วยและหลักสิบของผลคูณมาบวกกัน เช่น 12 จะกลายเป็น 1+2 = 3 หรือ 12-9 = 3)
4. การหาผลรวม: นำตัวเลขทั้งหมดที่ได้จากขั้นตอนก่อนหน้า (รวมถึงตัวเลขที่ไม่ถูกคูณสอง) มาบวกกันทั้งหมด
5. การคำนวณตัวเลขตรวจสอบ: ตัวเลขตรวจสอบคือค่าที่น้อยที่สุด (อาจเป็นศูนย์) ที่ต้องบวกเพิ่มเข้าไปในผลรวมเพื่อให้ผลรวมนั้นหารด้วย 10 ลงตัว โดยใช้สูตรทางคณิตศาสตร์ดังนี้: (10 - (s mod 10)) mod 10 โดยที่ s คือผลรวมจากขั้นตอนที่ 4

ตัวอย่างการคำนวณตัวเลขตรวจสอบ

สมมติว่ามีหมายเลขบัญชี 1789372997 (ส่วนข้อมูลหลักที่ยังไม่มีตัวเลขตรวจสอบ):

• นำตัวเลขมาประมวลผลจากขวาไปซ้าย และคูณสองในตำแหน่งที่กำหนด
• ผลรวมของตัวเลขที่ได้คือ 56
• คำนวณตัวเลขตรวจสอบ: (10 - (56 mod 10)) mod 10 = 4

ดังนั้น หมายเลขบัญชีที่สมบูรณ์คือ 17893729974

การตรวจสอบความถูกต้อง (Validation)

ในการตรวจสอบว่าหมายเลขที่ได้รับมาถูกต้องหรือไม่ ให้ทำตามขั้นตอนดังนี้:

1. แยกตัวเลขตัวสุดท้าย (ตัวเลขตรวจสอบ) ออกจากหมายเลขทั้งหมด
2. คำนวณหาตัวเลขตรวจสอบจากส่วนข้อมูลหลักที่เหลือด้วยวิธีข้างต้น
3. เปรียบเทียบผลลัพธ์ที่คำนวณได้กับตัวเลขตรวจสอบเดิม หากตรงกัน แสดงว่าหมายเลขนั้นมีความถูกต้องตามโครงสร้างของอัลกอริทึม

จุดแข็งและข้อจำกัด

อัลกอริทึมลูนสามารถตรวจจับข้อผิดพลาดได้หลายรูปแบบ ดังนี้:

• ข้อผิดพลาดตัวเลขเดี่ยว (Single-digit errors): ตรวจจับได้ทุกกรณี
• การสลับตำแหน่งตัวเลขที่อยู่ติดกัน (Transposition errors): ตรวจจับได้เกือบทั้งหมด ยกเว้นการสลับระหว่าง 09 และ 90 (หรือในทางกลับกัน) ซึ่งจะไม่ถูกตรวจพบ
• ข้อผิดพลาดแบบคู่ (Twin errors): ตรวจจับได้ส่วนใหญ่ แต่จะไม่ตรวจพบการสลับระหว่าง 22 ↔ 55, 33 ↔ 66 หรือ 44 ↔ 77

สำหรับผู้ที่ต้องการการตรวจจับข้อผิดพลาดที่ละเอียดกว่านี้ มีอัลกอริทึมอื่นที่ซับซ้อนกว่า เช่น อัลกอริทึมเวอร์ฮอฟฟ์ (Verhoeff algorithm) และ อัลกอริทึมแดมม์ (Damm algorithm) นอกจากนี้ยังมี Luhn mod N ซึ่งเป็นส่วนขยายที่รองรับการตรวจสอบสตริงที่ไม่ใช่ตัวเลข

ข้อดีอีกประการหนึ่งคือ การที่อัลกอริทึมทำงานจากขวาไปซ้าย ทำให้การเติมเลขศูนย์ข้างหน้า (Zero-padding) ไม่มีผลต่อผลลัพธ์การคำนวณ ระบบที่ต้องกำหนดความยาวตัวเลขให้คงที่จึงสามารถตรวจสอบความถูกต้องได้ทั้งก่อนและหลังการเติมเลขศูนย์

การนำไปใช้งานในปัจจุบัน

อัลกอริทึมลูนถูกนำไปใช้ในระบบระบุตัวตนระดับโลกมากมาย เช่น:

• การเงิน: หมายเลขบัตรเครดิต และหมายเลข CUSIP สำหรับตราสารทางการเงินในอเมริกาเหนือ
• โทรคมนาคม: หมายเลข IMEI ของโทรศัพท์มือถือ และหมายเลข ICCID ของ SIM Card
• ระบุตัวตนภาครัฐ: หมายเลขประกันสังคมของแคนาดา, หมายเลขประจำตัวประชาชนของอิสราเอลและแอฟริกาใต้, หมายเลขประจำตัวบุคคลของสวีเดน และหมายเลขประกันสังคมของกรีซ
• อื่นๆ: หมายเลขคำขอสิทธิบัตรยุโรป และหมายเลขติดตามพัสดุของไปรษณีย์สหรัฐฯ (ซึ่งใช้เวอร์ชันดัดแปลง)