Suma lub cyfra kontrolna - cd.

Współczynniki wagowe do obliczeń cyfr kontrolnych

Dla numeru takiego jak PESEL, NIP, REGON itp. algorytm obliczenia cyfry kontrolnej przebiega następująco:

  • każdej z pozycji cyfr numeru nadany został stały współczynnik zwany wagą pozycji,
  • każdą cyfrę numeru mnoży się przez odpowiednią wagę i sumuje się wynik mnożenia,
  • reszta z dzielenia sumy przez N jest cyfrą kontrolną.

Dla N=10 wynik dzielenia modulo N jest po prostu ostatnią cyfrą sumy.

 Oto przykład dla numeru PESEL 49040501580

    9 7 3 1 9 7 3 1 9 7    --> wagi
    X X X X X X X X X X K  --> cyfry nr PESEL 
                              (K- cyfra kontrolna)
czyli:       
            9 7 3 1 9 7 3 1 9 7
         *  4 9 0 4 0 5 0 1 5 8
        -----------------------
suma=(9*4+7*9+3*0+1*4+9*0+7*5+3*0+1*1+9*5+7*8) =
    =( 36+ 63+  0+  4+  0+ 35+  0+  1+ 45+ 56) = 240
 
       240 mod 10 = 0      --> cyfra kontrolna =   0

W przypadku wprowadzenia błędnej pojedynczej cyfry numeru PESEL, komputer po obliczeniu cyfry kontrolnej może ten błąd wykryć, gdyż np: jeśli pomylimy się i zamiast 49040501580 podamy 46040501580 to otrzymamy:

            9 7 3 1 9 7 3 1 9 7
         *  4 6 0 4 0 5 0 1 5 8
        -----------------------
suma=(9*4+7*6+3*0+1*4+9*0+7*5+3*0+1*1+9*5+7*8) =
    =( 36+ 42+  0+  4+  0+ 35+  0+  1+ 45+ 56) = 219
 
       219 mod 10 = 9      --> cyfra kontrolna =   9

Obliczona cyfra kontrolna to 9, podczas gdy prawidłowa cyfra to 0.

Dobór współczynników wagowych

Dobór współczynników wagowych powinien zapewnić:

  • wykrywanie błędnej cyfry w dowolnym miejscu numeru;
  • odporność na tzw. czeski błąd czyli zamianę miejscami dwóch kolejnych cyfr numeru.

W obu wypadkach obliczona cyfra kontrolna powinna się różnić od cyfry kontrolnej obliczonej dla prawidłowego numeru.

cyfra kontrolna po dzieleniu modulo 10

Poniżej podamy testy dla wag od 1 do 9 przy założeniu, że cyfra kontrolna powstaje przez dzielenie modulo 10 sumy iloczynów wag i kolejnych cyfr numeru.


waga    =  1   1   1   1   1   1   1   1   1   1
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   1   2   3   4   5   6   7   8   9
x mod 10=  0   1   2   3   4   5   6   7   8   9

Ponieważ w iloczynach nie powtarzają się liczby, to 
współczynnik wagowy 1 nadaje się do stosowania 
w zwykłej sumie kontrolnej, oraz 1 nadaje się do 
algorytmu Luhna.

waga    =  2   2   2   2   2   2   2   2   2   2
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   2   4   6   8  10  12  14  16  18
x mod 10=  0   2   4   6   8   0   2   4   6   8
iloczyn =  0   2   4   6   8  1+0 1+2 1+4 1+6 1+8 (wg. Luhna)
suma    =  0   2   4   6   8   1   3   5   7   9

Ponieważ w iloczynach powtarzają się liczby, to 
współczynnik wagowy 2 nie nadaje się do stosowania 
w zwykłej sumie kontrolnej, natomiast 2 nadaje się 
do algorytmu Luhna.


