将Damm算法扩展到base-32

Question

我想使用Damm算法为具有32个字符的字母表生成校验位.算法本身很容易应用于任何基础(2或6除外).难点是必要的查找表,它必须是一个完全反对称的拟群,在主对角线下面有一个字符(通常为0).

在维基百科页面给出了基地10台,以及Python实现提供了一个表16为基的,但我还没有找到一个基地-32的例子.有没有人有一个合适的基地32表？

Answer 1

由大卫Eisenstat的回答(和启发通过达姆原始论文,他引用),这里有一个简单的Python程序来计算/验证达姆校验和2中的任何基础^ň 2≤ ñ ≤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以下,并且数Ñ每位比特(假设为在范围2至32包括).

通过此实施达姆算法中使用的完全非对称拟群是由地图(给定的一个,b)↦ 2 ⊗(一个 ⊕ b),其中,⊕表示除了在有限域 GF(2 ^Ñ)(这是简单地按位XOR ),⊗表示在GF(2乘法^ñ),和2表示由比特串0 ... 010表示的元件₂以通常的ñ GF(2比特表示^ñ).

这相当于在地图(一个,b)↦(2 ⊗ 一个)⊕ b由达姆实施例他的论文的5.2,在给定的不同之处在于输入数字是b置换(通过在GF它们与2乘以(2 ^Ñ))确保所有a(a,a)↦0 .这相当于置换拟群操作表的列,使对角线全为零,并允许仅通过将校验和附加到原始输入并检查扩展输入的新校验和为零来验证校验和.

使用通常的左移一个技巧来实现GF(2 ⁿ)乘以2,并且如果设置了结果的第n位,则使用对应于n阶monic不可约多项式的位掩码对其进行异或.所使用的特定位掩码是从所拍摄的低分子量二元不可约多项式的表由加迪尔Seroussi(1998) .如果您(由于某种原因)需要校验和大于2 ^32的基数,他们的表会达到惊人的2 ^10,000.Seroussi表列出了每个归约多项式的非零系数的指数,不包括常数项; 在代码中的位掩码的上方通过丢弃最高指数(总是获得Ñ),一起求和2 ^ķ为其他指数ķ并加入1(因此,例如,条目"8,4,3,1"对于n = 8,得到掩模2 ⁴ + 2 ³ + 2 ¹ + 1 = 16 + 8 + 2 + 1 = 27.)

特别是,对于n = 4,上面的代码产生与Johannes Spielmann 的base-16 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)