校验位-将Damm算法扩展到32进制

Question

我想使用Damm算法为32个字符的字母表代码生成校验数字。该算法本身很容易应用于任何基数(除了2或6)。困难的是必要的查找表，它必须是一个完全反对称的拟群，在主对角线上只有一个字符(通常是0)。

维基百科页面给出了一个以10为基数的表，Python实现给出了一个以16为基数的表，但我还没有找到一个以32为基数的例子。有人有适合32进制的桌子吗?

Answer 1

受David Eisenstat的回答(以及他引用的Damm的原始论文)的启发，这里有一个简单的Python例程来计算/验证Damm的校验和对于任何基数2ⁿ对于2 ≤ n 勒;32:

# reduction bitmasks for GF(2^n), 2 <= n <= 32
masks = (3, 3, 3, 5, 3, 3, 27, 3, 9, 5, 9, 27, 33, 3, 43, 9,
         9, 39, 9, 5, 3, 33, 27, 9, 27, 39, 3, 5, 3, 9, 141)
# calculate Damm checksum for base 2^n
def damm2n (digits, n):
    modulus = (1 << n)
    mask = modulus | masks[n - 2]
    checksum = 0
    for digit in digits:
        checksum ^= digit
        checksum <<= 1
        if checksum >= modulus: checksum ^= mask
    return checksum

例程接受一个数字列表(或者更一般地说，一个可迭代对象)，假定这些数字是0到2ⁿ& - 1(含)范围内的整数，以及n每个数字的位数(假定在2到32(含)范围内)

这个Damm算法实现所使用的完全不对称拟群由映射(a， b) ↦2 ⊗( oplus;b)，其中& 0 +;表示有限域GF(2ⁿ)中的加法(简单的按位异或)，⊗表示GF(2ⁿ)中的乘法，2表示由位串0表示的元素…010₂在通常的n位表示GF(2ⁿ)。

这相当于映射(a， b) ↦2 ( ⊗) oplus;由Damm在其论文例5.2中给出的b，除了输入数字b排列(通过在GF(2ⁿ)中乘以2)以确保(a， a) &映射;所有a为0。这相当于对拟群运算表的列进行排列，使对角线全部为零，并允许通过将校验和附加到原始输入并检查扩展输入的新校验和是否为零来验证校验和。

GF(2ⁿ)乘以2是用通常的左移1的技巧实现的，如果结果的n-位被设置，则用一个对应于阶n的单不可约多项式的位掩码对其进行XORing。所使用的特定位掩码取自低权重二进制表不可约多项式，加迪尔·塞鲁西(1998)。如果你(出于某种原因)需要大于2³²的校验和，那么他们的表将达到惊人的2^10,000。Seroussi表列出了每个约简多项式的非零系数的指数，不包括常数项;上面代码中的位掩码是通过丢弃最高指数(总是n)，对其他指数k求和2^k并加上1来获得的。(因此，例如，对于n = 8，条目"8,4,3,1"得到掩码2⁴ + 2³ + 2¹ + 1 = 16 + 8 + 2 + 1 = 27)

特别是，上面的代码产生，对于n = 4，结果与Johannes Spielmann实现的基数为16的Damm校验和匹配。通常不能保证这一点，因为有许多可能的方法可以为给定的基数实现Damm校验和，但在这种情况下，两个实现使用的准组恰好是匹配的。

---

p。下面是一些Python代码，以类似于维基百科文章使用的格式打印查找表。(感谢CJM提供的初始版本。)

alphabet = '0123456789ABCDEFGHJKLMNPQRTUVWXY' # avoids easy-to-confuse characters
bits = 5
# find out which first single-digit input gives which checksum
r = [-1] * 2**bits
for i in range(2**bits): r[damm2n([i], bits)] = i
# print header
print '  |',  ' '.join(alphabet)
print '--+' + '--' * len(alphabet)
# print rest of table    
for i in range(2**bits):
    row = (alphabet[damm2n([r[i], j], bits)] for j in range(2**bits))
    print alphabet[i], '|', ' '.join(row)

Answer 2

总结一下下面的讨论:我们想要一个主对角线上有零的表。Niklas和我的印象是，这个性质不是算法的重要组成部分，而仅仅是为了避免求解方程x*y = 0在y中对x给定，其中*是拟群运算。如果主对角线上有0，则x = y，如果没有0，则可以通过在32个元素的表中查找一次来计算y。

