Algorytm Luhna mod N

Algorytm Luhna mod N bazie jest rozszerzeniem algorytmu Luhna ( znanego również jako algorytm mod 10), które umożliwia mu pracę z sekwencjami wartości w dowolnej parzystej . Może to być przydatne, gdy cyfra kontrolna jest wymagana do sprawdzenia poprawności ciągu identyfikacyjnego złożonego z liter, kombinacji liter i cyfr lub dowolnego zestawu N znaków, gdzie N jest podzielne przez 2.

Nieformalne wyjaśnienie

Luhna mod N generuje cyfrę kontrolną (dokładniej znak kontrolny) w tym samym zakresie prawidłowych znaków, co ciąg wejściowy. Na przykład, jeśli algorytm zostanie zastosowany do ciągu małych liter ( a do z ), znak kontrolny będzie również małą literą. Poza tym rozróżnieniem bardzo przypomina oryginalny algorytm.

Główną ideą tego rozszerzenia jest to, że pełny zestaw prawidłowych znaków wejściowych jest odwzorowywany na listę punktów kodowych (tj. kolejnych liczb całkowitych zaczynających się od zera). Algorytm przetwarza łańcuch wejściowy, konwertując każdy znak na powiązany z nim punkt kodowy, a następnie wykonując obliczenia w mod N (gdzie N to liczba prawidłowych znaków wejściowych). Na koniec wynikowy punkt kodowy kontroli jest odwzorowywany z powrotem w celu uzyskania odpowiadającego mu znaku kontrolnego.

Ograniczenie

Algorytm Luhna mod N działa tylko wtedy, gdy N jest podzielne przez 2. Dzieje się tak, ponieważ istnieje operacja korygowania wartości pozycji po podwojeniu jej wartości, która nie działa, gdy N nie jest podzielne przez 2. Dla aplikacji korzystających z alfabetu angielskiego nie stanowi to problemu, ponieważ ciąg małych liter ma 26 punktów kodowych, a dodanie znaków dziesiętnych dodaje kolejne 10, zachowując N podzielne przez 2.

Wyjaśnienie

Drugi krok w algorytmie Luhna przepakowuje podwojoną wartość pozycji do podstawy oryginalnej cyfry , dodając do siebie poszczególne cyfry podwojonej wartości, gdy są zapisane w podstawie N . Ten krok skutkuje liczbami parzystymi, jeśli podwojona wartość jest mniejsza lub równa N , i liczbami nieparzystymi, jeśli podwojona wartość jest większa niż N . Na przykład w aplikacjach dziesiętnych , w których N wynosi 10, oryginalne wartości między 0 a 4 dają liczby parzyste, a oryginalne wartości między 5 a 9 dają liczby nieparzyste, skutecznie przepakowując podwojone wartości między 0 a 18 w jeden odrębny wynik między 0 a 9.

Gdy używane jest N , które nie jest podzielne przez 2, ten krok zwraca liczby parzyste dla podwojonych wartości większych niż N , których nie można odróżnić od podwojonych wartości mniejszych lub równych N .

Wynik

Algorytm nie wykryje ani wszystkich błędów jednocyfrowych, ani wszystkich transpozycji sąsiednich cyfr, jeśli zostanie użyte N , które nie jest podzielne przez 2. Ponieważ te możliwości wykrywania są głównymi zaletami algorytmu, algorytm jest prawie całkowicie osłabiony przez to ograniczenie. Nieparzysta odmiana algorytmu Luhna mod N umożliwia zastosowania, w których N nie jest podzielne przez 2, poprzez zastąpienie podwojonej wartości w każdej pozycji resztą po podzieleniu wartości pozycji przez N , co daje reszty nieparzyste zgodne z oryginalnym projektem algorytmu.

Odwzorowywanie znaków na punkty kodowe

Początkowo należy utworzyć mapowanie między prawidłowymi znakami wejściowymi a punktami kodowymi. Weźmy na przykład pod uwagę, że prawidłowe znaki to małe litery od a do f . Dlatego odpowiednim odwzorowaniem byłoby:

Postać	A	B	C	D	mi	F
Punkt kodowy	0	1	2	3	4	5

Pamiętaj, że kolejność znaków jest całkowicie nieistotna. To inne mapowanie również byłoby akceptowalne (choć być może bardziej kłopotliwe w implementacji):

Postać	C	mi	A	F	B	D
Punkt kodowy	0	1	2	3	4	5

