Jimy Ma's Zone
0%

GF( 256 ) 的构造

Posted on Edited on In ,

GF( 256 ) 的构造

步骤

  • Step 1： 找到本原多项式，构造线性反馈移位寄存器
  • Step 2： 构造有限域中乘方表示与向量表示的对照表
  • Step 3： 根据对照表完成有限域的加、减、乘、除的操作，不需要考虑求余( 为什么？ )

GF( 256 ) 的本原多项式

GF( 256 ) = GF( $2^8$ )，本原多项式可以通过 MATLAB 生成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
>> primpoly(8,'all')

Primitive polynomial(s) =

D^8+D^4+D^3+D^2+1
D^8+D^5+D^3+D^1+1
D^8+D^5+D^3+D^2+1
D^8+D^6+D^3+D^2+1
D^8+D^6+D^4+D^3+D^2+D^1+1
D^8+D^6+D^5+D^1+1
D^8+D^6+D^5+D^2+1
D^8+D^6+D^5+D^3+1
D^8+D^6+D^5+D^4+1
D^8+D^7+D^2+D^1+1
D^8+D^7+D^3+D^2+1
D^8+D^7+D^5+D^3+1
D^8+D^7+D^6+D^1+1
D^8+D^7+D^6+D^3+D^2+D^1+1
D^8+D^7+D^6+D^5+D^2+D^1+1
D^8+D^7+D^6+D^5+D^4+D^2+1

我们选择一个去实现就可以了，选择第一个构造线性反馈移位寄存器。

实现线性反馈移位寄存器

采用移位亦或的方法进行实现。

构造乘方表示与向量表示的对照表

根据线性反馈寄存器依次得到向量表示的对照表。

加减乘除四则运算

  • 加： 按位亦或得到新的向量表示再通过查表的方法进行更新乘方表示。
  • 减： 同加
  • 乘：
    • 法1. 被乘数作为基，根据乘数判断是否需要移位，将移位后的数亦或，然后更新乘方表示。
    • 法2. 对应的乘方相加，查找找到向量表示( $\surd$ )。
  • 除： 乘的逆运算

注： 查表的复杂度为 $O(1)$，所以尽量选择查表的方法。