1
$\begingroup$

The Wikipedia page tells me I need to understand permutation groups and dihedral groups. Can someone clearly outline what exactly the perquisites of understanding this is and how much time I'll take to understand this ?

I know some basic group theory. I don't know what dihedral groups are and I haven't studied information theory.

$\endgroup$
  • 1
    $\begingroup$ This is a nice question -- just learned that this sort of checksum was used for pre-Euro German banknotes earlier today; what a happy coincidence! $\endgroup$ – pjs36 Jun 7 '16 at 5:10
  • $\begingroup$ here it is the dihedral group $D_5$ which is used, not very complicated, see its operation table en.wikipedia.org/wiki/Verhoeff_algorithm#Table-based_algorithm . in a regular checksum, the group operation used is the addition modulo $10$, while here we send the digits to $D_5$, and the operation are computed in this group. $\endgroup$ – reuns Jun 7 '16 at 5:32
  • $\begingroup$ at first you need to understand what is a checksum. en.wikipedia.org/wiki/Checksum , then think to how it is possible to improve it for detecting the most frequent errors in this particular case of Dutch postal system $\endgroup$ – reuns Jun 7 '16 at 5:34
  • $\begingroup$ I understand what a checksum and an invariant is. But, not so much what a dihedral group is. $\endgroup$ – user230452 Jun 7 '16 at 6:16
0
$\begingroup$

Bit of a strange question. As (finite) groups go, I'd rate the family of Dihedral groups as the second easiest to get a handle on, after cyclic groups. Only 2 generators - basically a rotation and a reflection of a n-gons. In any book on group theory you are still in an early chapter when you reach this topic :-)

For the agorithm itself, you need very little "group theory" per se. For example one could code the algorithm in java, perl, pascal, whatever without knowing any theory at all (not that I recommend it, but one could).

$\endgroup$
  • $\begingroup$ I'm not interested in just knowing the algorithm without understanding the group theory. After posting this question, I have learnt what dihedral groups are ... But I don't understand why the algorithm works. Can you tell me how I can understand it ? $\endgroup$ – user230452 Jun 9 '16 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.