Luhn Algorithm Calculator

Introduction

อัลกอริธึม Luhn ซึ่งรู้จักกันในชื่อ "โมดูลัส 10" หรือ "mod 10" เป็นสูตรตรวจสอบความถูกต้องที่ง่าย ใช้ในการตรวจสอบหมายเลขประจำตัวต่างๆ เช่น หมายเลขบัตรเครดิต หมายเลขประกันสังคมของแคนาดา หมายเลข IMEI และหมายเลขผู้ให้บริการแห่งชาติในสหรัฐอเมริกา เครื่องคำนวณนี้ช่วยให้คุณตรวจสอบความถูกต้องของหมายเลขโดยใช้อัลกอริธึม Luhn และสร้างหมายเลขที่ถูกต้องซึ่งผ่านการตรวจสอบ Luhn

How the Luhn Algorithm Works

อัลกอริธึม Luhn ทำงานดังนี้:

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

นี่คือการแสดงภาพของอัลกอริธึม Luhn:

Formula

อัลกอริธึม Luhn สามารถแสดงเป็นทางคณิตศาสตร์ได้ดังนี้:

ให้ $d_i$ เป็นหลักที่ $i$-th นับจากหลักขวาสุด (ไม่รวมหลักตรวจสอบ) และเคลื่อนที่ไปทางซ้าย จากนั้นหลักตรวจสอบ $d_0$ จะถูกเลือกเพื่อให้:

$(2d_{2n} \bmod 9 + d_{2n-1} + 2d_{2n-2} \bmod 9 + d_{2n-3} + \cdots + 2d_2 \bmod 9 + d_1 + d_0) \bmod 10 = 0$

โดยที่ $\bmod$ คือการดำเนินการโมดูลัส

Use Cases

อัลกอริธึม Luhn มีการใช้งานในหลากหลายสาขา:

1. การตรวจสอบบัตรเครดิต: หมายเลขบัตรเครดิตส่วนใหญ่จะถูกตรวจสอบโดยใช้อัลกอริธึม Luhn
2. หมายเลขประกันสังคมของแคนาดา: อัลกอริธึม Luhn ใช้ในการตรวจสอบความถูกต้องของหมายเลขประจำตัวเหล่านี้
3. หมายเลข IMEI: หมายเลข IMEI ของโทรศัพท์มือถือมีการรวมหลักตรวจสอบที่ตรวจสอบโดยอัลกอริธึม Luhn
4. หมายเลขผู้ให้บริการแห่งชาติ (NPI): ใช้ในระบบการดูแลสุขภาพของสหรัฐอเมริกา หมายเลขเหล่านี้จะถูกตรวจสอบโดยใช้อัลกอริธึม Luhn
5. ISBN: หมายเลข ISBN-10 บางหมายเลขใช้รูปแบบที่แตกต่างของอัลกอริธึม Luhn สำหรับการตรวจสอบความถูกต้อง

Alternatives

แม้อัลกอริธึม Luhn จะใช้กันอย่างแพร่หลาย แต่ก็มีอัลกอริธึมตรวจสอบอื่นๆ สำหรับวัตถุประสงค์ที่แตกต่างกัน:

1. อัลกอริธึม Damm: อัลกอริธึมตรวจสอบหลักอีกตัวที่ตรวจจับข้อผิดพลาดที่เกิดขึ้นเพียงหลักเดียวและข้อผิดพลาดการสลับที่อยู่ติดกันทั้งหมด
2. อัลกอริธึม Verhoeff: อัลกอริธึมตรวจสอบที่ซับซ้อนกว่าซึ่งจับข้อผิดพลาดที่เกิดขึ้นเพียงหลักเดียวและข้อผิดพลาดการสลับส่วนใหญ่
3. หลักตรวจสอบ ISBN-13: ใช้อัลกอริธึมที่แตกต่างจาก ISBN-10 ซึ่งอิงจากอัลกอริธึม Luhn

History

อัลกอริธึม Luhn ถูกสร้างขึ้นโดย Hans Peter Luhn นักวิทยาศาสตร์คอมพิวเตอร์ของ IBM ในปี 1954 Luhn เป็นผู้บุกเบิกในสาขาวิทยาศาสตร์ข้อมูลและได้รับเครดิตสำหรับนวัตกรรมหลายอย่าง รวมถึงระบบการจัดทำดัชนี KWIC (Key Word In Context)