Damm描述的结构是有问题的，因为它具有所需的性质当且仅当a = -1，但是，在特征2中，我们有1 = -1。约束求解器Z3没有帮助。

---

Damm的论文(德文)在这里。相关的定义是拉丁方是完全反对称的[对于所有x和y， (x,y)元素等于(y,x)元素[iff x = y]]。Damm通过取(x,y)元素为a*x + y给出了除2以外的素数幂n的构造(包括n = 32的情况)，其中a既不是0也不是1，并且*是n元素伽罗瓦域的乘法(Beispiel 5.2)。

下面是n = 32时这个方法的实例化。

[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31],
 [2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13, 18, 19, 16, 17, 22, 23, 20, 21, 26, 27, 24, 25, 30, 31, 28, 29],
 [4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 8, 9, 10, 11, 20, 21, 22, 23, 16, 17, 18, 19, 28, 29, 30, 31, 24, 25, 26, 27],
 [6, 7, 4, 5, 2, 3, 0, 1, 14, 15, 12, 13, 10, 11, 8, 9, 22, 23, 20, 21, 18, 19, 16, 17, 30, 31, 28, 29, 26, 27, 24, 25],
 [8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 24, 25, 26, 27, 28, 29, 30, 31, 16, 17, 18, 19, 20, 21, 22, 23],
 [10, 11, 8, 9, 14, 15, 12, 13, 2, 3, 0, 1, 6, 7, 4, 5, 26, 27, 24, 25, 30, 31, 28, 29, 18, 19, 16, 17, 22, 23, 20, 21],
 [12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3, 28, 29, 30, 31, 24, 25, 26, 27, 20, 21, 22, 23, 16, 17, 18, 19],
 [14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1, 30, 31, 28, 29, 26, 27, 24, 25, 22, 23, 20, 21, 18, 19, 16, 17],
 [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
 [18, 19, 16, 17, 22, 23, 20, 21, 26, 27, 24, 25, 30, 31, 28, 29, 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13],
 [20, 21, 22, 23, 16, 17, 18, 19, 28, 29, 30, 31, 24, 25, 26, 27, 4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 8, 9, 10, 11],
 [22, 23, 20, 21, 18, 19, 16, 17, 30, 31, 28, 29, 26, 27, 24, 25, 6, 7, 4, 5, 2, 3, 0, 1, 14, 15, 12, 13, 10, 11, 8, 9],
 [24, 25, 26, 27, 28, 29, 30, 31, 16, 17, 18, 19, 20, 21, 22, 23, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7],
 [26, 27, 24, 25, 30, 31, 28, 29, 18, 19, 16, 17, 22, 23, 20, 21, 10, 11, 8, 9, 14, 15, 12, 13, 2, 3, 0, 1, 6, 7, 4, 5],
 [28, 29, 30, 31, 24, 25, 26, 27, 20, 21, 22, 23, 16, 17, 18, 19, 12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3],
 [30, 31, 28, 29, 26, 27, 24, 25, 22, 23, 20, 21, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1],
 [5, 4, 7, 6, 1, 0, 3, 2, 13, 12, 15, 14, 9, 8, 11, 10, 21, 20, 23, 22, 17, 16, 19, 18, 29, 28, 31, 30, 25, 24, 27, 26],
 [7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8, 23, 22, 21, 20, 19, 18, 17, 16, 31, 30, 29, 28, 27, 26, 25, 24],
 [1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14, 17, 16, 19, 18, 21, 20, 23, 22, 25, 24, 27, 26, 29, 28, 31, 30],
 [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12, 19, 18, 17, 16, 23, 22, 21, 20, 27, 26, 25, 24, 31, 30, 29, 28],
 [13, 12, 15, 14, 9, 8, 11, 10, 5, 4, 7, 6, 1, 0, 3, 2, 29, 28, 31, 30, 25, 24, 27, 26, 21, 20, 23, 22, 17, 16, 19, 18],
 [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16],
 [9, 8, 11, 10, 13, 12, 15, 14, 1, 0, 3, 2, 5, 4, 7, 6, 25, 24, 27, 26, 29, 28, 31, 30, 17, 16, 19, 18, 21, 20, 23, 22],
 [11, 10, 9, 8, 15, 14, 13, 12, 3, 2, 1, 0, 7, 6, 5, 4, 27, 26, 25, 24, 31, 30, 29, 28, 19, 18, 17, 16, 23, 22, 21, 20],
 [21, 20, 23, 22, 17, 16, 19, 18, 29, 28, 31, 30, 25, 24, 27, 26, 5, 4, 7, 6, 1, 0, 3, 2, 13, 12, 15, 14, 9, 8, 11, 10],
 [23, 22, 21, 20, 19, 18, 17, 16, 31, 30, 29, 28, 27, 26, 25, 24, 7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8],
 [17, 16, 19, 18, 21, 20, 23, 22, 25, 24, 27, 26, 29, 28, 31, 30, 1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14],
 [19, 18, 17, 16, 23, 22, 21, 20, 27, 26, 25, 24, 31, 30, 29, 28, 3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12],
 [29, 28, 31, 30, 25, 24, 27, 26, 21, 20, 23, 22, 17, 16, 19, 18, 13, 12, 15, 14, 9, 8, 11, 10, 5, 4, 7, 6, 1, 0, 3, 2],
 [31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0],
 [25, 24, 27, 26, 29, 28, 31, 30, 17, 16, 19, 18, 21, 20, 23, 22, 9, 8, 11, 10, 13, 12, 15, 14, 1, 0, 3, 2, 5, 4, 7, 6],
 [27, 26, 25, 24, 31, 30, 29, 28, 19, 18, 17, 16, 23, 22, 21, 20, 11, 10, 9, 8, 15, 14, 13, 12, 3, 2, 1, 0, 7, 6, 5, 4]]

