Máy tính Thuật toán Luhn

Máy Tính Thuật Toán Luhn

Giới Thiệu

Thuật toán Luhn, còn được gọi là thuật toán "modulus 10" hoặc "mod 10", là một công thức kiểm tra đơn giản được sử dụng để xác thực nhiều loại số nhận dạng, chẳng hạn như số thẻ tín dụng, Số An Sinh Xã Hội Canada, số IMEI và số Nhà Cung Cấp Quốc Gia tại Hoa Kỳ. Máy tính này cho phép bạn xác thực các số bằng cách sử dụng thuật toán Luhn và tạo ra các số hợp lệ vượt qua kiểm tra Luhn.

Cách Thuật Toán Luhn Hoạt Động

Thuật toán Luhn hoạt động như sau:

Bắt đầu từ chữ số bên phải (không bao gồm chữ số kiểm tra) và di chuyển sang bên trái, gấp đôi giá trị của mỗi chữ số thứ hai.
Nếu kết quả của phép gấp đôi này lớn hơn 9, hãy trừ 9 khỏi kết quả.
Tính tổng tất cả các chữ số trong chuỗi kết quả.
Nếu tổng modulo 10 bằng 0 (nếu tổng kết thúc bằng số không), thì số đó hợp lệ theo công thức Luhn; nếu không, thì không hợp lệ.

Dưới đây là một hình ảnh minh họa cho thuật toán Luhn:

Công Thức

Thuật toán Luhn có thể được biểu diễn toán học như sau:

Gọi $d_i$ là chữ số thứ $i$ , đếm từ chữ số bên phải (không bao gồm chữ số kiểm tra) và di chuyển sang bên trái. Sau đó, chữ số kiểm tra $d_0$ được chọn sao cho:

$(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$

Trong đó $\bmod$ là phép toán modulo.

Các Trường Hợp Sử Dụng

Thuật toán Luhn có nhiều ứng dụng trong các lĩnh vực khác nhau:

Xác Thực Số Thẻ Tín Dụng: Hầu hết các số thẻ tín dụng được xác thực bằng thuật toán Luhn.
Số An Sinh Xã Hội Canada: Thuật toán Luhn được sử dụng để xác minh tính hợp lệ của các số nhận dạng này.
Số IMEI: Các số IMEI của điện thoại di động bao gồm một chữ số kiểm tra được xác thực bởi thuật toán Luhn.
Số Nhà Cung Cấp Quốc Gia (NPI): Được sử dụng trong hệ thống chăm sóc sức khỏe của Hoa Kỳ, các số này được xác thực bằng thuật toán Luhn.
ISBN: Một số số ISBN-10 sử dụng một biến thể của thuật toán Luhn để xác thực.

Các Lựa Chọn Thay Thế

Mặc dù thuật toán Luhn được sử dụng rộng rãi, vẫn có các thuật toán kiểm tra khác cho các mục đích khác nhau:

Thuật toán Damm: Một thuật toán chữ số kiểm tra khác phát hiện tất cả các lỗi một chữ số và tất cả các lỗi hoán đổi liền kề.
Thuật toán Verhoeff: Một thuật toán kiểm tra phức tạp hơn phát hiện tất cả các lỗi một chữ số và hầu hết các lỗi hoán đổi.
Chữ số kiểm tra ISBN-13: Sử dụng một thuật toán khác so với ISBN-10, dựa trên thuật toán Luhn.

Lịch Sử

Thuật toán Luhn được tạo ra bởi Hans Peter Luhn, một nhà khoa học máy tính của IBM, vào năm 1954. Luhn là một người tiên phong trong lĩnh vực khoa học thông tin và được ghi nhận với nhiều phát minh, bao gồm hệ thống lập chỉ mục KWIC (Từ Khóa Trong Ngữ Cảnh).

Thuật toán này ban đầu được thiết kế để bảo vệ chống lại các lỗi vô tình, không phải các cuộc tấn công ác ý. Điều quan trọng cần lưu ý là trong khi thuật toán Luhn có thể phát hiện nhiều lỗi phổ biến, nó không phải là một hình thức mã hóa an toàn và không nên được dựa vào cho các mục đích bảo mật dữ liệu.

Mặc dù đã có tuổi đời lâu, thuật toán Luhn vẫn được sử dụng rộng rãi nhờ vào tính đơn giản và hiệu quả trong việc phát hiện các lỗi sao chép phổ biến.

Ví Dụ Thực Hiện

Dưới đây là một số ví dụ mã để thực hiện thuật toán Luhn trong các ngôn ngữ lập trình khác nhau:

import random

def luhn_validate(number):
    digits = [int(d) for d in str(number)]
    checksum = 0
    for i in range(len(digits) - 1, -1, -1):
        d = digits[i]
        if (len(digits) - i) % 2 == 0:
            d = d * 2
            if d > 9:
                d -= 9
        checksum += d
    return checksum % 10 == 0

def generate_valid_number(length):
    digits = [random.randint(0, 9) for _ in range(length - 1)]
    checksum = sum(digits[::2]) + sum(sum(divmod(d * 2, 10)) for d in digits[-2::-2])
    check_digit = (10 - (checksum % 10)) % 10
    return int(''.join(map(str, digits + [check_digit])))

## Ví dụ sử dụng:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # Tạo ra một số hợp lệ 16 chữ số

function luhnValidate(number) {
    const digits = number.toString().split('').map(Number);
    let checksum = 0;
    for (let i = digits.length - 1; i >= 0; i--) {
        let d = digits[i];
        if ((digits.length - i) % 2 === 0) {
            d *= 2;
            if (d > 9) d -= 9;
        }
        checksum += d;
    }
    return checksum % 10 === 0;
}

function generateValidNumber(length) {
    const digits = Array.from({length: length - 1}, () => Math.floor(Math.random() * 10));
    const checksum = digits.reduce((sum, digit, index) => {
        if ((length - 1 - index) % 2 === 0) {
            digit *= 2;
            if (digit > 9) digit -= 9;
        }
        return sum + digit;
    }, 0);
    const checkDigit = (10 - (checksum % 10)) % 10;
    return parseInt(digits.join('') + checkDigit);
}

// Ví dụ sử dụng:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // Tạo ra một số hợp lệ 16 chữ số

import java.util.Random;

public class LuhnValidator {
    public static boolean luhnValidate(long number) {
        String digits = String.valueOf(number);
        int checksum = 0;
        boolean isEven = true;
        for (int i = digits.length() - 1; i >= 0; i--) {
            int digit = Character.getNumericValue(digits.charAt(i));
            if (isEven) {
                digit *= 2;
                if (digit > 9) digit -= 9;
            }
            checksum += digit;
            isEven = !isEven;
        }
        return checksum % 10 == 0;
    }

    public static long generateValidNumber(int length) {
        Random random = new Random();
        long[] digits = new long[length - 1];
        for (int i = 0; i < length - 1; i++) {
            digits[i] = random.nextInt(10);
        }
        long checksum = 0;
        for (int i = digits.length - 1; i >= 0; i--) {
            long digit = digits[i];
            if ((length - 1 - i) % 2 == 0) {
                digit *= 2;
                if (digit > 9) digit -= 9;
            }
            checksum += digit;
        }
        long checkDigit = (10 - (checksum % 10)) % 10;
        long result = 0;
        for (long digit : digits) {
            result = result * 10 + digit;
        }
        return result * 10 + checkDigit;
    }

    public static void main(String[] args) {
        System.out.println(luhnValidate(4532015112830366L));  // true
        System.out.println(luhnValidate(4532015112830367L));  // false
        System.out.println(generateValidNumber(16));  // Tạo ra một số hợp lệ 16 chữ số
    }
}

Các Trường Hợp Biên và Các Xem Xét Đặc Biệt

Khi thực hiện thuật toán Luhn, hãy xem xét các trường hợp biên và các xem xét đặc biệt sau:

Kiểm Tra Đầu Vào: Đảm bảo rằng đầu vào là một chuỗi số hợp lệ. Các ký tự không phải số nên được xử lý một cách thích hợp (hoặc bị loại bỏ hoặc coi là đầu vào không hợp lệ).
Số 0 Đầu: Thuật toán nên hoạt động chính xác với các số có số 0 đầu.
Số Lớn: Hãy chuẩn bị để xử lý các số rất dài có thể vượt quá khả năng của các kiểu số nguyên tiêu chuẩn trong một số ngôn ngữ lập trình.
Đầu Vào Trống: Định nghĩa cách thực hiện của bạn nên xử lý các chuỗi trống hoặc đầu vào null.
Tập Ký Tự Không Chuẩn: Trong một số ứng dụng, bạn có thể gặp các số được biểu diễn bằng các ký tự ngoài phạm vi tiêu chuẩn 0-9. Định nghĩa cách xử lý những điều này.
Xem Xét Hiệu Suất: Đối với các ứng dụng cần xác thực một số lượng lớn đầu vào nhanh chóng, hãy xem xét tối ưu hóa việc thực hiện thuật toán.

Ví Dụ Số Học

Số Thẻ Tín Dụng Hợp Lệ:
- Số: 4532015112830366
- Kiểm Tra Luhn: Hợp lệ
Số Thẻ Tín Dụng Không Hợp Lệ:
- Số: 4532015112830367
- Kiểm Tra Luhn: Không hợp lệ
Số An Sinh Xã Hội Canada Hợp Lệ:
- Số: 046 454 286
- Kiểm Tra Luhn: Hợp lệ
Số IMEI Không Hợp Lệ:
- Số: 490154203237518
- Kiểm Tra Luhn: Không hợp lệ

Các Trường Hợp Kiểm Tra

Để xác minh việc thực hiện thuật toán Luhn, bạn có thể sử dụng các trường hợp kiểm tra sau:

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # Kiểm tra các số được tạo ra
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("Tất cả các bài kiểm tra đều đã vượt qua!")

test_luhn_algorithm()

Tài Liệu Tham Khảo

Luhn, H. P. (1960). "Máy Tính Để Xác Minh Các Số". Bằng sáng chế Hoa Kỳ 2,950,048.
Gallian, Joseph. "Toán Học Của Các Số Nhận Dạng." Tạp Chí Toán Học Cao Đẳng, vol. 22, no. 3, 1991, pp. 194–202. JSTOR, www.jstor.org/stable/2686878.
"ISO/IEC 7812-1:2017". Tổ Chức Tiêu Chuẩn Quốc Tế. Truy cập ngày 2 tháng 8 năm 2024.
Knuth, Donald. "Nghệ Thuật Lập Trình Máy Tính, Tập 2: Thuật Toán Số Học." Addison-Wesley, 1997.