Luhn Algoritmus Számológép

Bevezetés

A Luhn algoritmus, más néven "modulus 10" vagy "mod 10" algoritmus, egy egyszerű ellenőrző számítási formula, amelyet különféle azonosító számok, például hitelkártya számok, kanadai társadalombiztosítási számok, IMEI számok és az Egyesült Államokban használt Országos Szolgáltató Azonosító számok érvényesítésére használnak. Ez a számológép lehetővé teszi, hogy érvényesítse a számokat a Luhn algoritmus segítségével, és generáljon érvényes számokat, amelyek átmennek a Luhn ellenőrzésen.

Hogyan működik a Luhn algoritmus

A Luhn algoritmus a következőképpen működik:

1. A legjobboldali számjegytől (a ellenőrző számjegy kivételével) kezdve, haladjon balra, és duplázza meg minden második számjegy értékét.
2. Ha a duplázás eredménye nagyobb, mint 9, vonjon le 9-et az eredményből.
3. Összegezze az összes számjegyet az eredményül kapott sorozatban.
4. Ha az összeg modulo 10 egyenlő 0-val (ha az összeg nullával végződik), akkor a szám érvényes a Luhn formula szerint; különben nem érvényes.

Itt egy vizuális ábrázolás a Luhn algoritmusról:

Formula

A Luhn algoritmus matematikailag a következőképpen fejezhető ki:

Legyen $d_i$ az $i$-edik számjegy, a legjobboldali számjegytől (a ellenőrző számjegy kivételével) balra haladva. Ekkor az ellenőrző számjegy $d_0$ úgy van kiválasztva, hogy:

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

Ahol $\bmod$ a modulo művelet.

Használati esetek

A Luhn algoritmusnak különböző alkalmazásai vannak különböző területeken:

1. Hitelkártya Érvényesítés: A legtöbb hitelkártya számot a Luhn algoritmus segítségével érvényesítenek.
2. Kanadai Társadalombiztosítási Számok: A Luhn algoritmust használják ezen azonosító számok érvényességének ellenőrzésére.
3. IMEI Számok: A mobiltelefonok IMEI számai tartalmaznak egy ellenőrző számjegyet, amelyet a Luhn algoritmus érvényesít.
4. Országos Szolgáltató Azonosító (NPI) Számok: Az Egyesült Államok egészségügyi rendszerében használt számokat a Luhn algoritmus érvényesíti.
5. ISBN: Néhány ISBN-10 szám a Luhn algoritmus egy változatát használja az érvényesítéshez.

Alternatívák

Bár a Luhn algoritmus széles körben használt, más ellenőrző algoritmusok is léteznek különböző célokra:

1. Damm algoritmus: Egy másik ellenőrző számjegy algoritmus, amely észleli az összes egyjegyű hibát és az összes szomszédos transzpozíciós hibát.
2. Verhoeff algoritmus: Egy összetettebb ellenőrző algoritmus, amely észleli az összes egyjegyű hibát és a legtöbb transzpozíciós hibát.
3. ISBN-13 ellenőrző számjegy: Más algoritmust használ, mint az ISBN-10, amely a Luhn algoritmuson alapul.

Történelem

A Luhn algoritmust Hans Peter Luhn, az IBM számítástechnikai tudósa alkotta meg 1954-ben. Luhn az információs tudomány területének úttörője, és számos innováció fűződik a nevéhez, beleértve a KWIC (Kulcsszó a Kontextusban) indexelési rendszert.

Az algoritmust eredetileg a véletlen hibák elleni védelemre tervezték, nem pedig rosszindulatú támadások ellen. Fontos megjegyezni, hogy bár a Luhn algoritmus képes észlelni sok gyakori hibát, nem biztonságos titkosítási forma, és nem szabad adatbiztonsági célokra támaszkodni.

Korától függetlenül a Luhn algoritmus továbbra is széles körben használt a egyszerűsége és a közönséges másolási hibák észlelésének hatékonysága miatt.

Megvalósítási Példák

Itt van néhány kód példa a Luhn algoritmus megvalósítására különböző programozási nyelvekben:

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## Példa használat:
22print(luhn_validate(4532015112830366))  # True
23print(luhn_validate(4532015112830367))  # False
24print(generate_valid_number(16))  # Generál egy érvényes 16-jegyű számot
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// Példa használat:
29console.log(luhnValidate(4532015112830366));  // true
30console.log(luhnValidate(4532015112830367));  // false
31console.log(generateValidNumber(16));  // Generál egy érvényes 16-jegyű számot
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));  // Generál egy érvényes 16-jegyű számot
47    }
48}
49

Széljegyzetek és különleges megfontolások

A Luhn algoritmus megvalósításakor vegye figyelembe a következő széljegyzeteket és különleges megfontolásokat:

1. Bemeneti Érvényesítés: Biztosítsa, hogy a bemenet egy érvényes számjegy string legyen. A nem számjegy karaktereket megfelelően kell kezelni (vagy eltávolítani, vagy érvénytelen bemenetként kezelni).

2. Előtag Zérók: Az algoritmusnak helyesen kell működnie a zérókkal kezdődő számokkal.

3. Nagy Számok: Készüljön fel arra, hogy nagyon hosszú számokat kezeljen, amelyek meghaladhatják a standard egész szám típusok kapacitását egyes programozási nyelvekben.

4. Üres Bemenet: Határozza meg, hogyan kell kezelni a üres stringeket vagy null bemeneteket.

5. Nem Szabványos Karakterkészletek: Egyes alkalmazásokban előfordulhat, hogy a számokat a standard 0-9 tartományon kívüli karakterekkel ábrázolják. Határozza meg, hogyan kell ezeket kezelni.

6. Teljesítmény Megfontolások: Azok számára, akiknek gyorsan kell érvényesíteniük nagyszámú bemenetet, fontolja meg az algoritmus megvalósításának optimalizálását.

Szám példák

1. Érvényes Hitelkártya Szám:

   • Szám: 4532015112830366
   • Luhn Ellenőrzés: Érvényes

2. Érvénytelen Hitelkártya Szám:

   • Szám: 4532015112830367
   • Luhn Ellenőrzés: Érvénytelen

3. Érvényes Kanadai Társadalombiztosítási Szám:

   • Szám: 046 454 286
   • Luhn Ellenőrzés: Érvényes

4. Érvénytelen IMEI Szám:

   • Szám: 490154203237518
   • Luhn Ellenőrzés: Érvénytelen

Teszt Esetek

A Luhn algoritmus megvalósításának ellenőrzésére használhatja a következő teszt eseteket:

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    # Tesztelt generált számok
8    for _ in range(10):
9        assert luhn_validate(generate_valid_number(16)) == True
10    
11    print("Minden teszt sikerült!")
12
13test_luhn_algorithm()
14

Hivatkozások

1. Luhn, H. P. (1960). "Számítógép a számok ellenőrzésére". US Patent 2,950,048.
2. Gallian, Joseph. "Az azonosító számok matematikája." A Főiskolai Matematikai Folyóirat, vol. 22, no. 3, 1991, pp. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". Nemzetközi Szabványügyi Szervezet. Hozzáférés: 2024. augusztus 2.
4. Knuth, Donald. "A számítógép programozás művészete, 2. kötet: Félszámszerű algoritmusok". Addison-Wesley, 1997.