อัลกอริธึมนี้ถูกออกแบบมาเพื่อป้องกันข้อผิดพลาดที่เกิดขึ้นโดยบังเอิญ ไม่ใช่การโจมตีที่มุ่งร้าย ควรสังเกตว่าแม้อัลกอริธึม Luhn จะสามารถตรวจจับข้อผิดพลาดทั่วไปได้มากมาย แต่ไม่ใช่รูปแบบการเข้ารหัสที่ปลอดภัยและไม่ควรถูกพึ่งพาเพื่อวัตถุประสงค์ด้านความปลอดภัยของข้อมูล

แม้ว่าจะมีอายุ แต่ก็ยังคงใช้กันอย่างแพร่หลายเนื่องจากความเรียบง่ายและประสิทธิภาพในการจับข้อผิดพลาดการถอดความทั่วไป

Implementation Examples

นี่คือตัวอย่างโค้ดในการใช้อัลกอริธึม Luhn ในภาษาการเขียนโปรแกรมต่างๆ:

1import random
2
3def luhn_validate(number):
4    digits = [int(d) for d in str(number)]
5    checksum = 0
6    for i in range(len(digits) - 1, -1, -1):
7        d = digits[i]
8        if (len(digits) - i) % 2 == 0:
9            d = d * 2
10            if d > 9:
11                d -= 9
12        checksum += d
13    return checksum % 10 == 0
14
15def generate_valid_number(length):
16    digits = [random.randint(0, 9) for _ in range(length - 1)]
17    checksum = sum(digits[::2]) + sum(sum(divmod(d * 2, 10)) for d in digits[-2::-2])
18    check_digit = (10 - (checksum % 10)) % 10
19    return int(''.join(map(str, digits + [check_digit])))
20
21## Example usage:
22print(luhn_validate(4532015112830366))  # True
23print(luhn_validate(4532015112830367))  # False
24print(generate_valid_number(16))  # Generates a valid 16-digit number
25

1function luhnValidate(number) {
2    const digits = number.toString().split('').map(Number);
3    let checksum = 0;
4    for (let i = digits.length - 1; i >= 0; i--) {
5        let d = digits[i];
6        if ((digits.length - i) % 2 === 0) {
7            d *= 2;
8            if (d > 9) d -= 9;
9        }
10        checksum += d;
11    }
12    return checksum % 10 === 0;
13}
14
15function generateValidNumber(length) {
16    const digits = Array.from({length: length - 1}, () => Math.floor(Math.random() * 10));
17    const checksum = digits.reduce((sum, digit, index) => {
18        if ((length - 1 - index) % 2 === 0) {
19            digit *= 2;
20            if (digit > 9) digit -= 9;
21        }
22        return sum + digit;
23    }, 0);
24    const checkDigit = (10 - (checksum % 10)) % 10;
25    return parseInt(digits.join('') + checkDigit);
26}
27
28// Example usage:
29console.log(luhnValidate(4532015112830366));  // true
30console.log(luhnValidate(4532015112830367));  // false
31console.log(generateValidNumber(16));  // Generates a valid 16-digit number
32

1import java.util.Random;
2
3public class LuhnValidator {
4    public static boolean luhnValidate(long number) {
5        String digits = String.valueOf(number);
6        int checksum = 0;
7        boolean isEven = true;
8        for (int i = digits.length() - 1; i >= 0; i--) {
9            int digit = Character.getNumericValue(digits.charAt(i));
10            if (isEven) {
11                digit *= 2;
12                if (digit > 9) digit -= 9;
13            }
14            checksum += digit;
15            isEven = !isEven;
16        }
17        return checksum % 10 == 0;
18    }
19
20    public static long generateValidNumber(int length) {
21        Random random = new Random();
22        long[] digits = new long[length - 1];
23        for (int i = 0; i < length - 1; i++) {
24            digits[i] = random.nextInt(10);
25        }
26        long checksum = 0;
27        for (int i = digits.length - 1; i >= 0; i--) {
28            long digit = digits[i];
29            if ((length - 1 - i) % 2 == 0) {
30                digit *= 2;
31                if (digit > 9) digit -= 9;
32            }
33            checksum += digit;
34        }
35        long checkDigit = (10 - (checksum % 10)) % 10;
36        long result = 0;
37        for (long digit : digits) {
38            result = result * 10 + digit;
39        }
40        return result * 10 + checkDigit;
41    }
42
43    public static void main(String[] args) {
44        System.out.println(luhnValidate(4532015112830366L));  // true
45        System.out.println(luhnValidate(4532015112830367L));  // false
46        System.out.println(generateValidNumber(16));  // Generates a valid 16-digit number
47    }
48}
49

