
BoostCommit : 
Subject: [Boostcommit] svn:boost r74362  sandbox/SOC/2011/checks/libs/checks/doc
From: pierre.talbot.6114_at_[hidden]
Date: 20110912 16:07:19
Author: trademark
Date: 20110912 16:07:19 EDT (Mon, 12 Sep 2011)
New Revision: 74362
URL: http://svn.boost.org/trac/boost/changeset/74362
Log:
Merge modulus and algorithm.
Text files modified:
sandbox/SOC/2011/checks/libs/checks/doc/algorithm.qbk  75 +++++++++++
1 files changed, 21 insertions(+), 54 deletions()
Modified: sandbox/SOC/2011/checks/libs/checks/doc/algorithm.qbk
==============================================================================
 sandbox/SOC/2011/checks/libs/checks/doc/algorithm.qbk (original)
+++ sandbox/SOC/2011/checks/libs/checks/doc/algorithm.qbk 20110912 16:07:19 EDT (Mon, 12 Sep 2011)
@@ 63,17 +63,18 @@
addition is ['commutative], so the digit order is not important. The solution is to
attribute fixed ['weight] to each position.
The choice of the weight pattern should respect the following statments:
+The choice of the weight pattern should respect the following statements:
# The weights must be less than the modulus. The explanation is:
``
If weight = modulus, than weight = 0.
And if weight = modulus + 1, than weight = 1.
Finally if weight = modulus + n, than weight = n % modulus.
+If weight = modulus, than weight = 0 because weight * C % modulus = modulus % modulus = 0
+So if weight = modulus + n, than weight = n % modulus because weight * C % modulus = (modulus + n) % modulus = n % modulus.
``
# The weights must be coprime to the modulus. It means the greatest common divisor between
+It proves that a weight has the same impact on the checksum as the same weight plus the modulus.
+
+# A weight must be coprime to the modulus. It means the greatest common divisor between
the weight and the modulus is 1. If a and b are not coprime to the modulus, than
it exists a number n that verify the following equation:
@@ 83,61 +84,27 @@
And this number is a common divisor between a,b and the modulus.
# [HS] An error in the checksum is detected if  new_checksum  checksum  != modulus.
# [HS] The assertion: "new_checksum == checksum" doesn't mean that the number is errorfree.
Digits can be compensated or the check digit altered.

The weight pattern is always a limited sequence that can be repetitive. For example: [~137]
is not repetitive on a sequence with less than 4 numbers but will on a greater sequence.

The weight pattern greatly depends on the modulus. The weights should be coprime to the modulus,
we will prove it with an example:

[table:modulus_influence_on_weight Modulus 10 influence on the weight pattern
[[Position] [1] [2] [3] [4] [5] [6] [7] ]
[[Weight] [1] [3] [5] [8] [1] [3] [5] ]
[[Number] [9] [5] [2] [5] [4] [5] [6] ]
]

The weight pattern choose is [~1358] on a seven digits sequence: [~9525456], so the check digit is:

``
check digit = (1*9 + 3*5 + 5*2 + 8*5 + 1*4 + 3*5 + 5*6) % 10
check digit = 3
``

A checksum with weights that are not coprime to 10 could not detect simple alteration.
For example, we can prove it with the third digit of the sequence above:
``
checksum = 1*9 + 3*5 + 5*X + 8*5 + 1*4 + 3*5 + 5*6
checksum = 113 + 5X
+[note By consequence, all prime modulus can use any weights because they are all coprime.]
+[h5 Luhn algorithm]
check digit = (113 + 5X) % 10
If X = {0,2,4,6,8}
 check digit = 3
If X = {1,3,5,7,9}
 check digit = 7
``
+It's a weighted sum with a modulus 10 and a weight pattern of '12'. The sum is computed from
+right to left. The peculiarity of this algorithm is the treatment on the digits weighted. For
+example, when the weight multiply by the digit exceeds 9, we substract 9 from it. This scheme
+catches every transposition but 9 and 0. It's because 9*2 = 18 and 189 = 9. So 9 multiply by
+the weight '1' give the same result than multiply it by the weight '2'.
To avoid this disaster, we should respect the following formula:
``
modulus € 0+ Strict Positive Integer
+[endsect] [/section:checksum_algorithm Checksum algorithms]
weight >= 0 AND weight < modulus
d1 >= 0 AND d1 < modulus
d2 >= 0 AND d2 < modulus
d1 != d2
+[section:verhoeff_algorithm Verhoeff algorithm]
(Weight * d1) % Modulus != (Weight * d2) % Modulus
``
+The Verhoeff algorithm has been designed to catch all transpositions of two adjacent digits and
+all alterations. It produces a single check digit. Badly, this check can't easily be performed by
+hand from memory.
# Note 1: All prime number modulus can be use with any weight.
+It uses the properties of the dihedral group D5, the elements in this group are not commutative.
+Whatever the manner we can compute these elements, we use three precomputed tables: d, p and inv.
[table:summary Error catching summary
[[][1 Alteration] [2 Alterations] [Twin transpositions] ]
[[Luhn] [18/18 (100%)] [] [88/90 (97.78%)]]
[[Verhoeff] [18/18 (100%)] [] [90/90 (100%)]]
]
+[endsect]
[endsect] [/section:algorithm Common check algorithms]
BoostCommit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk