Luhn-algoritmen
Luhnalgoritmen, även kallad modulus-10-algoritmen eller mod-10-algoritmen, är en vanligt förekommande algoritm för att beräkna en enkelfelupptäckande kod i form av en kontrollsumma. Luhnalgoritmen används bland annat för att beräkna kontrollsiffran i svenska personnummer, samt i kreditkorts-, postgiro-, bankgiro- och bankkontonummer. Den ingår i kontrollsiffrorna för OCR-nummer (referensnummer på inbetalningskort av typ bankgiro och plusgiro), men där är den ibland kompletterad med en kontrollsiffra som anger entalssiffran i antalet siffror i OCR-numret. På så sätt kan man även upptäcka om en nolla lagts till eller tagits bort ur OCR-numret.
Algoritmen kan alltid upptäcka enkelfel, det vill säga en felskriven siffra, och nästan alltid ett byte av två intilliggande siffror (med undantag av om de två siffrorna är 0 och 9). Om två eller fler siffror är felskrivna finns emellertid en liten risk att felen inte upptäcks därför att de tar ut varandra så att de ger upphov till samma kontrollsiffra. Algoritmen är utformad så att det är möjligt att infoga ett godtyckligt antal nollor i början av koden utan att det påverkar kontrollsiffran (ex 000123 och 123 ger upphov till samma kontrollsiffra).
När algoritmen uppfanns fanns det krav på en enkel algoritm för att kunna kontrollera och generera kontrollsiffror och Luhn-algoritmen uppfyller detta krav. I jämförelse med moderna felupptäckande koder har algoritmen inte någon betydande styrka eller effektivitet.
Algoritmen utvecklades av Hans Peter Luhn på IBM och beskrivs i US patent 2950048, med ansökningsdatum den 6 januari, 1954, och beviljandedatum den 23 augusti, 1960.
Innehåll |
[redigera] Funktionsprincip
[redigera] Kontroll av nummer
Vid kontroll av koden, inklusive kontrollsiffra, fungerar algoritmen på så sätt att med start från den sista siffran i koden (den minst signifikanta siffran), det vill säga kontrollsiffran, multipliceras siffrorna ömsom med 1 och ömsom med 2. Skulle något tal vid en sådan multiplikation bli större än 9 ersätts talet med dess siffersumma (eller, likvärdigt, med talet subtraherat med 9). Därefter summeras talen. Om den erhållna summan är jämnt delbar med 10 så är kontrollsiffran korrekt.
Exempel på personnummer 811218-9876:
8 1 1 2 1 8 9 8 7 6 * 2 1 2 1 2 1 2 1 2 1 ------------------------- ^ ^ ^ ^ ^ ^ ^ ^ ^ 16 1 2 2 2 8 18 8 14 6
Tvåsiffriga produkter splittras upp i ensiffriga tal. Siffrorna summeras därefter:
1+6+1+2+2+2+8+1+8+8+1+4+6 = 50
Denna summa är delbar med 10 och sålunda har vi inte upptäckt något fel i numret.
[redigera] Beräkning av kontrollsiffra
För att beräkna kontrollsiffran är förfarandet likvärdigt, med skillnaden att man multiplicerar ömsom med 2 och ömsom med 1 (det vill säga att man börjar att multiplicera den sista siffran med 2, och inte med 1 som i fallet vid kontroll). Den erhållna summan dras därefter ifrån närmast större 10-tal, varvid kontrollsiffran erhålles.
För att beräkna kontrollsiffran för det niosiffriga personnumret 811218-987 erhålles följande produkter:
8 1 1 2 1 8 9 8 7 * 2 1 2 1 2 1 2 1 2 ------------------------- ^ ^ ^ ^ ^ ^ ^ ^ 16 1 2 2 2 8 18 8 14
Tvåsiffriga produkter splittras upp i ensiffriga tal. Siffrorna summeras därefter:
1+6+1+2+2+2+8+1+8+8+1+4 = 44
Kontrollsiffran erhålls genom att detta tal subtraheras från närmast högre tiotal.
50-44 = 6
Den avslutande kontrollsiffran blir således en sexa. Det tiosiffriga personnumret blir 811218-9876.
[redigera] Implementationer
[redigera] Transact-SQL
Här är en funktion i SQL (för Microsoft SQL Server och Sybase) för att beräkna checksumman, både för "vanliga" summor men även för OCR-koder. Om checksumman för OCR beräknas läggs även kontrollsiffran för längd in.
Varning Denna funktion är inte komplett. Och kommer räkna ut fel kontrollsiffra för personnummer från 2000-talet (då personnumret börjar med 0).
CREATE FUNCTION DBO.LUHN(@NUM1 VARCHAR(20), @ISOCR BIT = 0) RETURNS VARCHAR(22) AS BEGIN DECLARE @NUM BIGINT DECLARE @NUM2 BIGINT DECLARE @I INT DECLARE @SUM INT DECLARE @N INT SET @NUM = CONVERT(BIGINT,@NUM1) IF @ISOCR = 0X1 SET @NUM=@NUM * 10 + ((LEN(@NUM)+2) % 10) SET @NUM2 = @NUM SET @I = 2 SET @SUM=0 WHILE @NUM>0 BEGIN SET @N = @NUM % 10 SET @NUM = (@NUM-@N)/10 IF @N*@I >9 SET @SUM=@SUM + @N*@I - 9 ELSE SET @SUM=@SUM + @N*@I IF @I=2 SET @I=1 ELSE SET @I=2 END DECLARE @R VARCHAR(22) IF 10 -(@SUM % 10) = 10 SET @R= CONVERT(VARCHAR(22),@NUM2 * 10 ) ELSE SET @R = CONVERT(VARCHAR(22),@NUM2 * 10 + (10 -(@SUM % 10))) RETURN @R END GO --EXEMPEL 1 - MED OCR SELECT DBO.LUHN(6000060,1) -- RETURNERAR 600006092 -- LÄNGD 9 SIFFROR KONTROLLSIFFRA 2 -- EXEMPEL 2 - PERSONNUMMER SELECT DBO.LUHN(790501123,0) -- RETURNERAR 7905011230
[redigera] MySQL
Här är en implementation av algoritmen för MySQL (testad på MySL 5.1). Den returnerar 0 för korrekta person- och organisationsnummer. För att beräkna en kontrollsiffra, skicka in hela numret med noll på positionen för kontrollsiffran.
DROP FUNCTION IF EXISTS luhn; DELIMITER // CREATE FUNCTION luhn(p_number VARCHAR(15)) RETURNS CHAR(1) BEGIN DECLARE string_position INTEGER; DECLARE weight INTEGER; DECLARE digits VARCHAR(30); DECLARE digit_sum INTEGER; SET string_position = LENGTH(p_number); SET weight = 1; SET digits = ''; SET digit_sum = 0; -- Beräkna alla viktade termer WHILE string_position > 0 DO SET digits = CONCAT(digits, weight * SUBSTR(p_number, string_position, 1)); SET weight = weight % 2 + 1; SET string_position = string_position - 1; END WHILE; -- Beräkna siffersumma SET string_position = 1; SET digit_sum = 0; WHILE string_position <= LENGTH(digits) DO SET digit_sum = digit_sum + SUBSTR(digits, string_position, 1); SET string_position = string_position + 1; END WHILE; RETURN (10 - digit_sum % 10) % 10; END // DELIMITER ;
[redigera] C
Här är en c-implementation av algoritmen som kontrollerar om kontrollsiffran är korrekt. Funktionen luhn returnerar 0 om kontrollsiffran är korrekt, och annars ett värde x. Om kontrollsiffran är felaktig, kan 10-x adderas till denna varvid en korrekt kontrollsiffra (mod 10) erhålles.
#include <stdio.h> #include <string.h> #include <stdlib.h> int luhn(const char *p) { int m = 1; int sum = 0; int term = 0; if (strlen(p) % 2 == 0) m = 2; while(*p) { term = ( *p - '0' ) * m ; if ( term > 9 ) term -= 9; sum += term; p++; m = 3 - m; } return sum % 10; } int main(int argc, char **argv) { if (argc != 2) exit(1); printf("%d\n", luhn(argv[1])); return 0; }
[redigera] Java
Samma algoritm i java:
class Mod10 { public static int luhn(String indata) { int a = 1; int sum = 0; int term; for (int i = indata.length() - 1; i >= 0; i--) { term = Character.digit(indata.charAt(i),10) * a; if ( term > 9) term -= 9; sum += term; a = 3 - a; } return sum % 10; } public static void main(String[] args) { if (args.length != 1) System.exit(0); System.out.println(luhn(args[0])); } }
[redigera] C#
class luhnProgram { static void Main(string[] args) { if (args.Length > 0) System.Console.WriteLine(luhn(args[0])); } static bool luhn(string pNum) { int sum = 0; for (int i = 0; i < pNum.Length; i++){ int temp = (pNum[i] - '0') << (1 - (i & 1)); if (temp > 9) temp -= 9; sum += temp; } return (sum % 10) == 0; } }
[redigera] Haskell
import Data.Char (digitToInt) luhn :: String -> Int luhn n = (`mod` 10) . sum . map addUp . zipWith (*) lst . reverse . map digitToInt $ n where lst = 1 : 2 : lst addUp c = (c `mod` 10) + (c `div` 10)
[redigera] Matlab eller GNU Octave
function y = luhncheck(x) if ischar(x), x=x-'0'; % Konvertera sträng till heltalsvektorn x end b = x(end-1:-2:1); % Bilda vektorn b av vartannat element i x. y = (mod(sum([x b -(b>4)*9]),10) == 0); % Summera elementen i x med elementen i b. För varje element i b som är >= 5, dra ifrån 9. Kontrollera att summan är delbar med 10.
[redigera] Pascal
En implementation i Pascal som en unit (använd FreePascal eller gpc - The Gnu Pascal compiler - om du vill kompilera nedanstående)
unit luhnunit; interface function luhn( a : string ) : integer; implementation function luhn(a : string ):integer; var x, m, term : word; sum : integer; begin sum := 0; m := 1; for x := length(a) downto 1 do begin term := ( ord(a[x]) - ord('0') ) * m; if term > 9 then term := term - 9; sum := sum + term; m := 3 - m; end; luhn := (sum mod 10); end; { valid } begin end.
[redigera] PHP
Såhär kan personnumret verifieras med PHP.
function luhn($ssn) { $sum = 0; for ($i = 0; $i < strlen($ssn)-1; $i++) { $tmp = substr($ssn, $i, 1) * (2 - ($i & 1)); //växla mellan 212121212 if ($tmp > 9) $tmp -= 9; $sum += $tmp; } //extrahera en-talet $sum = (10 - ($sum % 10)) % 10; return substr($ssn, -1, 1) == $sum; }
[redigera] Javascript
Här är en variant i javascript och html. Den anger även korrekt kontrollsiffra om en felaktig angivits.
<!DOCTYPE html>
<html>
<head>
<title>Luhn</title>
</head>
<body>
<div>
<form method="get" action="">
<fieldset>
<legend>Ange det nummmer som skall kontrolleras</legend>
<input id="luhn" type="text" />
<input type="submit" value="Kontrollera">
</fieldset>
<fieldset>
<legend>Resultat</legend>
<div id="resultat"></div>
</fieldset>
</form>
</div>
<script type="text/javascript">/*<![CDATA[*/
function checkLuhn2(c) {
if (c.match(/[^\d]/)) return "Endast siffror är tillåtet";
if (c.length < 2) return "Måste vara minst två siffror";
var sum = 0, m = 1, d;
var last = c.charAt(c.length - 1) * 1;
for (var i = c.length - 1; i >= 0; i--) {
d = c.charAt(i) * m;
sum += d > 9 ? d - 9 : d;
m = 3 - m;
}
if (sum % 10) {
return "'" + c + "'" + " har en <b>FELAKTIG<\/b> kontrollsiffra. Korrekt siffra är: " + ((10 - (sum - last) % 10) % 10);
}
return "'" + c + "'" + " har en <b>KORREKT<\/b> kontrollsiffra.";
}
document.getElementsByTagName("form")[0].onsubmit = function () {
document.getElementById('resultat').innerHTML = checkLuhn(this.luhn.value);
return false;
};
</script>
</body>
</html>
[redigera] VBA
Function Luhn(ByVal Nummer As Double, Optional Multi As Integer = 1) As Integer 'Luhn funktionen kontrollerar eller genererar en kontrollsiffra enl. Luhn-algoritmen http://sv.wikipedia.org/wiki/Luhn-algoritmen 'Giltiga argument är: Nummer, ett positivt heltal av Single typ (0-3E38) 'Multiplikator 1 eller 2, bestämmer om en kontrollsiffra skall kontrolleras (1) eller genereras (2) 'Resutlatet är ett heltal mellan 0 och 9 där 0 vid kontroll (Multi=1) indikerar en giltig kontrollsiffra 'Vid generering (Multi=2) representerar resutatet helt enkelt kontrollsiffran Dim x As Integer, Text As String, Prod As String Text = Trim(Str(Nummer)) 'Gör en sträng (utan inledande blanksteg) av Numret For x = Len(Text) To 1 Step -1 'Loopar från höger till vänster i strängen Prod = Prod & Val(Mid(Text, x, 1)) * Multi 'Lägger till produkten av varje tal och multiplikator i en sträng If Multi = 2 Then Multi = 1 Else Multi = 2 'Byter värde på multiplikatorn Next x For x = 1 To Len(Prod) 'Loopar igenom listan av produkter Luhn = Luhn + Val(Mid(Prod, x, 1)) '...och summerar dessa tal för tal Next x Luhn = 10 - Val(Right(Str(Luhn), 1)) If Luhn = 10 Then Luhn = 0 End Function
[redigera] XML/XSL
<?xml version="1.0" encoding="UTF-8"?> <xsl:stylesheet version="1.1" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> <xsl:output method="text"/> <xsl:template match="/"> <!-- Testcall --> <xsl:call-template name="Mod10Check"> <xsl:with-param name="InValue">21436587</xsl:with-param> </xsl:call-template> </xsl:template> <!-- Mod10Check --> <xsl:template name="Mod10Check"> <xsl:param name="InValue"/> <xsl:param name="NowPosIn"></xsl:param> <xsl:param name="NowValue">0</xsl:param> <xsl:param name="CurCheckNum">2</xsl:param> <xsl:variable name="NowPos"> <xsl:choose> <xsl:when test="string-length($NowPosIn)=0"> <xsl:value-of select="string-length($InValue)"/> </xsl:when> <xsl:otherwise> <xsl:value-of select="$NowPosIn"/> </xsl:otherwise> </xsl:choose> </xsl:variable> <xsl:choose> <xsl:when test="$NowPos > 0"> <xsl:variable name="iTemp1" select="number(substring($InValue,$NowPos,1)) * $CurCheckNum"/> <xsl:variable name="iTemp2"> <xsl:choose> <xsl:when test="$iTemp1 > 9"> <xsl:value-of select="$iTemp1 - 9"/> </xsl:when> <xsl:otherwise> <xsl:value-of select="$iTemp1"/> </xsl:otherwise> </xsl:choose> </xsl:variable> <xsl:call-template name="Mod10Check"> <xsl:with-param name="InValue" select="$InValue"/> <xsl:with-param name="NowPosIn" select="$NowPos - 1"/> <xsl:with-param name="NowValue" select="$NowValue + $iTemp2"/> <xsl:with-param name="CurCheckNum"> <xsl:choose> <xsl:when test="$CurCheckNum=2 ">1</xsl:when> <xsl:otherwise>2</xsl:otherwise> </xsl:choose> </xsl:with-param> </xsl:call-template> </xsl:when> <xsl:otherwise> <xsl:variable name="NowValue2" select="format-number($NowValue,'00')"/> <xsl:variable name="NextUpTen" select="concat(substring($NowValue2,string-length($NowValue2)-1,1)+1,'0')"/> <xsl:value-of select="substring($NextUpTen - $NowValue,string-length($NextUpTen - $NowValue),1)"/> </xsl:otherwise> </xsl:choose> </xsl:template> </xsl:stylesheet>
[redigera] C/AL
Här är samma algoritm som beräknar kontrollsiffra i C/AL, dvs det språk som används i Microsoft Dynamics Nav.
PROCEDURE Luhn@1000000002(Number@1000000000 : Text[50]) CheckDigit : Integer; VAR LOC_iMultiply@1000000001 : Integer; LOC_iSum@1000000002 : Integer; LOC_iIndex@1000000003 : Integer; LOC_iTerm@1000000004 : Integer; LOC_iPositionInteger@1000000005 : Integer; LOC_iStrLen@1000000006 : Integer; BEGIN LOC_iMultiply := 1; // Rensa bort allt som inte är siffror Number := DELCHR(Number,'=',DELCHR(Number,'=','0123456789')); LOC_iStrLen := STRLEN(Number); IF (LOC_iStrLen MOD 2) = 1 THEN LOC_iMultiply := 2; FOR LOC_iIndex := 1 TO LOC_iStrLen DO BEGIN EVALUATE(LOC_iPositionInteger, FORMAT(Number[LOC_iIndex])); LOC_iTerm := LOC_iPositionInteger * LOC_iMultiply; IF LOC_iTerm > 9 THEN LOC_iTerm := LOC_iTerm - 9; LOC_iSum := LOC_iSum + LOC_iTerm; LOC_iMultiply := 3 - LOC_iMultiply; END; CheckDigit := (10 - (LOC_iSum MOD 10)) MOD 10; END;
[redigera] Python
def luhn(num): """Returnerar Luhns kontrollsiffra""" faktor = 2 summa = 0 for i in map(int, str(num)[::-1]): summa += sum(map(int, str(i * faktor))) faktor = 1 if faktor != 1 else 2 return summa % 10 and 10 - summa % 10
[redigera] Excel
Excel (Svenskt)
Kontroll av slutsiffra, returnerar SANT eller FALSKT.
Tar nummer ur cell A1 i format "ÅÅMMDD-XXXX"
=HÖGER((VÄNSTER(A1)+EXTEXT(A1;3;1)+EXTEXT(A1;5;1)+EXTEXT(A1;8;1)+EXTEXT(A1;10;1))*2-((VÄNSTER(A1)*1>4)+(EXTEXT(A1;3;1)*1>4)+(EXTEXT(A1;5;1)*1>4)+(EXTEXT(A1;8;1)*1>4)+(EXTEXT(A1;10;1)*1>4))*9+EXTEXT(A1;2;1)+EXTEXT(A1;4;1)+EXTEXT(A1;6;1)+EXTEXT(A1;9;1)+HÖGER(A1))="0"
[redigera] Ruby
en modul som räknar ut kontrollsiffran av en talsekvens. Du kommer åt funktionen genom antingen Luhn::getControllNumber() eller Luhn.getControllNumber().
#modul för beräkning av kontrollsiffra och kontroll av kontrollsiffra i luhn-10 algoritmen module Luhn def Luhn.getControllNumber(sequence) sequence=sequence.to_s container = [] factor = 2 sequence.each_character {|z| container << (z.to_i * factor) if(factor==2) factor = 1 else factor = 2 end } sequence = 0 container.each {|z| if(z.to_s.size == 2) sequence += z%10 + z/10 else sequence += z end } factor = ((sequence/10)+1)*10 - sequence return factor end end
Ett annat upplägg
require 'enumerator' module Luhn class CivicNumber attr_reader :civic_number def initialize(civic_number) @civic_number = civic_number.to_s.gsub(/\D/, '') end def valid? civic_number.length == 10 && checksum(civic_number) % 10 == 0 end def control_digit 10 - checksum(civic_number[0...9]) % 10 end def sex valid? ? (civic_number[8...9].to_i.even? ? 'female' : 'male') : 'unknown' end def female? sex == 'female' end def male? sex == 'male' end private def checksum(value) value.split(//).enum_for(:each_with_index).map do |c, i| ((i % 2).even? ? 2 : 1) * c.to_i end.to_s.split(//).inject(0) { |sum, c| sum += c.to_i } end end end class String def as_civic_number Luhn::CivicNumber.new(self) end end class Numeric def as_civic_number Luhn::CivicNumber.new(self.to_s) end end # Usage: # '811218-9876'.as_civic_number.valid? # => true # '811218-9876'.as_civic_number.control_digit # => 6 # '811218-9870'.as_civic_number.valid? # => false # '811218-9870'.as_civic_number.control_digit # => 6
[redigera] Groovy
class Luhn { static void main(String[] args) { if (args) println Luhn.isValid(args[0]) } static boolean isValid(String s) { new Luhn().luhn(s) == 0 } private def add = { i, j -> i + j } private boolean toggle private int multiply(int i) { toggle = !toggle i * (toggle ? 1 : 2) } private int luhn(String s) { toggle = s.size() % 2 == 0 s.collect {multiply(it as int)}.collect {(it > 9) ? it - 9 : it}.inject(0, add) % 10 } }
[redigera] ActionScript
public class LuhnUtil { public static function validate( input:String ) : Boolean { var sum:int = 0; var i:int; var temp:int; for( i=0; i<input.length; i++ ) { temp = (int(input.charAt(i))) << (1 - (i & 1) ); if( temp > 9 ) temp -= 9; sum += temp; } return sum % 10 == 0; } }