Możliwe jest również mieszanie liter i cyfr (a być może nawet innych znaków). Na przykład to odwzorowanie byłoby odpowiednie dla małych cyfr szesnastkowych:

Postać	0	1	2	3	4	5	6	7	8	9	A	B	C	D	mi	F
Punkt kodowy	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

Algorytm w C#

Zakładając, że zdefiniowane są następujące funkcje:

   

   

   int  CodePointFromCharacter  (  char  znak  )  {...}  char  CharacterFromCodePoint  (  int  codePoint  )  {...}  int  NumberOfValidInputCharacters  ()  {...}

Funkcja generująca znak kontrolny to:

  

       
       0
       

    
    
             0 char  GenerateCheckCharacter  (  string  input  )  {  int  factor  =  2  ;  int  suma  =  ;  int  n  =  liczba prawidłowych znaków wejściowych  ();  // Rozpoczęcie od prawej strony i praca w lewo jest łatwiejsze, ponieważ  // początkowy "współczynnik" zawsze będzie wynosił "2".  for  (  int  i  =  wejście  .  Długość  -  1  ;  i  >=  ;  
    
           
             

        
                

        
          i  --)  {  int  codePoint  =  CodePointFromCharacter  (  input  [  i  ]);  int  addend  =  czynnik  *  codePoint  ;  // Zamień „czynnik”, że każdy „punkt kodowy” jest mnożony przez  factor  =  (  factor  ==  2  )  ?  1  :  2  ;  // Zsumuj cyfry „addend” wyrażone w podstawie „n”  addend  =        
          
    

    
    
         
           

     IntegerValue  (  addend  /  n  )  +  (  addend  %  n  );  suma  +=  dodaj  ;  }  // Oblicz liczbę, którą należy dodać do "sumy"  // aby była podzielna przez "n".  int  reszta  =  suma  %  n  ;  int  checkCodePoint  =  (  n  -  reszta  )  %  n  ;  powrót  
 ZnakOdPunktuKodowego  (  sprawdzaniePunktuKodowego  );  }

A funkcja sprawdzania poprawności łańcucha (ze znakiem kontrolnym jako ostatnim znakiem) to:

  

       
       0
       

    
    
    
           bool  ValidateCheckCharacter  (  ciąg  wejściowy  )  {  współczynnik  int  =  1  ;  int  suma  =  ;  int  n  =  liczba prawidłowych znaków wejściowych  ();  // Rozpoczynając od prawej strony, pracuj w lewo  // Teraz początkowym „współczynnikiem” będzie zawsze „1”  // ponieważ ostatnim znakiem jest znak kontrolny.  for  (  int  i  =  wejście  .  Długość  -  1  ;    0 
    
           
             

        
                 ja  >=  ;  i  --)  {  int  codePoint  =  CodePointFromCharacter  (  input  [  i  ]);  int  addend  =  czynnik  *  codePoint  ;  // Zamień „czynnik”, że każdy „punkt kodowy” jest mnożony przez  factor  =  (  factor  ==  2  )  ?  1  :  2  ; 

        
                
          
    

         

       0
 // Zsumuj cyfry „addend” wyrażone w podstawie „n”  addend  =  IntegerValue  (  addend  /  n  )  +  (  addend  %  n  );  suma  +=  dodaj  ;  }  int  reszta  =  suma  %  n  ;  powrót  (  reszta  ==  );  }

Algorytm w Javie

Zakładając, że zdefiniowane są następujące funkcje:

   

   

   int  codePointFromCharacter  (  char  znak  )  {...}  char  characterFromCodePoint  (  int  codePoint  )  {...}  int  numberOfValidInputCharacters  ()  {...}

Funkcja generująca znak kontrolny to:

   
       
       0
       

    
    
             char  generujCheckCharacter  (  ciąg znaków  wejściowych  )  {  współczynnik  int  =  2  ;  int  suma  =  ;  int  n  =  liczba prawidłowych znaków wejściowych  ();  // Rozpoczęcie od prawej strony i praca w lewo jest łatwiejsze, ponieważ  // początkowy "współczynnik" zawsze będzie wynosił "2".  for  (  int  i  =  input  .  length  ()  -  1  ;  i  >=  0  
           
             

        
                 ;  i  --  )  {  int  codePoint  =  codePointFromCharacter  (  input  .  charAt  (  i  ));  int  addend  =  czynnik  *  codePoint  ;  // Zamień „czynnik”, że każdy „punkt kodowy” jest mnożony przez  factor  =  (  factor  ==  2  )  ?  1  :  2  ; 

        
                
          
    

    
    
         
          // Zsumuj cyfry „addend” wyrażone w podstawie „n”  addend  =  (  addend  /  n  )  +  (  addend  %  n  );  suma  +=  dodaj  ;  }  // Oblicz liczbę, którą należy dodać do "sumy"  // aby była podzielna przez "n".  int  reszta  =  suma  %  n  ;  int  checkCodePoint  =  (  n  -  reszta   

     
 )  %  n  ;  zwraca  znakOdPunktuKodowego  (  sprawdźPunktKodowy  );  }

A funkcja sprawdzania poprawności łańcucha (ze znakiem kontrolnym jako ostatnim znakiem) to:

   
       
       0
       

    
    
    
          boolean  validateCheckCharacter  (  ciąg znaków  wejściowych  )  {  int  factor  =  1  ;  int  suma  =  ;  int  n  =  liczba prawidłowych znaków wejściowych  ();  // Zaczynając od prawej strony, pracuj w lewo  // Teraz początkowy „czynnik” zawsze będzie wynosił „1”  // ponieważ ostatni znak to znak kontrolny.  for  (  int  i  =  wejście  .  długość  ()  -     0  
           
             

        
                 1  ;  ja  >=  ;  i  --  )  {  int  codePoint  =  codePointFromCharacter  (  input  .  charAt  (  i  ));  int  addend  =  czynnik  *  codePoint  ;  // Zamień „czynnik”, że każdy „punkt kodowy” jest mnożony przez  factor  =  (  factor  ==  2  )  ?  1  :  2  ; 

        
                
          
    

         

       0
 // Zsumuj cyfry „addend” wyrażone w podstawie „n”  addend  =  (  addend  /  n  )  +  (  addend  %  n  );  suma  +=  dodaj  ;  }  int  reszta  =  suma  %  n  ;  powrót  (  reszta  ==  );  }

Algorytm w JavaScript

Zakładając, że zdefiniowane są następujące funkcje:

   


  
     


  
     


  const  codePoints  =  "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"  ;  //Może to być dowolny ciąg dozwolonych znaków  function  numberOfValidInputCharacters  ()  {  return  codePoints  .  długość  ;  }  function  codePointFromCharacter  (  znak  )  {  zwraca  codePoints  .  indexOf  (  znak  );  }  funkcja  znakOdPunktuKodowego  (  
     
 codePoint  )  {  zwraca  codePoints  .  charAt  (  punkt kodowy  );  }

Funkcja generująca znak kontrolny to:

  
       
       0
       

    
    
             0  funkcja  generujCheckCharacter  (  input  )  {  niech  factor  =  2  ;  niech  suma  =  ;  niech  n  =  liczbaPrawidłowychZnakówWejścia  ();  // Rozpoczęcie od prawej strony i praca w lewo jest łatwiejsze, ponieważ  // początkowy "współczynnik" zawsze będzie wynosił "2".  for  (  niech  i  =  wejście  .  długość  -  1  ;  i  >=  ;  i  
           
             

        
                

         --  )  {  niech  codePoint  =  codePointFromCharacter  (  input  .  charAt  (  i  ));  niech  addend  =  factor  *  codePoint  ;  // Zamień „czynnik”, że każdy „punkt kodowy” jest mnożony przez  factor  =  (  factor  ==  2  )  ?  1  :  2  ;  // Zsumuj cyfry „dodaj” wyrażone w podstawie „n” 
                
          
    

    
    
         
           addend  =  (  Math  .  floor  (  addend  /  n  ))  +  (  addend  %  n  );  suma  +=  dodaj  ;  }  // Oblicz liczbę, którą należy dodać do "sumy"  // aby była podzielna przez "n".  niech  reszta  =  suma  %  n  ;  niech  checkCodePoint  =  (  n  -  reszta  )  %  
     
 n  ;  zwraca  znakOdPunktuKodowego  (  sprawdźPunktKodowy  );  }

