g2p

文档

该crate可以生成实现快速有限域算术的类型。许多纠错码依赖于形式为GF(2^p)的某种有限域，其中p相对较小。同样，一些加密算法如AES也使用有限域算术。

虽然加法和减法可以通过简单的异或操作快速完成，但乘法则更复杂。为了提高效率，可以使用预计算表。通常这个表会直接复制到源代码中。使用这个crate，您可以享受到预计算表的速度优势，而无需创建具有自定义乘法和除法实现的类型。

警告

由该库生成的类型可能不适合加密用途，因为乘法的时间复杂度无法保证为常数。

注意

该实现针对大小为2^17的有限域进行了测试，编译速度相当快。空间需求与字段大小成线性关系，对于求逆表为线性，对于乘法表为log^2(N)。这意味着无法使用它生成大小为2^32的域，这将需要4*4GB的内存。

示例

use g2p;
g2p::g2p!(GF16, 4, modulus: 0b10011);
let one: GF16 = 1.into();
let a: GF16 = 5.into();
let b: GF16 = 4.into();
let c: GF16 = 7.into();
assert_eq!(a + c, 2.into());
assert_eq!(a - c, 2.into());
assert_eq!(a * b, c);
assert_eq!(a / c, one / b);
assert_eq!(b / b, one);

性能

有一个基准测试套件，比较了该crate与galois_2p8和reed-solomon-erasure的结果，这两个crate都实现了具有256个元素的有限域。

请注意，竞争性库实现了一些特殊功能，以提高其中一个操作数为固定值时的性能。以下是结果

实现细节

g2p生成一个新的类型，该类型实现了所有常见的算术运算。计算是在u8、u16或u32上进行的，具体取决于字段大小。

加法和减法使用常规的Xor实现。对于除法，使用预计算的求逆表来求除数的逆，然后使用以下概述的乘法进行乘法

乘法

乘法使用多个预计算表来确定结果。由于完整的表会随着字段大小的平方增长，这种方法被认为不可行。例如，使用GF65536（即GF(2^16)）的完整表，需要2^32个条目，这意味着程序仅为此表就保留了2*4GB的内存。

相反，数字n被分解为8位组件n = a + 256*b + 65536*c ...。使用这种表示方法，我们可以通过交叉乘法乘以所有组件然后再次相加来乘以两个数字。因此，假设16位数字n = n0 + 256*n1和m = m0 + 256*m1，我们得到n*m = n0*m0 + 256*n0*m1 + 256*n1*m0 + 65536*n1*m1。

现在我们可以为乘以不同组件创建预计算表。有一个表是第一个组件乘以第一个组件，第一个乘以第二个等等。然后只需使用正常的有限域加法将这些结果相加。对于我们的GF65536示例，这意味着乘法表使用4 * 256 * 256个条目，每个条目2字节，约为0.5MB。

许可证

根据Apache License，版本2.0 LICENSE-APACHE 或MIT许可证 LICENSE-MIT>，任选其一。