Luhn algorithm (modulus 10)
What is the Luhn algorithm?
The Luhn algorithm, also called modulus 10 or modulus 10 algorithm, is a simple mathematical formula used to validate a user's identification numbers. Originally created by a group of mathematicians and inventor Hans Peter Luhn in the 1960s, the Luhn algorithm is used by most major credit card companies to verify that the cardholder's number is valid. It is also used to validate number sequences for government identification numbers, Social Security numbers, Social Insurance numbers in Canada and International Mobile Equipment Identity (IMEI) numbers. The algorithm, which is in the public domain and can be used by anyone, was designed to detect incorrect values and single-digit errors that may have been introduced by mistyping but not specific malicious attacks.
The mathematical formula used is called a checksum, which is a value that represents the number of bits in a transmission message. Similar to how a checksum is used in Luhn's algorithm, checksums are commonly used by IT professionals to detect high-level errors within data transmissions.
How does the Luhn algorithm work?
The Luhn formula applies some basic arithmetic to an identification number to calculate a value that must agree with the check digit -- which, for example, is the last number that appears on the credit card. Here are the formula's four steps:
- Beginning on the top line at the second digit from the end, going from right to left, multiply every other number on the "Digit" line by two.
- Again, proceeding right to left, take each of the digits skipped in step 1 and multiply it by 1.
- Next, add the numbers from steps 1 and 2 together on the "Product" line. If doubling a number in step 1 results in a two-digit number, such as 5 x 2 = 10, use the sum of each of these digits -- 1 + 0 = 1 -- when adding the sum of the products.
- If the sum of the numbers added up ends in 0, then the number is valid. If not, it is invalid.
Real-world examples of the Luhn algorithm
Businesses can use the Luhn formula to ensure a credit card number is valid before sending it for authorization. Credit card companies, including American Express, Visa, Mastercard and Discover, use the Luhn algorithm. It does not verify any other information on a credit card, including whether the card's date is valid.
The IMEI number is used to identify hardware type for a mobile phone. Every mobile phone has a unique 15- to 17-digit code, and the leftmost digits contain information about the phone type. An IMEI code can also be used to prevent a misplaced or stolen phone from being used to make calls, as well as help someone who buys a used phone determine if the phone is valid.
The Luhn formula can also be used with gift cards, where a gift card code is generated with a random number and a checksum is associated with it. The gift card code is stored in a database with its associated data. The Luhn algorithm ensures the gift code, if written by a person, is valid and without mistakes.
Aside from validating credit card numbers and gift cards, other instances of the use of the Luhn algorithm include the following:
- SIM card numbers
- survey codes
- point-of-sale systems
- South African ID numbers
- Swedish national identification numbers
- programming languages and code libraries
There are several digital authentication methods used today, including passwords and two-factor authentication. Learn what other forms of authentication are used to verify electronic authenticity.
