อัลกอริทึมLuhn mod Nเป็นส่วนขยายของอัลกอริทึม Luhn (หรือที่รู้จักกันในชื่ออัลกอริทึม mod 10) ซึ่งช่วยให้สามารถทำงานกับลำดับของค่าในฐาน เลขคู่ใดๆ ได้ สิ่งนี้มีประโยชน์เมื่อต้องการตัวเลขตรวจสอบเพื่อยืนยันสตริงระบุตัวตนที่ประกอบด้วยตัวอักษร การผสมผสานระหว่างตัวอักษรและตัวเลข หรือชุดอักขระN ใดๆ ที่Nหารด้วย 2 ลงตัว

อัลกอริทึม Luhn ดั้งเดิมได้รับการออกแบบโดยHans Peter Luhnและจดสิทธิบัตรในปี 1960 (ในฐานะอุปกรณ์ทางกายภาพสำหรับการใช้งานอัลกอริทึม) ^{[ 1 ]}เป็น อัลกอริทึม ตัวเลขตรวจสอบที่ออกแบบมาเพื่อตรวจจับข้อผิดพลาดในการป้อนข้อมูลทั่วไปส่วนใหญ่โดยการตรวจสอบการคำนวณตัวเลขของหมายเลขประจำตัวของอัลกอริทึมกับตัวเลขสุดท้าย ("ตัวเลขตรวจสอบ") การใช้งานอัลกอริทึม Luhn ที่พบได้บ่อยอย่างหนึ่งคือในบัตรเครดิตตัวเลขสุดท้ายของหมายเลขบัตรเครดิต 16 หลัก คือผลลัพธ์ของอัลกอริทึม Luhn ที่ใช้กับตัวเลข 15 หลักแรก หมายเลขประจำตัวประชาชน หมายเลขบัญชีธนาคาร หมายเลข ISBNและหมายเลขประจำตัวอื่นๆ อีกมากมายใช้อัลกอริทึม Luhn หรือการดัดแปลงเล็กน้อย^{[ 2 ]}

อัลกอริทึม Luhn ดั้งเดิมเป็นกรณีพิเศษของอัลกอริทึม Luhn mod Nโดยที่Nเท่ากับ 10 อัลกอริทึมนี้รับสตริงตัวเลข (โดยละเว้นตัวเลขสุดท้าย) กลับลำดับของสตริง คูณตัวเลขทุกๆ สองตัวด้วยสอง จากนั้นบวกผลลัพธ์ทั้งหมด ตัวเลขสุดท้ายของผลรวมนี้ควรจะเหมือนกับตัวเลขสุดท้ายของสตริง^{[ 2 ]} (สำหรับตัวอย่างการคำนวณแบบเต็ม โปรดดูที่Luhn algorithm#Description ) เป้าหมายของอัลกอริทึม Luhn คือการตรวจจับข้อผิดพลาดในการป้อนข้อมูลทั่วไปเมื่อป้อนสตริงตัวเลขลงในคอมพิวเตอร์ อัลกอริทึมนี้ตรวจจับข้อผิดพลาดการแทนที่ทั้งหมด ซึ่งตัวเลขหนึ่งถูกแทนที่ด้วยตัวเลขอื่นโดยไม่ได้ตั้งใจ รวมถึงข้อผิดพลาดการสลับตำแหน่งส่วนใหญ่ โดยมี90เทียบกับ09เป็นข้อยกเว้นเพียงอย่างเดียว^{[ 3 ]}แม้ว่าจะเป็นฟังก์ชันแฮชแต่ก็ไม่ได้มีจุดประสงค์เพื่อให้มีความปลอดภัยทางด้านการเข้ารหัสหรือเพื่อตรวจจับข้อผิดพลาดที่เป็นอันตรายหรือการฉ้อโกง^{[ 2 ]}

อัลกอริทึมของลูห์น (Luhn algorithm) ดั้งเดิมเรียกว่าอัลกอริทึม "mod 10" เพราะมันทำการคำนวณแบบโมดูลัสบนระบบตัวเลข 10 หลัก ตัวเลขตรวจสอบ (check digit) สร้างขึ้นโดยการรวมผลลัพธ์จากอัลกอริทึมของลูห์นแล้วนำผลลัพธ์นั้นมาหารด้วย 10 แบบโมดูลัส ซึ่งเทียบเท่ากับเศษที่เหลือจากการหารด้วย 10 หรือหลักหน่วยของตัวเลขนั้น แนวคิดพื้นฐานเดียวกันนี้สามารถนำไปใช้กับระบบตัวเลข N ตัวใดๆ ก็ได้

อัลกอริทึม Luhn mod Nสร้างตัวเลขตรวจสอบ (หรือเรียกให้แม่นยำยิ่งขึ้นคือ อักขระตรวจสอบ) ภายในช่วงอักขระที่ถูกต้องเดียวกันกับสตริงอินพุต ตัวอย่างเช่น หากใช้อัลกอริทึมกับสตริงตัวอักษรพิมพ์เล็ก ( aถึงz ) อักขระตรวจสอบก็จะเป็นตัวอักษรพิมพ์เล็กเช่นกัน นอกเหนือจากความแตกต่างนี้แล้ว อัลกอริทึมนี้ก็คล้ายคลึงกับอัลกอริทึมดั้งเดิมมาก

แนวคิดหลักเบื้องหลังส่วนขยายนี้คือ การแปลงชุดอักขระอินพุตที่ถูกต้องทั้งหมดไปเป็นรายการของรหัสจุด (เช่น จำนวนเต็มเรียงลำดับที่เริ่มต้นจากศูนย์) อัลกอริทึมจะประมวลผลสตริงอินพุตโดยการแปลงอักขระแต่ละตัวเป็นรหัสจุดที่เกี่ยวข้อง จากนั้นทำการคำนวณในรูปแบบ mod N (โดยที่Nคือจำนวนอักขระอินพุตที่ถูกต้อง) สุดท้าย รหัสจุดตรวจสอบที่ได้จะถูกแปลงกลับไปเป็นอักขระตรวจสอบที่สอดคล้องกัน

The Luhn mod N algorithm only works where N is divisible by 2. This is because there is an operation to correct the value of a position after doubling its value which does not work where N is not divisible by 2. For applications using the ISO basic Latin alphabet this is not a problem, since a string of same-case letters has 26 code-points. Adding decimal characters adds a further 10, and adding the other case adds a further 26, maintaining an N divisible by 2 in both cases.

The second step in the Luhn algorithm re-packs the doubled value of a position into the original digit's base by adding together the individual digits in the doubled value when written in baseN. This step results in even numbers if the doubled value is less than or equal to N, and odd numbers if the doubled value is greater than N. For example, in decimal applications where N is 10, original values between 0 and 4 result in even numbers and original values between 5 and 9 result in odd numbers, effectively re-packing the doubled values between 0 and 18 into a single distinct result between 0 and 9.

Where an N is used that is not divisible by 2 this step returns even numbers for doubled values greater than N which cannot be distinguished from doubled values less than or equal to N.

The algorithm will neither detect all single-digit errors nor all transpositions of adjacent digits if an N is used that is not divisible by 2. As these detection capabilities are the algorithm's primary strengths, the algorithm is weakened almost entirely by this limitation. The Luhn mod N algorithm odd variation enables applications where N is not divisible by 2 by replacing the doubled value at each position with the remainder after dividing the position's value by N which gives odd number remainders consistent with the original algorithm design.

Initially, a mapping between valid input characters and code-points must be created. For example, consider that the valid characters are the lower-case letters from a to f. Therefore, a suitable mapping would be:

Note that the order of the characters is completely irrelevant. This other mapping would also be acceptable (although possibly more cumbersome to implement):

It is also possible to intermix letters and digits (and possibly even other characters). For example, this mapping would be appropriate for lower-case hexadecimal digits:

Assuming the following functions are defined:

/// <summary>/// This can be any string of characters./// </summary>privateconststringCodePoints="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";privateintNumberOfValidInputCharacters()=>CodePoints.Length;privateintCodePointFromCharacter(charcharacter)=>CodePoints.IndexOf(character);privatecharCharacterFromCodePoint(intcodePoint)=>CodePoints[codePoint];

The function to generate a check character is:

charGenerateCheckCharacter(stringinput){intfactor=2;intsum=0;intn=NumberOfValidInputCharacters();// Starting from the right and working leftwards is easier since// the initial "factor" will always be "2".for(inti=input.Length-1;i>=0;i--){intcodePoint=CodePointFromCharacter(input[i]);intaddend=factor*codePoint;// Alternate the "factor" that each "codePoint" is multiplied byfactor=(factor==2)?1:2;// Sum the digits of the "addend" as expressed in base "n"addend=IntegerValue(addend/n)+(addend%n);sum+=addend;}// คำนวณจำนวนที่ต้องบวกเพิ่มเข้าไปใน "ผลรวม" // เพื่อให้หารด้วย "n" ลงตัวint remainder = sum % n ; int checkCodePoint = ( n - remainder ) % n ;return CharacterFromCodePoint ( checkCodePoint ); }

และฟังก์ชันสำหรับตรวจสอบความถูกต้องของสตริง (โดยใช้ตัวตรวจสอบเป็นอักขระตัวสุดท้าย) คือ:

bool ValidateCheckCharacter ( string input ) { int factor = 1 ; int sum = 0 ; int n = NumberOfValidInputCharacters ();// เริ่มจากทางขวา ทำงานไปทางซ้าย// ตอนนี้ "ตัวประกอบ" เริ่มต้นจะเป็น "1" เสมอ// เนื่องจากอักขระตัวสุดท้ายเป็นอักขระตรวจสอบfor ( int i = input . Length - 1 ; i >= 0 ; i -- ) { int codePoint = CodePointFromCharacter ( input [ i ]); int addend = factor * codePoint ;// สลับ "ตัวคูณ" ที่แต่ละ "codePoint" ถูกคูณด้วยfactor = ( factor == 2 ) ? 1 : 2 ;// รวมตัวเลขของ "บวก" ที่แสดงในฐาน "n" addend = IntegerValue ( เพิ่ม/ n ) + ( เพิ่ม% n ); ผลรวม+= เพิ่ม; }เศษเหลือสุทธิ= ผลรวม% n ;คืนค่า( ส่วนที่เหลือ== 0 ); }

โดยสมมติว่าฟังก์ชันต่อไปนี้ได้รับการกำหนดไว้แล้ว:

int codePointFromCharacter ( char character ) {...}char characterFromCodePoint ( int codePoint ) {...}จำนวนอักขระที่ป้อนได้ที่ถูกต้อง() {...}

ฟังก์ชันสำหรับสร้างอักขระตรวจสอบคือ:

char generateCheckCharacter ( String input ) { int factor = 2 ; int sum = 0 ; int n = numberOfValidInputCharacters ();// การเริ่มต้นจากทางขวาและทำงานไปทางซ้ายจะง่ายกว่า เนื่องจาก// "ตัวประกอบ" เริ่มต้นจะเป็น "2" เสมอสำหรับ( int i = input . length () - 1 ; i >= 0 ; i -- ) { int codePoint = codePointFromCharacter ( input . charAt ( i )); int addend = factor * codePoint ;// สลับ "ตัวคูณ" ที่แต่ละ "codePoint" ถูกคูณด้วยfactor = ( factor == 2 ) ? 1 : 2 ;// รวมตัวเลขของ "บวก" ที่แสดงในฐาน "n" เพิ่ม= ( เพิ่ม/ n ) + ( เพิ่ม% n ); ผลรวม+= เพิ่ม; }// คำนวณจำนวนที่ต้องบวกเพิ่มเข้าไปใน "ผลรวม" // เพื่อให้หารด้วย "n" ลงตัวint remainder = sum % n ; int checkCodePoint = ( n - remainder ) % n ;คืนค่าcharacterFromCodePoint ( checkCodePoint ); }

และฟังก์ชันสำหรับตรวจสอบความถูกต้องของสตริง (โดยใช้ตัวตรวจสอบเป็นอักขระตัวสุดท้าย) คือ:

boolean validateCheckCharacter ( String input ) { int factor = 1 ; int sum = 0 ; int n = numberOfValidInputCharacters ();// Starting from the right, work leftwards// Now, the initial "factor" will always be "1"// since the last character is the check character.for(inti=input.length()-1;i>=0;i--){intcodePoint=codePointFromCharacter(input.charAt(i));intaddend=factor*codePoint;// Alternate the "factor" that each "codePoint" is multiplied byfactor=(factor==2)?1:2;// Sum the digits of the "addend" as expressed in base "n"addend=(addend/n)+(addend%n);sum+=addend;}intremainder=sum%n;return(remainder==0);}

Assuming the following functions are defined:

constcodePoints="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";//This can be any string of permitted charactersfunctionnumberOfValidInputCharacters(){returncodePoints.length;}functioncodePointFromCharacter(character){returncodePoints.indexOf(character);}functioncharacterFromCodePoint(codePoint){returncodePoints.charAt(codePoint);}

The function to generate a check character is:

functiongenerateCheckCharacter(input){letfactor=2;letsum=0;letn=numberOfValidInputCharacters();// Starting from the right and working leftwards is easier since// the initial "factor" will always be "2".for(leti=input.length-1;i>=0;i--){letcodePoint=codePointFromCharacter(input.charAt(i));letaddend=factor*codePoint;// Alternate the "factor" that each "codePoint" is multiplied byfactor=(factor==2)?1:2;// Sum the digits of the "addend" as expressed in base "n"addend=(Math.floor(addend/n))+(addend%n);sum+=addend;}// Calculate the number that must be added to the "sum"// to make it divisible by "n".letremainder=sum%n;letcheckCodePoint=(n-remainder)%n;returncharacterFromCodePoint(checkCodePoint);}

And the function to validate a string (with the check character as the last character) is:

functionvalidateCheckCharacter(input){letfactor=1;letsum=0;letn=numberOfValidInputCharacters();// Starting from the right, work leftwards// Now, the initial "factor" will always be "1"// since the last character is the check character.for(leti=input.length-1;i>=0;i--){letcodePoint=codePointFromCharacter(input.charAt(i));letaddend=factor*codePoint;// Alternate the "factor" that each "codePoint" is multiplied byfactor=(factor==2)?1:2;// Sum the digits of the "addend" as expressed in base "n"addend=(Math.floor(addend/n))+(addend%n);sum+=addend;}letremainder=sum%n;return(remainder==0);}

Consider the above set of valid input characters and the example input string abcdef. To generate the check character, start with the last character in the string and move left doubling every other code-point. The "digits" of the code-points as written in base 6 (since there are 6 valid input characters) should then be summed up:

The total sum of digits is 14 (0 + 2 + 2 + 1 + 4 + 5). The number that must be added to obtain the next multiple of 6 (in this case, 18) is 4. This is the resulting check code-point. The associated check character is e.

The resulting string abcdefe can then be validated by using a similar procedure:

The total sum of digits is 18. Since it is divisible by 6, the check character is valid.

การแปลงอักขระเป็นรหัสจุดและแปลงกลับสามารถทำได้หลายวิธี วิธีที่ง่ายที่สุด (คล้ายกับอัลกอริทึมของ Luhn ดั้งเดิม) คือการใช้การคำนวณรหัส ASCII ตัวอย่างเช่น เมื่อกำหนดชุดข้อมูลอินพุตตั้งแต่0ถึง9รหัสจุดสามารถคำนวณได้โดยการลบรหัส ASCII ของ '0' ออกจากรหัส ASCII ของอักขระที่ต้องการ การดำเนินการย้อนกลับจะให้ผลลัพธ์ที่ตรงกันข้าม นอกจากนี้ยังสามารถจัดการกับช่วงอักขระเพิ่มเติมได้โดยใช้คำสั่งเงื่อนไข

ชุดข้อมูลที่ไม่เรียงลำดับสามารถแมปได้ทั้งสองทางโดยใช้ คำสั่ง switch/case ที่กำหนดไว้ล่วงหน้า วิธีการที่ยืดหยุ่นกว่าคือการใช้สิ่งที่คล้ายกับอาร์เรย์แบบเชื่อมโยงเพื่อให้ได้ผลลัพธ์เช่นนี้ จำเป็นต้องมีอาร์เรย์สองตัวเพื่อให้สามารถแมปได้ทั้งสองทาง

อีกทางเลือกหนึ่งคือการใช้อาร์เรย์ของอักขระ โดยที่ดัชนีของอาร์เรย์คือรหัสจุดที่เกี่ยวข้องกับแต่ละอักขระ จากนั้นสามารถทำการจับคู่จากอักขระไปยังรหัสจุดได้โดยใช้การค้นหาเชิงเส้นหรือการค้นหาแบบไบนารีในกรณีนี้ การจับคู่ย้อนกลับก็เป็นเพียงการค้นหาในอาร์เรย์อย่างง่ายเท่านั้น

ส่วนขยายนี้มีจุดอ่อนเช่นเดียวกับอัลกอริทึมดั้งเดิม กล่าวคือ ไม่สามารถตรวจจับการสลับตำแหน่งของลำดับ<อักขระที่ถูกต้องตัวแรก><อักขระที่ถูกต้อง ตัวสุดท้าย> เป็น <อักขระที่ถูกต้องตัวสุดท้าย><อักขระที่ถูกต้อง ตัวแรก> (หรือในทางกลับกัน) ซึ่งเทียบเท่ากับการสลับตำแหน่งของ09เป็น90 (โดยสมมติว่าชุดอักขระอินพุตที่ถูกต้องมีตั้งแต่0ถึง9ตามลำดับ) ข้อดีคือ ยิ่งชุดอักขระอินพุตที่ถูกต้องมีขนาดใหญ่ขึ้น ผลกระทบของจุดอ่อนก็จะยิ่งน้อยลง^{[ 4 ]}

• หมายเลขประจำตัวหลักทรัพย์ระหว่างประเทศ (ISIN)