The Luhn algorithm also known as the "modulus 10" algorithm, is a checksum formula used to verifying a variety of identification numbers, such as credit card numbers and IMEI numbers.
Luhn algorithm provide simple and inexpensive method for computing check digits and provide a simple device for verifying numbers which have a single check digit appended. The Luhn Mod-10 Method is used in a checking system for multi-digit numbers to indicate whether, in transmitting a number, an error has been made, such as a transposition of the digits. It may be used where a great many parts are ordered, manufactured, invoiced, shipped,and billed by multi-digit numbers.
When a number is first assigned to a new part a check digit is computed. This single check digit is appended to the righthand of the part number. The value of this check digit is so computed that in verifying the number by cross addition of multiple digits of the number and the check digit, in accordance with a rule of substitution, the result will be a zero.
e.g: The multi-digit number is 3046016202394 and the check digit is 9. The whole number is 30460162023949.
3 0 4 6 0 1 6 2 0 2 3 9 4 9
x2 x1 x2 x1 x2 x1 x2 x1 x2 x1 x2 x1 x2 x1
-- -- -- -- -- -- -- -- -- -- -- -- -- --
6 0 8 6 0 1 12 2 0 2 6 9 8 9
6+ 0+ 8+ 6+ 0+ 1+ 3+ 2+ 0+ 2+ 6+ 9+ 8+ 9 = 60
In the above summation, any two-digit product is included as the sum of its two digits. In that case the sum of number 12 is 3 (1 + 2). Since the sum of the digits in the bottom row is 60, which is divisible by 10, so the Number is valid because the 60/10 yields no remainder, or 60 mod 10=0. The computation PASSED since the result is zero.
x2 x1 x2 x1 x2 x1 x2 x1 x2 x1 x2 x1 x2 x1
-- -- -- -- -- -- -- -- -- -- -- -- -- --
6 0 8 6 0 1 12 2 0 2 6 9 8 9
6+ 0+ 8+ 6+ 0+ 1+ 3+ 2+ 0+ 2+ 6+ 9+ 8+ 9 = 60
In the above summation, any two-digit product is included as the sum of its two digits. In that case the sum of number 12 is 3 (1 + 2). Since the sum of the digits in the bottom row is 60, which is divisible by 10, so the Number is valid because the 60/10 yields no remainder, or 60 mod 10=0. The computation PASSED since the result is zero.
Here I use PostgreSQL stored function to do generate a check digit for string of numbers.
CREATE OR REPLACE FUNCTION gen_lun10_checkdigit(character varying)
RETURNS character AS
$BODY$
SELECT ((10 - SUM(doubled_digit / 10 + doubled_digit % 10) % 10) % 10)::character
FROM generate_series(0, length($1)- 1) AS n) AS doubled_digits ;
$BODY$
LANGUAGE sql IMMUTABLE STRICT
COST 100;
To find the check digit, call the function by sending a multi-digit number, e.g:
select gen_lun10_checkdigit('3046016202394') as checkdigit;
checkdigit
----------
9
In real world, the Lun algorithm is widely used to verifying numbers such Credit Card and IMEI numbers.
To work with these I wrote this function in PostgreSQL.
CREATE OR REPLACE FUNCTION gen_lun10_number(pprefix character varying,pnumextralen integer) RETURNS character varying AS
$BODY$
DECLARE
vfmt character varying(16);
vnumber bigint;
vnum1 bigint;
vnum2 bigint;
x text;
vresult character varying(19);
BEGIN
pnumextralen := pnumextralen - 1;
vfmt := REPEAT('9', 16);
vnum1 := REPEAT('9', pnumextralen)::int8;
vnum2 := REPEAT('1', pnumextralen)::int8;
SELECT TRUNC (random() * ( vnum2 - vnum1) + vnum1) INTO vnumber;
x = pprefix || vnumber :: text;
vnumber = x::int8;
SELECT 10 * vnumber + ((10 - SUM(doubled_digit / 10 + doubled_digit % 10) % 10) % 10)::int8 FROM (SELECT MOD( (vnumber/ (10^n) ::int8), 10) * (2 - MOD(n,2))::int8 AS doubled_digit FROM generate_series(0, LENGTH(x)-1) AS n) AS doubled_digits INTO vresult;
IF (substr (pprefix,1,1)='0') THEN
vresult := '0' || vresult;
To work with these I wrote this function in PostgreSQL.
CREATE OR REPLACE FUNCTION gen_lun10_number(pprefix character varying,pnumextralen integer) RETURNS character varying AS
$BODY$
DECLARE
vfmt character varying(16);
vnumber bigint;
vnum1 bigint;
vnum2 bigint;
x text;
vresult character varying(19);
BEGIN
pnumextralen := pnumextralen - 1;
vfmt := REPEAT('9', 16);
vnum1 := REPEAT('9', pnumextralen)::int8;
vnum2 := REPEAT('1', pnumextralen)::int8;
SELECT TRUNC (random() * ( vnum2 - vnum1) + vnum1) INTO vnumber;
x = pprefix || vnumber :: text;
vnumber = x::int8;
SELECT 10 * vnumber + ((10 - SUM(doubled_digit / 10 + doubled_digit % 10) % 10) % 10)::int8 FROM (SELECT MOD( (vnumber/ (10^n) ::int8), 10) * (2 - MOD(n,2))::int8 AS doubled_digit
IF (substr (pprefix,1,1)='0') THEN
vresult := '0' || vresult;
RETURN vresult;
END;
$BODY$
LANGUAGE plpgsql VOLATILE COST 100;
You could also find PostgreSQL functions here or other languages in here.
A. Bank Card Number
A bank card number is the primary account number found on credit cards and bank cards. It has a certain amount of internal structure and shares a common numbering scheme. Credit card
numbers are a special case of ISO/IEC 7812 bank card numbers.
numbers are a special case of ISO/IEC 7812 bank card numbers.
An ISO/IEC 7812 number is typically 16 digits in length. It consists of:
- a six-digit Issuer Identification Number (IIN), the first digit of which is the Major Industry Identifier (MII),
- a variable length (up to 12 digits) individual account identifier,
- a single check digit calculated using the Luhn algorithm.
Using the above function, given prefix and length, we got these random number, and I use this site to check credit card.
AMEX
select gen_lun10_number('37',13);--->379385470967314
select gen_lun10_number('34',13);--->344631823379950
VISA
select gen_lun10_number('4539',12); --->4539442682130873
select gen_lun10_number('4556',12);--->4556142088753892
DISCOVER
select gen_lun10_number('6011',12);-->6011865781139571
select gen_lun10_number('622126',10);-->6221269895829522
DINNERS
select gen_lun10_number('304',11);--->30460162023949
select gen_lun10_number('305',11);--->30570718114024
To generate 10 number with prefix '12345' with length of appended numbers 11, simply I use this call.
SELECT c.result
SELECT c.result
FROM (SELECT gen_lun10_number('12345',11) AS result
FROM generate_series(0,9)) as c;
result
-----------------
1234517933942749
1234569174718767
1234582260609360
1234579067268580
1234516226418235
1234565468996135
1234535863889839
1234535902922765
1234594959690825
1234569877669242
B. IMEI
The International Mobile Equipment Identity or IMEI is a number, usually unique, to identify GSM, WCDMA, and iDEN mobile phones, as well as some satellite phones. It is usually found printed inside the
battery compartment of the phone. The IMEI number is used by the GSM network to identify valid devices and therefore can be used for stopping a stolen phone from accessing the network in that country.
battery compartment of the phone. The IMEI number is used by the GSM network to identify valid devices and therefore can be used for stopping a stolen phone from accessing the network in that country.
For example, if a mobile phone is stolen, the owner can call his or her network provider and instruct them to "blacklist" the phone using its IMEI number. This renders the phone useless on that network and sometimes other networks too, whether or not the phone's SIM is changed.
The IMEI is only used for identifying the device and has no permanent or semi-permanent relation to the subscriber. Instead, the subscriber is identified by transmission of an IMSI number, which is stored on a SIM card that can (in theory) be transferred to any handset. However, many network and security features are enabled by knowing the current device being used by a subscriber.
To work with IMEI, we have to know IMEI Structure, IMEI number has 15 decimal digits. Actualy it has 14 digits plus a check digit. First 8 digits of IMEI number are Type Allocation Code which will give you the mobile phone brand and model. Other 7 digits are defined by manufacturer (6 are serial number and 1 is check digit).
To view IMEI of your mobile phone, just press: *#06# and press Call button.
Below were some generated IMEI numbers with predetermined prefix and length.
Samsung SGH-A800
select gen_lun10_number('35357800',7);-->353578007008467 , 353578007478082
RiM BlackBerry Bold 9700
select gen_lun10_number('35425504',7);--> 354255042721045 , 354255045759083
Apple iPhone 3G model MB496RS
select en_lun10_number('01174400',7); -->011744003170479 , 011744001398676
Nokia 6210
select gen_lun10_number('449337',9); -->449337138770594 , 449337951410641
C. Highlights
The Luhn algorithm offers error detection, not offer security, just like a CRC in software. The algorithm help us from accidental errors. By applying the Luhn algorithm using PostgreSQL, I could generate identification numbers for data verification and validation.
You probably interest to read this article that gives inspiration, ...an internal auditor discovered the Luhn algorithm, a simple redundancy check that can be used to validate different identification numbers during fraud and IT audit investigations.