waga    =  3   3   3   3   3   3   3   3   3   3
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   3   6   9  12  15  18  21  24  27
x mod 10=  0   3   6   9   2   5   8   1   4   7
iloczyn =  0   3   6   9  1+2 1+5 1+8 2+1 2+4 2+7 (wg. Luhna)
suma    =  0   3   6   9   3   6   9   3   6   9

Ponieważ w iloczynach nie powtarzają się liczby, 
to współczynnik wagowy 3 nadaje się do stosowania 
w zwykłej sumie kontrolnej, ale 3 nie nadaje się do 
algorytmu Luhna.


waga    =  4   4   4   4   4   4   4   4   4   4
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   4   8  12  16  20  24  28  32  36
x mod 10=  0   4   8   2   6   0   4   8   2   6
iloczyn =  0   4   8  1+2 1+6 2+0 2+4 2+8 3+2 3+6 (wg. Luhna)
suma    =  0   4   8   3   7   2   6  10   5   9

Ponieważ w iloczynach powtarzają się liczby, to 
współczynnik wagowy 4 nie nadaje się do stosowania 
w zwykłej sumie kontrolnej, a także 4 nie nadaje się 
do algorytmu Luhna.


waga    =  5   5   5   5   5   5   5   5   5   5
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   5  10  15  20  25  30  35  40  45
x mod 10=  0   5   0   5   0   5   0   5   0   5 
iloczyn =  0   5  1+0 1+5 2+0 2+5 3+0 3+5 4+0 4+5 (wg. Luhna)
suma    =  0   5   1   6   2   7   3   8   4   9
Ponieważ w iloczynach powtarzają się liczby, to 
współczynnik wagowy 5 nie nadaje się do stosowania 
w zwykłej sumie kontrolnej, natomiast 5 nadaje się 
do algorytmu Luhna.


waga    =  6   6   6   6   6   6   6   6   6   6
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   6  12  18  24  30  36  42  48  54
x mod 10=  0   6   2   8   4   0   6   2   8   4
iloczyn =  0   1  1+2 1+8 2+4 3+0 3+6 4+2 4+8 5+4 (wg. Luhna)
suma    =  0   1   3   9   6   3   9   6  12   9

Ponieważ w iloczynach powtarzają się liczby, to 
współczynnik wagowy 6 nie nadaje się do stosowania 
w zwykłej sumie kontrolnej, a także 6 nie nadaje się 
do algorytmu Luhna.


waga    =  7   7   7   7   7   7   7   7   7   7
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   7  14  21  28  35  42  49  56  63
x mod 10=  0   7   4   1   8   5   2   9   6   3
iloczyn =  0   7  1+4 2+1 2+8 3+5 4+2 4+9 5+6 6+3 (wg. Luhna)
suma    =  0   7   5   3  10   8   6  13  11   9

Ponieważ w iloczynach nie powtarzają się liczby, 
to współczynnik wagowy 7 nadaje się do stosowania 
w zwykłej sumie kontrolnej. 
Natomiast 7*3=21 (2+1=3) i 7*7=49 (4+9=13) po dzieleniu mod 10 daje ten sam wynik 3 więc 7 nie nadaje się do algorytmu Luhna. waga = 8 8 8 8 8 8 8 8 8 8 cyfra = 0 1 2 3 4 5 6 7 8 9 iloczyn = 0 8 16 24 32 40 48 56 64 72 x mod 10= 0 8 6 4 2 0 8 6 4 2 iloczyn = 0 8 1+6 2+4 3+2 4+0 4+8 5+6 6+4 7+2 (wg. Luhna) suma = 0 8 7 6 5 4 12 11 10 9 Ponieważ w iloczynach powtarzają się liczby, to współczynnik wagowy 8 nie nadaje się do stosowania w zwykłej sumie kontrolnej, także 8 nie nadaje się do algorytmu Luhna gdyż zamiana 0 na 8 lub odwrotnie dawałaby tę samą cyfrę kontrolną. waga = 9 9 9 9 9 9 9 9 9 9 cyfra = 0 1 2 3 4 5 6 7 8 9 iloczyn = 0 9 18 27 36 45 54 63 72 81 x mod 10= 0 9 8 7 6 5 4 3 2 1 iloczyn = 0 9 1+8 2+7 3+6 4+5 5+4 6+3 7+2 8+1 (wg. Luhna) suma = 0 9 9 9 9 9 9 9 9 9 Ponieważ w iloczynach nie powtarzają się liczby, to współczynnik wagowy 9 nadaje się do stosowania w zwykłej sumie kontrolnej, ale 9 nie nadaje się do algorytmu Luhna.

