伽罗瓦场：入门指南

域

域是定义了以下操作的数学对象

• 加法： a + b
• 减法 a - b
• 乘法 a * b
• 除法 a / b

其中减法是加法的逆元

a + b - b == a
a + b - a == b

并且除法是乘法的逆元

a * b / b == a
a * b / a == b

还有更多属性

• 结合律： a + (b + c) == (a + b) + c 和 a * (b * c) == (a * b) * c
• 交换律： a + b == b + a 和 a * b == b * a
• 身份：a + 0 == a 和 a * 1 == a
• 分配律：a * (b + c) == a * b + a * c

实数构成一个域，但还有许多其他域。特别是，存在有限域。

有限域

有限域仅包含一定数量的不同成员：这些有限域中的运算变得循环。有限域也称为伽罗瓦域，因此库的名称为 galois_2p8。

伽罗瓦场的标准定义要求成员集的基数是一个素数。也就是说，在标准定义下，不能有一个包含不同成员合数的有限域。

在算术扩展下，具有合数基数的伽罗瓦场是可能的。也就是说，如果基数是一个素数的幂，则基数可以是合数。素数基被称为所结果域的 特征，指数被称为 阶。在本库中，实现的域具有特征为2和阶为8。具有给定特征和阶的伽罗瓦场的简称表示为 GF(特征 ^ 阶)，其中 特征 ^ 阶 可以具体写为指数运算的结果。本库实现了在 GF(2^8) == GF(256) 上进行的操作。

伽罗瓦场的算术扩展将所有成员视为一个度数为扩展阶数减一的多项式，确保在考虑0的情况下，当且仅当有 特征 ^ 阶 个成员时，域中可能有恰好 特征 ^ 阶 个成员。在本库中，域成员被视为一个度数为8的多项式，其中该多项式的系数是伽罗瓦域的两个可能成员：0和1。系数自然映射到位，整个多项式映射到无符号8位整数。

这些代数扩展中的算术遵循多项式算术的一般定义。两个多项式的加法和减法结果是一个多项式，其系数是源多项式中对应系数的加法或减法。除法定义为纯乘法逆，乘法使用域的分配性质进行，但有一个重要的注意事项：为了保持域的性质，乘法在不可约多项式上模运算。

不可约多项式和乘法

一个给定的多项式如果在一般意义上不能表示为两个其他多项式的乘积，则称为不可约。这在整数中类似于素数。用于代数扩展的不可约多项式的度数等于扩展的阶。

在伽罗瓦场的代数扩展中进行乘法时，需要将对多项式的常规分配乘法执行模不可约多项式。也就是说，整体操作的结果必须等于非模运算除以目标不可约多项式的余数。

通常情况下，代数扩张允许存在多个有效的不可约多项式，在这些多项式模下可以进行乘法运算。每个不同的不可约多项式定义了自己的独特伽罗瓦域。

此包实现了所有度数为8的不可约多项式，具有2的特异性质，特别支持本原多项式。

本原多项式

如果一个不可约多项式所生成的域结构使得存在某个基alpha，使得所有幂次（指数为该集合的基数）的集合等于该有限域的所有成员的集合，则称该不可约多项式为本原。也就是说，对于伽罗瓦域中的任意n，alpha ^ n是该伽罗瓦域中的唯一成员。在GF(2 ^ n)的任意n的情况下，alpha是2。

如果不可约多项式是本原多项式，乘法和除法可以用对数和指数表示。以对数和指数表示乘法和除法，所需的存储空间或操作数比使用渲染的乘法和除法表要少。在这个包中，乘法和除法表的设计旨在最小化存储需求，因此对于本原多项式上的域，单元素乘法和除法的实现更快。

请注意，只有不可约多项式的一个子集是本原的。

galois_2p8 包

此包包含对所有不可约多项式的一般GF(2^8)域算术的实现。不可约多项式已通过辅助实用脚本（参见utils/polys.py）预先计算，本原多项式也已通过此预计算识别。对于这些本原多项式，还提供了域算术的特殊实现，利用了能够准确表示指数和对数乘法和除法的特性。

如果编译时使用正确的优化级别，向量加法和减法相关的核预计会产生优化代码，但其他向量核默认为仅是标量操作的循环，除非启用了带有simd功能的SIMD支持。

SIMD 支持