我想使用Damm 算法为具有 32 个字符的字母的代码生成校验位。该算法本身很容易应用于任何基础（2 或 6 除外）。困难在于必要的查找表，它必须是一个完全反对称的拟群，在主对角线上有一个字符（通常为 0）。
Wikipedia 页面给出了 base-10 的表，Python实现给出了base-16的表，但我没有找到 base-32 的示例。有人有适合base-32的桌子吗？
问问题
2249 次
3 回答
13
受 David Eisenstat 的回答（以及他引用的 Damm 的原始论文）的启发，这里有一个简单的 Python 例程，用于计算/验证2 ≤ n ≤ 32的任何基数 2 n的 Damm 校验和：
# 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 n -1 范围内的整数，包括 0 到 2 n -1，以及每个数字的位数n（假定在 2 范围内）到 32（含）。
Damm 算法的这个实现所使用的完全非对称拟群由映射 ( a , b ) ↦ 2 ⊗ ( a ⊕ b ) 给出，其中 ⊕ 表示有限域GF(2 n ) 中的加法（简单的按位异或), ⊗ 表示GF(2 n )中的乘法，2 表示在 GF(2 n )的通常n位表示中由位串 0...010 2表示的元素。
这等效于 Damm 在他的论文的示例 5.2 中给出的映射 ( a , b ) ↦ ( 2 ⊗ a ) ⊕ b，除了输入数字是b置换的（通过将它们与 GF(2 n ) 中的 2 相乘）确保 ( a , a ) ↦ 0 对于所有a。这相当于对准群运算表的列进行置换，使对角线全为零，并允许通过简单地将校验和附加到原始输入并检查扩展输入的新校验和是否为零来验证校验和。
GF(2 n ) 乘以2是使用左移 1 的常用技巧来实现的，如果设置了结果的第n位，则使用对应于n阶的一元不可约多项式的位掩码对其进行异或运算。使用的特定位掩码取自Gadiel Seroussi (1998) 的低权重二元不可约多项式表。如果您（出于某种原因）需要大于 2 32的基数的校验和，则他们的表会高达 2 10,000. Seroussi 表列出了每个约简多项式的非零系数的指数，不包括常数项；上面代码中的位掩码是通过丢弃最高指数（始终为n ），将其他指数k的 2 k相加并加 1 获得的。（因此，例如，条目“8,4,3,1”对于n = 8 产生掩码 2 4 + 2 3 + 2 1 + 1 = 16 + 8 + 2 + 1 = 27。）
特别是，对于n = 4，上面的代码产生与Johannes Spielmann实现的 base-16 Damm 校验和匹配的结果。这通常不能保证，因为有许多可能的方法可以为给定的基实现 Damm 校验和，但在这种情况下，两个实现使用的准群恰好匹配。
附言。这是一些 Python 代码，用于以类似于 Wikipedia 文章使用的格式打印出查找表。（感谢 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)
于 2014-05-02T17:41:14.787 回答
4
总结下面的讨论：我们想要一个主对角线上有零的表格。Niklas 和我的印象是，该属性不是算法的重要组成部分，而仅仅是为了避免在给定 x 的情况下求解 y 中的方程 x*y = 0，其中 * 是拟群操作。主对角线上有零，我们有 x = y，但没有，我们可以通过在 32 元素表中的一次查找来计算 y。
Damm 描述的构造是有问题的，因为当且仅当 a = -1 时，它才具有所需的属性，但是在特征 2 中，我们有 1 = -1。约束求解器 Z3 没有帮助。
Damm 的论文（德语）在这里。相关定义是拉丁方完全反对称当且仅当[对于所有 x 和 y，(x,y) 元素等于 (y,x) 元素当且仅当 x = y]。Damm 将 (x,y) 元素设为 a*x + y，其中 a 既不是 0 也不是 1，* 是 n 的乘积，从而给出了除 2 以外的素数 n 的构造（包括 n = 32 的情况） -元素伽罗瓦场（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 代码。它可能适用于其他二的幂。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
于 2014-05-02T16:06:00.123 回答
2
如果你有一个 TA 拟群，你可以简单地重新排列列，使 0 在主对角线上。那么拟群（通常）是一个 WTA 拟群，可以用于 Damm 算法。我已经为订单 32 完成了此操作，请参见下面的结果，除了 2 和 6 之外的每个订单都可以这样做。
我认为可以在 Wikipedia 中找到的 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
于 2014-05-11T08:52:05.033 回答