Algoritmus Měsíce
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od
verze recenzované 27. listopadu 2018; kontroly vyžadují
93 úprav .
Luhnův algoritmus je algoritmus pro výpočet kontrolní číslice čísla plastové karty v souladu s ISO / IEC 7812. Nejedná se o kryptografický nástroj, ale je určen především k odhalování chyb způsobených neúmyslným zkreslením dat (např. při ručním zadávání číselná karta při přijímání informací o čísle sociálního pojištění po telefonu). Umožňuje pouze s určitou mírou jistoty posoudit absenci chyb v bloku čísel, ale nedává možnost zjištění a opravy zjištěných nepřesností.
Algoritmus vyvinul zaměstnanec IBM Hans Peter Lun, popsaný v USA v roce 1954 , patent přijat v roce 1960 .
Nejběžnější aplikace pro výpočet kontrolní číslice jsou:
- Čísla všech bankovních karet
- Čísla některých slevových karet
- Kódy sociálního zabezpečení
- IMEI kódy.
- Výpočet kontrolního znaku jediného 8místného čísla železničního vozu na ruských drahách.
- Výpočet ICCID ( integrated circuit card identifier ) je jedinečné sériové číslo SIM karty.
Algoritmus je v současné době ve veřejné doméně.
Výhody a nevýhody
Díky jednoduchosti implementace vyžaduje algoritmus minimum výpočetního výkonu; v některých případech, pokud máte dovednosti, lze výpočet provést v mysli. Luhnův algoritmus přitom umožňuje detekovat chyby pouze v datových blocích, a ne ve všech. Je detekováno zkreslení jedné číslice. Jsou nalezeny téměř všechny párové permutace po sobě jdoucích číslic (s výjimkou 09 ↔ 90). Některé zkreslení dvou po sobě jdoucích číslic nelze detekovat, konkrétně 22 ↔ 55, 33 ↔ 66 a 44 ↔ 77. Algoritmus neposkytuje informace o místě a povaze chyby.
Algoritmus lze aplikovat na sekvence číslic libovolné délky, je však třeba mít na paměti, že u dostatečně dlouhých čísel se pravděpodobně objeví několik zkreslení dat současně. Některé z těchto chyb mohou vést k mylnému závěru, že kontrolní číslo vypočítané Luhnovým algoritmem potvrzuje neměnnost dat.
Algoritmus pro kontrolu kontrolní číslice
Původní algoritmus popsaný vývojářem
1. Počínaje první číslicí sekvence vlevo a přes jednu číslici (tj. pozice 1, 3, 5, 7, 9, ...) v případě, že je počet číslic v sekvenci lichý (jako v tento příklad, kde je 15, 16- i - kontrola), ale pokud je počet číslic sudý, pak počínaje druhou číslicí sekvence přes jednu číslici (tj. pozice 2, 4, 6, 8, ...), je provedena kontrola: pokud 2 x\u003e 9, pak se součin odečte 9, jinak se součin 2 x ponechá beze změny, kde x je aktuální číslice.
například:
4 5 6 1 2 6 1 2 1 2 3 4 5 4 6 4
8 12 4 2 2 6 10 12
8 3 4 2 2 6 1 3
2. Poté se všechna čísla získaná v předchozím kroku sečtou.
8+5+3+1 + 4+6+2+2 + 2+2+6+4 + 1+4+3+4 = 57
3. Přijatá částka musí být násobkem 10 (to znamená 40, 50, 60, 70, ...). Ve výše uvedeném příkladu je původní sekvence nesprávná.
V příkladu: poslední číslice je šek. Aby bylo číslo platné podle Luhnova algoritmu, musí být kontrolní číslice 7.
4 5 6 1 2 6 1 2 1 2 3 4 5 4 6 7
8 12 4 2 2 6 10 12
8 3 4 2 2 6 1 3
8+5+3+1 + 4+6+2+2 + 2+2+6+4 + 1+4+3+7 = 60
Zjednodušený algoritmus
1. Čísla kontrolované sekvence jsou číslována zprava doleva.
2. Čísla na lichých místech zůstávají nezměněna.
3. Čísla na sudých místech se násobí 2.
4. Vznikne-li v důsledku takového násobení číslo větší než 9, nahradí se součtem číslic výsledného součinu - jednociferným číslem, tedy číslicí.
5. Všechna čísla získaná jako výsledek přepočtu se sečtou. Pokud je součet násobkem 10, pak jsou původní údaje správné.
Příklady implementace výpočtu kontrolní číslice
Jít
// CalculateLuhn vrátí kontrolní číslo
func CalculateLuhn(číslo int) int {
checkNumber := kontrolní součet(číslo)
if checkNumber == 0 {
vrátit 0
}
návrat 10 - kontrolní číslo
}
func kontrolní součet(číslo int) int {
var luh int
pro i := 0; číslo > 0; i++ {
cur := číslo % 10
if i%2 == 0 { // sudé
cur = cur * 2
pokud je > 9 {
cur = cur%10 + cur/10
}
}
luhn += kur
číslo = číslo / 10
}
návrat luhn % 10
}
Num[1..N] — číslo karty, Num[N] — kontrolní číslice.
součet = 0
pro i = 1 až N-1 do
p = Num[Ni]
if (i mod 2 <> 0) then
p = 2*p
if (p > 9) then
p = p - 9
konec pokud
konec pokud
součet = součet + p
příště já
//Doplněk 10
součet = 10 - (součet mod 10)
if (součet == 10) pak
součet = 0
konec pokud
Num[N] = součet
private static boolean isValidLuhn ( hodnota řetězce ) {
int součet = znak . getNumericValue ( hodnota . charAt ( hodnota . délka () - 1 ));
int parita = hodnota . délka () % 2 ;
for ( int i = hodnota . délka ( ) - 2 ; i >= 0 ; i -- ) {
int summand = znak . getNumericValue ( value.charAt ( i ) ) ;
if ( i % 2 == parita ) {
int součin = součet * 2 ;
součet = ( součin > 9 ) ? ( produkt - 9 ) : produkt ;
}
součet += součet ;
}
návrat ( součet % 10 ) == 0 ;
}
#include <string.h> // hlavička deklarující funkci strlen().
int luhn ( const char * card_number ) // přijetí čísla karty jako argumentů {
int len = strlen ( číslo_karty ); // zjistěte délku čísla karty int digit = 0 ; // aktuální číslice ve smyčce (viz níže) int kontrolní_číslo = 0 ; // proměnná, do které bude uložena kontrolní číslice int i ;
for ( i = len - 1 ; i >= 0 ; -- i ) // hlavní smyčka, během ní se vypočítá kontrolní číslice {
číslice = číslo_karty [ i ] - '0' ; // převod číslice z char na int
if ( i % 2 == 0 ) // pokud je pozice číslice sudá, pak: {
číslice *= 2 ; // vynásobte číslo 2
if ( číslice > 9 ) // podle algoritmu by žádné číslo nemělo být větší než 9 číslic -= 9 ; // druhá varianta redukce na jednu číslici }
kontrolní_číslo += číslice ; // přidání čísel do kontrolní_číslice podle algoritmu }
vrátit kontrolní_číslo % 10 ; // vrátí kontrolní číslo vypočítané podle algoritmu }
#include <řetězec>
int luhn ( std :: string const & input )
{
int kontrolní_číslo = 0 ;
bool odd = false ;
for ( auto it = input . rbegin (); it != input . rend (); ++ it )
{
automatická číslice = * it - '0' ;
jestliže (( lichý = ! lichý ))
{
číslice *= 2 ;
if ( číslice > 9 )
číslice -= 9 ;
}
kontrolní_číslo += číslice ;
}
návrat ( kontrolní_číslo * 9 ) % 10 ;
}
Příklady implementace ověření kontrolní číslice
Jít
// Platné kontrolní číslo je platné nebo není založeno na Luhnově algoritmu
func Valid(number int) bool {
návrat (číslo%10+kontrolní součet(číslo/10))%10 == 0
}
func kontrolní součet(číslo int) int {
var luh int
pro i := 0; číslo > 0; i++ {
cur := číslo % 10
if i%2 == 0 { // sudé
cur = cur * 2
pokud je > 9 {
cur = cur%10 + cur/10
}
}
luhn += kur
číslo = číslo / 10
}
návrat luhn % 10
}
function checkLuhn( string purportedCC) {
int sum := 0
int nDigits := length( purportedCC )
int parita := nDigits modul 2
pro i od 0 do nDigits - 1 {
int digit := integer(purportedCC[i])
if is 2 = parita
číslice := číslice × 2
pokud číslice > 9
číslice := číslice - 9
součet := součet + číslice
}
návratnost ( součtový modul 10) = 0
}
#include <stdbool.h> // pro typ bool
#include <string.h> // pro strlen()
bool checkLuhn ( const char * číslo_karty ) // přijetí čísla karty jako argumentu
{
int len = strlen ( číslo_karty ); // zjistěte délku čísla karty
int číslo = 0 ; // aktuální číslice ve smyčce (viz níže)
int součet = 0 ; // proměnná, která bude ukládat kontrolní součet číslic
for ( int i = 0 ; i < len ; i ++ ) // hlavní smyčka , během které se kontroluje platnost čísla karty
{
číslo = číslo_karty [ i ] - '0' ; // převod číslice z char na int
if (( i & 1 ) == 0 ) // pokud je pozice číslice sudá, pak:
{
číslo *= 2 ; // vynásobte číslo 2
if ( číslo > 9 ) // podle algoritmu by žádné číslo nemělo být větší než 9
{
číslo -= 9 ; // druhá varianta redukce na jednociferné číslo
}
}
součet += číslo ; // sčítání čísel k součtu podle algoritmu
if ( součet >= 10 ) // pokud je součet větší než 10
{
součet -= 10 ; // odečtěte 10 od součtu, protože poslední číslice se nezmění
}
}
návratový součet == 0 ; // návrat, pokud je poslední číslice nula
}
bool checkLuhn ( std :: string input ) {
int součet = 0 ;
for ( int i = vstup . délka ( ) - 1 ; i >= 0 ; i -- ) {
int cislo = vstup [ i ] - '0' ;
if ( i % 2 == 0 ) {
číslo *= 2 ;
if ( číslo > 9 ) {
číslo -= 9 ;
}
}
součet += číslo ;
}
návratový součet % 10 == 0 ;
}
z functools import snížit
def luhn ( kód ):
# Předem vypočítané výsledky násobení 2 mínus 9 pro velké číslice
# Indexové číslo se rovná číslu, které se používá na
VYHLEDAT = ( 0 , 2 , 4 , 6 , 8 , 1 , 3 , 5 , 7 , 9 )
kód = snížit ( str . __add__ , filtr ( str . isčíslice , kód ))
sudé = součet ( int ( i ) pro i v kódu [ - 1 :: - 2 ])
šancí = součet ( VYHLEDAT [ int ( i ) ] pro i v kódu [ - 2 :: - 2 ])
návrat (( sudé + kurzy ) % 10 == 0 )
tisknout ( " Splněno: " , luh ( '4561 2612 1234 5467' ))
tisknout ( " Neprošlo : " , luh ( '4561 2612 1234 5464' ))
function luhnAlgorithm ( value ) {
hodnota = hodnota . nahradit ( /\D/g , '' );
var nCheck = 0 ;
var bEven = false ;
for ( var n = hodnota . délka - 1 ; n >= 0 ; n -- ) {
var nDigit = parseInt ( hodnota . charAt ( n ), 10 );
if ( bEven && ( nDigit *= 2 ) > 9 ) {
nČíslice -= 9 ;
}
nCheck += nDigit ;
dokonce = ! bEven ;
}
return ( nKontrola % 10 ) == 0 ;
}
// Kratší verze
const Moon_Algorithm = setValue => {
nechť ch = 0 ;
const num = Řetězec ( setValue ). nahradit ( /\D/g , '' );
const jeLichý = num . délka % 2 !== 0 ;
if ( '' === num ) return false ;
for ( nechť i = 0 ; i < číslo . délka ; i ++ ) {
nech n = parseInt ( num [ i ], 10 );
ch += ( je liché | 0 ) === ( i % 2 ) && 9 < ( n *= 2 ) ? ( n - 9 ) : n ;
}
return 0 === ( ch % 10 );
};
function luhnAlgorithm ( $digit )
{
$cislo = strrev ( preg_replace ( '/[^\d]+/' , '' , $digit ));
$součet = 0 ;
for ( $i = 0 , $j = strlen ( $číslo ); $i < $j ; $i ++ ) {
if (( $i % 2 ) == 0 ) {
$val = $číslo [ $i ] ;
} else {
$val = $cislo [ $i ] * 2 ;
if ( $val > 9 ) {
$val -= 9 ;
}
}
$součet += $val ;
}
return (( $součet % 10 ) === 0 );
}
zábavný řetězec . luhnAlgoritmus () = zpětný chod ()
. map ( Character :: getNumericValue )
. mapIndexed { index , číslice ->
when {
index % 2 == 0 -> číslice
číslice < 5 -> číslice * 2
else -> číslice * 2 - 9
}
}. součet () % 10 == 0
Oracle PL/SQL
nastavit výstup serveru na ;
deklarovat
vpan varchar2 ( 50 ) : = '2345698465' ;
x varchar2 ( 2 ): = 0 ;
s varchar2 ( 3 ): = 0 ;
begin
for i in 1 .. length ( vpan )
loop
x : = substr ( vpan , length ( vpan ) - i + 1 , 1 );
if mod ( i , 2 ) != 0 pak x : = x * 2 ; jestliže x > 9 pak x : = x - 9 ; konec if ; konec if ;
s : = s + x ;
konec -smyčka ;
s : = 10 - mod ( s , 10 );
jestliže s = 10 , pak s : = 0 ; konec if ;
dbms_output . put_line ( 'luhn= ' || s || ' card= ' || vpan || s );
konec ;
TypeScript
var Moon_Algorithm :
any = ( setValue :
any ) : boolean => {
var ch :
number = 0 ,
num :
any = String ( setValue ). nahradit ( /\D/g , '' );
if ( '' === num ) return false ;
for ( var i in num ) {
var n :
číslo = parseInt ( num [ i ], 10 );
ch += 0 === ( i % 2 ) && 9 < ( n *= 2 ) ? ( n - 9 ) : n ;
}
return 0 == ( ch % 10 );
}
Zdroje informací
- US Patent 2,950,048 Computer for Verifying Numbers , Hans P. Luhn, 23. srpna 1960.
Odkazy