Podsumowanie: do zwykłych sum kontrolnych z dzieleniem modulo 10 nadają się wagi 1 3 7 9, a do algorytmu Luhna nadają się wagi 1 2 5. Użycie takich współczynników gwarantuje 100% skuteczność wykrycia błędnie wprowadzonej pojedynczej cyfry.


Odporność na czeskie błędy - mod 10

W przypadku zamiany dwu kolejnych cyfr numeru PESEL, komputer po obliczeniu cyfry kontrolnej może na ogół ten błąd wykryć. Ale jeśli pomylimy się i zamiast 49040501580 podamy 94040501580 to otrzymamy:

            9 7 3 1 9 7 3 1 9 7
         *  9 4 0 4 0 5 0 1 5 8
        -----------------------
suma=(9*9+7*4+3*0+1*4+9*0+7*5+3*0+1*1+9*5+7*8) =
    =( 81+ 28+  0+  4+  0+ 35+  0+  1+ 45+ 56) = 250
 
       250 mod 10 = 0      --> cyfra kontrolna =   0

Obliczona cyfra kontrolna to 0, podczas gdy prawidłowa cyfra dla numeru 49040501580 to także 0. Jak widać użyte współczynniki dla numeru PESEL nie zapewniają wykrycia każdego czeskiego błędu! Dokładnie rzecz biorąc, to niewykryte będą czeskie błędy dla cyfr różniących się o 5. W powyższym przykładzie są to cyfry 4 i 9.

Sprawdzenie wszystkich kombinacji cyfr i użytych dla PESELa wag (1379137913) pokazało, że 90% czeskich pomyłek jest wykrywana przez algorytm sprawdzania cyfry kontrolnej.

Użycie wag '1717171717' powoduje 100% pewność wykrywania błędów zamiany pojedynczej cyfry, oraz 90% pewność wykrywania czeskich błędów.

Algorytm Luhna jest lepszy jeśli chodzi o wykrywanie błędów. Jeśli użyjemy par wag ze zbioru 1 2 5 to mamy 100% pewność wykrycia błędnie wprowadzonej pojedynczej cyfry i w najlepszym wypadku 97.77% pewność wykrycia czeskiego błędu pod warunkiem użycia par (1 2) lub (1 5).
Przykładem niewykrywania czeskiego błędu przez algorytm Luhna jest zamiana kolejności cyfr 0 i 9, a więc np. zamiana 90 na 09 nie zostanie wykryta.


cyfra kontrolna po dzieleniu modulo 11

Poniżej podamy testy dla wag od 1 do 9 przy założeniu, że cyfra kontrolna powstaje przez dzielenie modulo 11 sumy iloczynów wag i kolejnych cyfr numeru.


waga    =  1   1   1   1   1   1   1   1   1   1
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   1   2   3   4   5   6   7   8   9
x mod 11=  0   1   2   3   4   5   6   7   8   9

Ponieważ w iloczynach (x mod 11) nie powtarzają się liczby, 
to współczynnik wagowy 1 nadaje się do stosowania 
w sumie kontrolnej.

waga    =  2   2   2   2   2   2   2   2   2   2
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   2   4   6   8  10  12  14  16  18
x mod 11=  0   2   4   6   8  10   1   3   5   7

Ponieważ w iloczynach (x mod 11) nie powtarzają się liczby, 
to współczynnik wagowy 2 nadaje się do stosowania 
w zwykłej sumie kontrolnej.