A funkcja sprawdzania poprawności łańcucha (ze znakiem kontrolnym jako ostatnim znakiem) to:

  
       
       0
       

    
    
    
            funkcja  validateCheckCharacter  (  input  )  {  niech  factor  =  1  ;  niech  suma  =  ;  niech  n  =  liczbaPrawidłowychZnakówWejścia  ();  // Rozpoczynając od prawej strony, pracuj w lewo  // Teraz początkowym „współczynnikiem” będzie zawsze „1”  // ponieważ ostatnim znakiem jest znak kontrolny.  for  (  niech  i  =  wejście  .  długość  -  1  ;  i   0  
           
             

        
                 >=  ;  i  --  )  {  niech  codePoint  =  codePointFromCharacter  (  input  .  charAt  (  i  ));  niech  addend  =  czynnik  *  codePoint  ;  // Zamienić „czynnik”, że każdy „punkt kodowy” jest mnożony przez  factor  =  (  factor  ==  2  )  ?  1  :  2  ; 

        
                
          
    
         
       0
 // Zsumuj cyfry „addend” wyrażone w podstawie „n”  addend  =  (  Math  .  floor  (  addend  /  n  ))  +  (  addend  %  n  );  suma  +=  dodaj  ;  }  niech  reszta  =  suma  %  n  ;  powrót  (  reszta  ==  );  }

Przykład

Pokolenie

Rozważ powyższy zestaw prawidłowych znaków wejściowych i przykładowy ciąg wejściowy abcdef . Aby wygenerować znak kontrolny, zacznij od ostatniego znaku w łańcuchu i przesuń w lewo podwajając każdy inny punkt kodowy. „Cyfry” punktów kodowych zapisane w podstawie 6 (ponieważ istnieje 6 prawidłowych znaków wejściowych) należy następnie zsumować:

Postać	A	B	C	D	mi	F
Punkt kodowy	0	1	2	3	4	5
Podwójnie		2		6 (podstawa 10) 10 (podstawa 6)		10 (podstawa 10) 14 (podstawa 6)
Zmniejszyć	0	2	2	1 + 0	4	1 + 4
Suma cyfr	0	2	2	1	4	5

Suma cyfr wynosi 14 (0 + 2 + 2 + 1 + 4 + 5). Liczba, którą należy dodać, aby otrzymać kolejną wielokrotność 6 (w tym przypadku 18 ) to 4 . To jest wynikowy punkt kodowy kontroli. Powiązanym znakiem kontrolnym jest e .

Walidacja

Wynikowy łańcuch abcdefe można następnie zweryfikować za pomocą podobnej procedury:

Postać	A	B	C	D	mi	F	mi
Punkt kodowy	0	1	2	3	4	5	4
Podwójnie		2		6 (podstawa 10) 10 (podstawa 6)		10 (podstawa 10) 14 (podstawa 6)
Zmniejszyć	0	2	2	1 + 0	4	1 + 4	4
Suma cyfr	0	2	2	1	4	5	4

Suma cyfr wynosi 18 . Ponieważ jest podzielna przez 6, znak kontrolny jest ważny .

Realizacja

0 Odwzorowanie znaków na punkty kodowe iz powrotem można zaimplementować na wiele sposobów. Najprostszym podejściem (podobnym do oryginalnego algorytmu Luhna) jest użycie arytmetyki kodu ASCII. Na przykład, mając dane wejściowe ustawione na 9 , punkt kodowy można obliczyć, odejmując kod ASCII dla „0” od kodu ASCII żądanego znaku. Operacja odwrotna zapewni odwzorowanie odwrotne. Dodatkowe zakresy znaków można obsłużyć za pomocą instrukcji warunkowych.

Zestawy niesekwencyjne można mapować w obie strony za pomocą zakodowanej na stałe instrukcji switch/case . Bardziej elastycznym podejściem jest użycie czegoś podobnego do tablicy asocjacyjnej . Aby to zadziałało, wymagana jest para tablic, aby zapewnić dwukierunkowe mapowanie.

Dodatkową możliwością jest użycie tablicy znaków, gdzie indeksy tablicy są punktami kodowymi powiązanymi z każdym znakiem. Odwzorowanie znaku na punkt kodowy można następnie przeprowadzić za pomocą wyszukiwania liniowego lub binarnego. W tym przypadku odwrotne mapowanie jest po prostu prostym wyszukiwaniem w tablicy.

Słabość

0 To rozszerzenie ma tę samą słabość, co oryginalny algorytm, a mianowicie nie może wykryć transpozycji sekwencji <pierwszy-ważny-znak><ostatni-ważny-znak> na <ostatni-ważny-znak><pierwszy-ważny-znak> (lub odwrotnie). Jest to równoważne transpozycji 09 do 90 (zakładając zestaw prawidłowych znaków wejściowych od do 9 w kolejności). Z pozytywnego punktu widzenia, im większy zestaw prawidłowych znaków wejściowych, tym mniejszy wpływ słabości.

Zobacz też

Międzynarodowy numer identyfikacyjny papierów wartościowych (ISIN)