下面是极其蹩脚的Haskell代码。对其他2的幂也适用。main中的参数5表示2^5。

module Main where
import Data.Char
import Data.List
xs +. ys = simplify (xs ++ ys)
xs *. ys
  = simplify $
      do x <- xs
         y <- ys
         return (x + y)
simplify xs
  = (reverse . map head . filter (odd . length) . group . sort) xs
subseqs [] = [[]]
subseqs (x : xs) = let xss = subseqs xs in xss ++ map (x :) xss
polys n = subseqs [n, n - 1 .. 0]
reduce [] ys = ys
reduce xs [] = []
reduce xs@(x : _) ys@(y : _)
  = if x > y then ys else reduce xs (map ((y - x) +) xs +. ys)
irred [] = False
irred ys@(y : _)
  = let xss = polys (y `div` 2) \ [[0]] in
      (not . any null . map (flip reduce ys)) xss
irreds n = filter irred (polys n)
ip n = (head . filter irred . map (n :)) (polys (n - 1))
eval xs = (sum . map (2 ^)) xs
timesTable n
  = let ms = ip n
        zs = polys (n - 1) !! 2
      in
      do xs <- polys (n - 1)
         return $
           do ys <- polys (n - 1)
              return (reduce ms ((zs *. xs) +. ys))
verify t
  = all ((1 ==) . length . filter id) $
      zipWith (zipWith (==)) t (transpose t)
main = print $ map (map eval) $ timesTable 5

Answer 3

如果你有一个TA准群，你可以简单地重新排列列，使0在主对角线上。则该拟群一般为WTA拟群，可用于Damm算法。我已经为订单32这样做了，见下面的结果，除了2和6，这对每个订单都是可能的。

我认为在维基百科中可以找到的10阶拟群是由Damm的论文的引理5.2构造的。这是因为在重新排列列之后，它仍然应该检测语音错误，因此需要重命名元素并相应地重新排列行。

最后，这里是Damm算法的32阶WTA拟群:

00 02 04 06 08 10 12 14 16 18 20 22 24 26 28 30 03 01 07 05 11 09 15 13 19 17 23 21 27 25 31 29 
02 00 06 04 10 08 14 12 18 16 22 20 26 24 30 28 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31 
04 06 00 02 12 14 08 10 20 22 16 18 28 30 24 26 07 05 03 01 15 13 11 09 23 21 19 17 31 29 27 25 
06 04 02 00 14 12 10 08 22 20 18 16 30 28 26 24 05 07 01 03 13 15 09 11 21 23 17 19 29 31 25 27 
08 10 12 14 00 02 04 06 24 26 28 30 16 18 20 22 11 09 15 13 03 01 07 05 27 25 31 29 19 17 23 21 
10 08 14 12 02 00 06 04 26 24 30 28 18 16 22 20 09 11 13 15 01 03 05 07 25 27 29 31 17 19 21 23 
12 14 08 10 04 06 00 02 28 30 24 26 20 22 16 18 15 13 11 09 07 05 03 01 31 29 27 25 23 21 19 17 
14 12 10 08 06 04 02 00 30 28 26 24 22 20 18 16 13 15 09 11 05 07 01 03 29 31 25 27 21 23 17 19 
16 18 20 22 24 26 28 30 00 02 04 06 08 10 12 14 19 17 23 21 27 25 31 29 03 01 07 05 11 09 15 13 
18 16 22 20 26 24 30 28 02 00 06 04 10 08 14 12 17 19 21 23 25 27 29 31 01 03 05 07 09 11 13 15 
20 22 16 18 28 30 24 26 04 06 00 02 12 14 08 10 23 21 19 17 31 29 27 25 07 05 03 01 15 13 11 09 
22 20 18 16 30 28 26 24 06 04 02 00 14 12 10 08 21 23 17 19 29 31 25 27 05 07 01 03 13 15 09 11 
24 26 28 30 16 18 20 22 08 10 12 14 00 02 04 06 27 25 31 29 19 17 23 21 11 09 15 13 03 01 07 05 
26 24 30 28 18 16 22 20 10 08 14 12 02 00 06 04 25 27 29 31 17 19 21 23 09 11 13 15 01 03 05 07 
28 30 24 26 20 22 16 18 12 14 08 10 04 06 00 02 31 29 27 25 23 21 19 17 15 13 11 09 07 05 03 01 
30 28 26 24 22 20 18 16 14 12 10 08 06 04 02 00 29 31 25 27 21 23 17 19 13 15 09 11 05 07 01 03 
03 01 07 05 11 09 15 13 19 17 23 21 27 25 31 29 00 02 04 06 08 10 12 14 16 18 20 22 24 26 28 30 
01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31 02 00 06 04 10 08 14 12 18 16 22 20 26 24 30 28 
07 05 03 01 15 13 11 09 23 21 19 17 31 29 27 25 04 06 00 02 12 14 08 10 20 22 16 18 28 30 24 26 
05 07 01 03 13 15 09 11 21 23 17 19 29 31 25 27 06 04 02 00 14 12 10 08 22 20 18 16 30 28 26 24 
11 09 15 13 03 01 07 05 27 25 31 29 19 17 23 21 08 10 12 14 00 02 04 06 24 26 28 30 16 18 20 22 
09 11 13 15 01 03 05 07 25 27 29 31 17 19 21 23 10 08 14 12 02 00 06 04 26 24 30 28 18 16 22 20 
15 13 11 09 07 05 03 01 31 29 27 25 23 21 19 17 12 14 08 10 04 06 00 02 28 30 24 26 20 22 16 18 
13 15 09 11 05 07 01 03 29 31 25 27 21 23 17 19 14 12 10 08 06 04 02 00 30 28 26 24 22 20 18 16 
19 17 23 21 27 25 31 29 03 01 07 05 11 09 15 13 16 18 20 22 24 26 28 30 00 02 04 06 08 10 12 14 
17 19 21 23 25 27 29 31 01 03 05 07 09 11 13 15 18 16 22 20 26 24 30 28 02 00 06 04 10 08 14 12 
23 21 19 17 31 29 27 25 07 05 03 01 15 13 11 09 20 22 16 18 28 30 24 26 04 06 00 02 12 14 08 10 
21 23 17 19 29 31 25 27 05 07 01 03 13 15 09 11 22 20 18 16 30 28 26 24 06 04 02 00 14 12 10 08 
27 25 31 29 19 17 23 21 11 09 15 13 03 01 07 05 24 26 28 30 16 18 20 22 08 10 12 14 00 02 04 06 
25 27 29 31 17 19 21 23 09 11 13 15 01 03 05 07 26 24 30 28 18 16 22 20 10 08 14 12 02 00 06 04 
31 29 27 25 23 21 19 17 15 13 11 09 07 05 03 01 28 30 24 26 20 22 16 18 12 14 08 10 04 06 00 02 
29 31 25 27 21 23 17 19 13 15 09 11 05 07 01 03 30 28 26 24 22 20 18 16 14 12 10 08 06 04 02 00