algorithm - 将 Damm 算法扩展到 base-32

Question

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

Wikipedia page给出一个以 10 为基数的表格，Python implementation给出 table for base-16 ，但我还没有找到 base-32 示例。有没有人有适合 base-32 的表？

Answer 1

受 David Eisenstat 的回答(以及他引用的 original dissertation by Damm)的启发，这里有一个简单的 Python 例程，用于计算/验证任何基数 2ⁿ 的 2 的 Damm 校验和≤ 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 ⊗ ( a ⊕ b)，其中 ⊕ 表示 finite field GF(2ⁿ) 中的加法(这只是按位XOR), ⊗ 表示 multiplication in GF(2ⁿ) , 2 表示通常的 n 位表示中的位串 0...010₂ 表示的元素GF(2ⁿ)。

这相当于 map (a, b) ↦ (2 ⊗ a) ⊕ < em>b 由 Damm 在其论文的示例 5.2 中给出，除了输入数字是 b 置换(通过在 GF(2ⁿ)) 以确保所有 a 的 (a, a) ↦ 0。这相当于置换拟群运算表的列，使对角线全为零，并允许通过将校验和简单地附加到原始输入并检查扩展输入的新校验和是否为零来验证校验和。

GF(2ⁿ) 乘以 2 是使用向左移动一位的常用技巧实现的，如果 n 结果的第 bit 被设置，用对应于 n 阶的一元不可约多项式的位掩码对其进行 XOR。使用的特定位掩码取自 Table of Low-Weight BinaryIrreducible Polynomials by Gadiel Seroussi (1998) 。如果您(出于某种原因)需要大于 2³² 的碱基的校验和，他们的表格会高达 2^10,000。 Seroussi表列出了每个归约多项式的非零系数的指数，不包括常数项；上面代码中的位掩码是通过丢弃最高指数(始终为 n)，将其他指数加在一起 ​​2^k 获得的 < em>k 并加 1。(因此，例如，n = 8 的条目“8,4,3,1”产生掩码 2⁴ + 2³ + 2¹ + 1 = 16 + 8 + 2 + 1 = 27.)

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

---

Ps. 下面是一些 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)