Whiz Tools

룬 알고리즘 계산기

룬 알고리즘 계산기

소개

룬 알고리즘은 "모듈러스 10" 또는 "모드 10" 알고리즘으로도 알려져 있으며, 신용 카드 번호, 캐나다 사회 보장 번호, IMEI 번호 및 미국의 국가 제공자 식별 번호와 같은 다양한 식별 번호를 검증하는 데 사용되는 간단한 체크섬 공식입니다. 이 계산기를 사용하면 룬 알고리즘을 사용하여 번호를 검증하고 룬 검사를 통과하는 유효한 번호를 생성할 수 있습니다.

룬 알고리즘 작동 방식

룬 알고리즘은 다음과 같이 작동합니다:

  1. 오른쪽에서 가장 오른쪽 숫자(체크 숫자를 제외하고)부터 시작하여 모든 두 번째 숫자의 값을 두 배로 늘립니다.
  2. 이 두 배 연산의 결과가 9보다 크면 결과에서 9를 뺍니다.
  3. 결과 시퀀스의 모든 숫자를 합산합니다.
  4. 총합의 모듈로 10이 0과 같으면(총합이 0으로 끝나면) 해당 번호는 룬 공식에 따라 유효합니다. 그렇지 않으면 유효하지 않습니다.

다음은 룬 알고리즘의 시각적 표현입니다:

1. 모든 두 번째 숫자를 두 배로 늘리기 2. 숫자 합산 (9는 두 배로 늘린 숫자 > 9) 3. 총합 계산하기 4. 총합 % 10 == 0인지 확인하기

공식

룬 알고리즘은 수학적으로 다음과 같이 표현할 수 있습니다:

did_i를 오른쪽에서부터 세는 ii-번째 숫자(체크 숫자를 제외하고)라고 하자. 그러면 체크 숫자 d0d_0는 다음과 같이 선택됩니다:

(2d2n mod 9+d2n−1+2d2n−2 mod 9+d2n−3+⋯+2d2 mod 9+d1+d0) mod 10=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

여기서  mod \bmod는 모듈로 연산입니다.

사용 사례

룬 알고리즘은 다양한 분야에서 여러 가지 응용 프로그램이 있습니다:

  1. 신용 카드 검증: 대부분의 신용 카드 번호는 룬 알고리즘을 사용하여 검증됩니다.
  2. 캐나다 사회 보장 번호: 룬 알고리즘은 이러한 식별 번호의 유효성을 검증하는 데 사용됩니다.
  3. IMEI 번호: 모바일 전화 IMEI 번호는 룬 알고리즘으로 검증되는 체크 숫자를 포함합니다.
  4. 국가 제공자 식별(NPI) 번호: 미국 의료 시스템에서 사용되는 이 번호는 룬 알고리즘을 사용하여 검증됩니다.
  5. ISBN: 일부 ISBN-10 번호는 검증을 위해 룬 알고리즘의 변형을 사용합니다.

대안

룬 알고리즘은 널리 사용되지만, 다른 목적을 위한 체크섬 알고리즘도 있습니다:

  1. 담 알고리즘: 모든 단일 숫자 오류와 모든 인접 전환 오류를 감지하는 다른 체크 숫자 알고리즘입니다.
  2. 베로프 알고리즘: 모든 단일 숫자 오류와 대부분의 전환 오류를 잡는 더 복잡한 체크섬 알고리즘입니다.
  3. ISBN-13 체크 숫자: ISBN-10과는 다른 알고리즘을 사용하며, 이는 룬 알고리즘을 기반으로 합니다.

역사

룬 알고리즘은 1954년 IBM 컴퓨터 과학자 한스 피터 룬에 의해 만들어졌습니다. 룬은 정보 과학 분야의 선구자로, KWIC(문맥 내 키워드) 색인 시스템을 포함하여 여러 혁신으로 인정받고 있습니다.

이 알고리즘은 원래 우발적인 오류를 방지하기 위해 설계되었으며, 악의적인 공격을 염두에 두고 있지 않았습니다. 룬 알고리즘은 많은 일반적인 오류를 감지할 수 있지만, 데이터 보안 목적으로 의존해서는 안 되는 안전한 암호화 형태가 아니라는 점에 유의해야 합니다.

오래된 알고리즘임에도 불구하고 룬 알고리즘은 간단함과 일반적인 전사 오류를 잡는 효과성 덕분에 여전히 널리 사용되고 있습니다.

구현 예제

다양한 프로그래밍 언어에서 룬 알고리즘을 구현하는 코드 예제는 다음과 같습니다:

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])))

## 사용 예시:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # 유효한 16자리 숫자 생성

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);
}

// 사용 예시:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // 유효한 16자리 숫자 생성

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));  // 유효한 16자리 숫자 생성
    }
}

엣지 케이스 및 특별 고려 사항

룬 알고리즘을 구현할 때 다음의 엣지 케이스 및 특별 고려 사항을 고려하십시오:

  1. 입력 검증: 입력이 유효한 숫자 문자열인지 확인하십시오. 비숫자 문자는 적절하게 처리되어야 합니다(제거되거나 유효하지 않은 입력으로 처리됨).

  2. 선행 제로: 알고리즘은 선행 제로가 있는 숫자에 대해 올바르게 작동해야 합니다.

  3. 큰 숫자: 일부 프로그래밍 언어의 표준 정수 유형의 용량을 초과할 수 있는 매우 긴 숫자를 처리할 수 있도록 준비하십시오.

  4. 빈 입력: 빈 문자열 또는 null 입력을 처리하는 방법을 정의하십시오.

  5. 비표준 문자 집합: 일부 응용 프로그램에서는 표준 0-9 범위를 벗어난 문자로 표현된 숫자를 만날 수 있습니다. 이러한 경우를 처리하는 방법을 정의하십시오.

  6. 성능 고려 사항: 빠르게 많은 수의 입력을 검증해야 하는 응용 프로그램의 경우 알고리즘 구현을 최적화하는 것을 고려하십시오.

숫자 예제

  1. 유효한 신용 카드 번호:

    • 번호: 4532015112830366
    • 룬 체크: 유효

  2. 유효하지 않은 신용 카드 번호:

    • 번호: 4532015112830367
    • 룬 체크: 유효하지 않음

  3. 유효한 캐나다 사회 보장 번호:

    • 번호: 046 454 286
    • 룬 체크: 유효

  4. 유효하지 않은 IMEI 번호:

    • 번호: 490154203237518
    • 룬 체크: 유효하지 않음

테스트 케이스

룬 알고리즘의 구현을 검증하기 위해 다음 테스트 케이스를 사용할 수 있습니다:

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # 생성된 숫자 테스트
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("모든 테스트 통과!")

test_luhn_algorithm()

참고 문헌

  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.
Feedback