Luhn

Luhn

Luhn 演演算法或是Luhn 公式,也被稱作“模10演演算法”。它是一種簡單的校驗公式,一般會被用於身份證號碼,IMEI號碼,美國供應商識別號碼,或是加拿大的社會保險號碼的驗證。該演演算法是由IBM的科學家Hans Peter Luhn所創造,於1954年1月6日提出該專利的申請,並於1960年8月23日被授予,在美國的專利號為2950048。

該演演算法一直都被大家所公用,並且時至今日應用也很廣泛。它被指定在ISO/IEC7812-1。它的目的不是成為一種加密安全的哈希函數;它的目的是防止意外出現的錯誤,而不是惡意攻擊。很多信用卡和眾多的政府身份識別號碼都使用該演演算法從一系列的隨機數字中提取有效的數字。

優點和缺點

Luhn 演演算法會檢測到任何單碼的錯誤以及幾乎所有的相鄰數字換位的錯誤。但是它不會檢測兩個數字序列09轉90的錯誤(反之亦然)。它會檢測到十分之七的相同雙位數錯誤(不會檢測到22和55的互換,33和66的互換,44和77的互換)。其他更複雜的檢查數字演演算法,如費爾赫夫演演算法,可以檢測出更多的轉錄錯誤。模N的Luhn演演算法是Luhn演演算法的一個擴展,支持非數字字元串。因為該演演算法採取了從右向左的方式,而且零位會影響計算的結果。只有當零位造成了數位的移動或是用零來填充一串數字的開頭時才不會影響計算結果的生成。因此不論在將1234用零填充為0001234之前或是之後,使用Luhn演演算法得到的結果都是一樣的。

該演演算法在美國專利上是為了給手持或是機械設備計算校驗碼。所以它必須儘可能的簡單。

演演算法特點


1、從卡號最後一位數字開始,偶數位乘以2,如果乘以2的結果是兩位數,將結果減去9。
2、把所有數字相加,得到總和。
3、如果信用卡號碼是合法的,總和可以被10整除。

英文描述


1.Counting from the check digit, which is the rightmost, and moving left, double the value of every second digit.
2.Sum the digits of the products (e.g., 10: 1 + 0 = 1, 14: 1 + 4 = 5) together with the undoubled digits from the original number.
3.If the total modulo 10 is equal to 0 (if the total ends in zero) then the number is valid according to the Luhn formula; else it is not valid.

代碼演示


C++:
char digit;
int oddLengthChecksum=0;
int evenLenthChecksum=0;
int position =1;
cout<<"Enter a number:";
digit=cin.get();
while(digit != 10)
{
if(position%2==0)
{
oddLengthChecksum+=doubleDigitValue(digit-'0');
evenLengthChecksum+=digit-'0';
}
else {
oddLengthChecksum+=digit-'0';
evenLenthChencksum+=doubleDigitValue(digit-'0');
}
digit=cin.get();
position++;
}
int checksum;
//對輸入的標識號長度進行奇偶檢查
if((position-1)%2==0) checksum=evenLenthChecksum;
//position-1 原因:前段使用cin.get()函數,最後一個字元是表示結束的行末符
else checksum=oddLengthChecksum;
cout<<"Checksum is"<
if(checksum%10==0)
{
cout<<"Checksum is divisible by 10. Valid.\n";
}
else { cout<<"Checksum is not divisible by 10. Invalid. \n"}
  • 目錄