Edge Cases and Special Considerations

เมื่อใช้อัลกอริธึม Luhn ควรพิจารณากรณีขอบและข้อพิจารณาพิเศษดังต่อไปนี้:

1. การตรวจสอบข้อมูลนำเข้า: ตรวจสอบให้แน่ใจว่าข้อมูลนำเข้าเป็นสตริงหมายเลขที่ถูกต้อง ตัวอักษรที่ไม่ใช่ตัวเลขควรได้รับการจัดการอย่างเหมาะสม (ลบออกหรือถือว่าเป็นข้อมูลนำเข้าสูงสุด)

2. ศูนย์นำหน้า: อัลกอริธึมควรทำงานได้อย่างถูกต้องกับหมายเลขที่มีศูนย์นำหน้า

3. หมายเลขขนาดใหญ่: เตรียมพร้อมที่จะจัดการกับหมายเลขที่ยาวมากซึ่งอาจเกินความสามารถของประเภทจำนวนเต็มมาตรฐานในบางภาษาการเขียนโปรแกรม

4. ข้อมูลนำเข้าสูญญากาศ: กำหนดวิธีที่การใช้งานของคุณควรจัดการกับสตริงว่างหรือข้อมูลนำเข้าสูญญากาศ

5. ชุดอักขระที่ไม่เป็นมาตรฐาน: ในบางแอปพลิเคชัน คุณอาจพบหมายเลขที่แสดงด้วยตัวอักษรนอกช่วงมาตรฐาน 0-9 กำหนดวิธีที่ควรจัดการกับสิ่งเหล่านี้

6. ข้อพิจารณาด้านประสิทธิภาพ: สำหรับแอปพลิเคชันที่ต้องการตรวจสอบข้อมูลนำเข้าจำนวนมากอย่างรวดเร็ว ให้พิจารณาเพิ่มประสิทธิภาพการใช้งานอัลกอริธึม

Numerical Examples

1. หมายเลขบัตรเครดิตที่ถูกต้อง:

   • หมายเลข: 4532015112830366
   • ตรวจสอบ Luhn: ถูกต้อง

2. หมายเลขบัตรเครดิตที่ไม่ถูกต้อง:

   • หมายเลข: 4532015112830367
   • ตรวจสอบ Luhn: ไม่ถูกต้อง

3. หมายเลขประกันสังคมของแคนาดาที่ถูกต้อง:

   • หมายเลข: 046 454 286
   • ตรวจสอบ Luhn: ถูกต้อง

4. หมายเลข IMEI ที่ไม่ถูกต้อง:

   • หมายเลข: 490154203237518
   • ตรวจสอบ Luhn: ไม่ถูกต้อง

Test Cases

เพื่อยืนยันการใช้งานอัลกอริธึม Luhn คุณสามารถใช้กรณีทดสอบต่อไปนี้:

1def test_luhn_algorithm():
2    assert luhn_validate(4532015112830366) == True
3    assert luhn_validate(4532015112830367) == False
4    assert luhn_validate(79927398713) == True
5    assert luhn_validate(79927398714) == False
6    
7    # ทดสอบหมายเลขที่สร้างขึ้น
8    for _ in range(10):
9        assert luhn_validate(generate_valid_number(16)) == True
10    
11    print("การทดสอบทั้งหมดผ่าน!")
12
13test_luhn_algorithm()
14

References

1. Luhn, H. P. (1960). "Computer for Verifying Numbers". US Patent 2,950,048.
2. Gallian, Joseph. "The Mathematics of Identification Numbers." The College Mathematics Journal, vol. 22, no. 3, 1991, pp. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". International Organization for Standardization. Retrieved August 2, 2024.
4. Knuth, Donald. "The Art of Computer Programming, Volume 2: Seminumerical Algorithms". Addison-Wesley, 1997.