waga    =  3   3   3   3   3   3   3   3   3   3
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   3   6   9  12  15  18  21  24  27
x mod 11=  0   3   6   9   1   4   7  10   2   5

Ponieważ w iloczynach (x mod 11) nie powtarzają się liczby, 
to współczynnik wagowy 3 nadaje się do stosowania 
w zwykłej sumie kontrolnej.


waga    =  4   4   4   4   4   4   4   4   4   4
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   4   8  12  16  20  24  28  32  36
x mod 11=  0   4   8   1   5   9   2   6  10   3

Ponieważ w iloczynach (x mod 11) nie powtarzają się liczby, 
to współczynnik wagowy 4 nadaje się do stosowania 
w zwykłej sumie kontrolnej.


waga    =  5   5   5   5   5   5   5   5   5   5
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   5  10  15  20  25  30  35  40  45
x mod 11=  0   5  10   4   9   3   8   2   7   1 

Ponieważ w iloczynach (x mod 11) nie powtarzają się liczby, 
to współczynnik wagowy 5 nadaje się do stosowania 
w zwykłej sumie kontrolnej.


waga    =  6   6   6   6   6   6   6   6   6   6
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   6  12  18  24  30  36  42  48  54
x mod 11=  0   6   1   7   2   8   3   9   4  10

Ponieważ w iloczynach (x mod 11) nie powtarzają się liczby, 
to współczynnik wagowy 6 nadaje się do stosowania 
w zwykłej sumie kontrolnej.


waga    =  7   7   7   7   7   7   7   7   7   7
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   7  14  21  28  35  42  49  56  63
x mod 11=  0   7   3  10   6   2   9   5   1   8

Ponieważ w iloczynach (x mod 11) nie powtarzają się liczby, 
to współczynnik wagowy 7 nadaje się do stosowania 
w zwykłej sumie kontrolnej.


waga    =  8   8   8   8   8   8   8   8   8   8
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   8  16  24  32  40  48  56  64  72
x mod 11=  0   8   5   2  10   7   4   1   9   6

Ponieważ w iloczynach (x mod 11) nie powtarzają się liczby, 
to współczynnik wagowy 8 nadaje się do stosowania 
w zwykłej sumie kontrolnej.


waga    =  9   9   9   9   9   9   9   9   9   9
cyfra   =  0   1   2   3   4   5   6   7   8   9
iloczyn =  0   9  18  27  36  45  54  63  72  81
x mod 11=  0   9   7   5   3   1  10   8   6   4

Ponieważ w iloczynach (x mod 11) nie powtarzają się liczby, 
to współczynnik wagowy 9 nadaje się do stosowania 
w zwykłej sumie kontrolnej.

Podsumowanie: do sum kontrolnych jako współczynniki wagowe nadają się cyfry 1 2 3 4 5 6 7 8 9. Użycie takich współczynników gwarantuje 100% skuteczność wykrycia błędnie wprowadzonej pojedynczej cyfry i wykrycie każdego czeskiego błędu.


Odporność na czeskie błędy - mod 11

W przypadku zamiany dwu kolejnych cyfr numeru NIP, komputer po obliczeniu cyfry kontrolnej może ten błąd wykryć. Jeśli pomylimy się i zamiast 768-000-24-66 podamy 678-000-24-66 to otrzymamy:

            6 5 7 2 3 4 5 6 7   -> wagi
         *  6 7 8 0 0 0 2 4 6   -> nr NIP (bez cyfry kontr.)
        ---------------------
suma= (6*7+5*6+7*8+2*0+3*0+4*0+5*2+6*4+7*6)=
    = ( 36+ 35+ 56+  0+  0+  0+ 10+ 24+ 42)=  203
 
           203 mod 11 = 5 ----> cyfra kontrolna różna od 6

ciąg dalszy


          Licznik = (od 25 wrz 2006)
          ostatnie poprawki           zylla  @  wipos.p.lodz.pl

Valid HTML 4.01!