请问有人能够为我解释一下吗?
编辑: 谢谢大家的回答,但为什么这种方法只是一种不同的乘法等算法,它却要使用完全不同的数据类型呢?
左边 = 普通乘法,右边 = 无进位乘法
1 1 0 1 1 1 0 1
* 1 0 0 1 1 0 0 1
------------ --> --------------
(1)1 1 0 1 <-- (1) is carry 1 1 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 0 1 + 1 1 0 1 + GF(2) or XOR
------------- ---------------
1 1 1 0 1 0 1 1 1 0 0 1 0 1
对角线下降矩阵中的每个1或0表示向量“1101”和另一个向量“1001”的一个源位的部分积。
右侧应用于CRC,(ECC)错误校正码计算(Reed Solomon、BCH)和密码学(椭圆曲线、AES内部)。
说明与多项式乘法的联系,上述操作可以总结为:
1101 == x^3 + x^2 + 0 + 1;
1001 == x^3 + 0 + 0 + 1;
常规的多项式乘法为:p(x) * (x^3 + 1) == p(x)*x^3 + p(x) ==
(x^3 + x^2 + 1)(x^3 + 1) == x^6+x^5+x^3 + x^3+x^2+1
== 1x^6 + 1x^5 + 0x^4 + 2x^3 + 1^x2 + 0x + 1
== "1102101"
在GF(2)中,每个系数都被模2简单地计算,从而得出1100101b。
GF中的数据类型看起来就像uint8_t、uint16_t或者128_t,在GF(2^8)中,数据类型包含256种独特的位模式。然而例如位模式'00010001'并没有传统的解释。(它不是十进制17,但可能是unity的123次幂,除以另一个多项式的余数。)将这个数字乘以相同的"unity"模生成多项式g(x),导致124次幂等等。然后有限域的性质(恒等式)就有有趣的应用——例如可以(远程)轻松计算要附加到文件的32位数字以使其32位CRC匹配;或者可以使用这些属性对crc计算进行并行化,或者在有限域中实现类傅里叶变换的大数乘法(数论变换)。
poly8x16_t vmulq_p8 (poly8x16_t, poly8x16_t)
给出了期望指令的形式:vmul.p8 q0, q0, q0
。如果是 vmul.p8
,那么它是否意味着 GF(2^8),但您的解释是 GF(2)?也就是说,在第八位没有进位,但在中间有进位。GF(2) 乘法是 XOR/EOR
。 - artless noisevmull
和**GF(256)而不是GF(2^8)**。 - artless noiseVMUL.P8
。 - Aki Suihkonen您没有描述PMUL与PMULL之间的区别。
据我所知(可能不正确),每个单元的PMUL作用于两个8位源元素,并生成一个8位结果元素。
每个单元的PMUL生成8个部分积,每个部分积在异或之前都会移位。因此从第一个PP的LSB到最后一个PP的MSB,似乎有15位结果。但是,PMUL只能存储8位结果。
这15位结果中的最高有效7位是否被丢弃了?
作为参考,这段来自Cortex-A Series Programmer’s Guide (v4)的第七章第二节:
在实现某些密码学或数据完整性算法时,多项式算术非常有用。
在{0,1}上添加两个多项式等同于按位异或。多项式加法的结果与传统加法不同。
在{0,1}上乘以两个多项式首先需要确定部分积,就像传统乘法一样,然后将部分积进行异或操作而不是传统加法。多项式乘法的结果与传统乘法不同,因为它需要对部分积进行多项式加法。
typedef short poly16_t;
- this