用例：有三个数x=2,y=5,z=3,
如何多存储m=1个数，在丢失m=1个数据的时候能够恢复。

一、冗余线性方程组的角度理解

1、三个一次方程解三个未知数$$W_{3\times 3}X_{3\times 1}=B_{3\times 1}$$，如果丢失一个就解不出
$$\left\{ \begin{array}{l} x+y+z=10 \\ x-y+z=0 \\ 2x+y-z=6 \end{array} \right. $$
2、多加m=1或2个线性方程$$W_{5\times 3}X_{3\times 1}=B_{5\times 1}$$ ,则任取其中3个都能解出三个未知数。
$$\left\{ \begin{array}{l} x+y+z=(10)_{miss} \\ x-y+z=0 \\ 2x+y-z=(6)_{miss} \\ x+2y+z=15 \\-x+y+2z=14 \end{array} \right. $$
3、要保证任意三个方程有解，就要使任意三行组成的行列式有逆矩阵，det(W)≠0
范德蒙德或者柯西矩阵能满足这个要求。

柯西矩阵：

二、范德蒙德（Vandermonde）矩阵原理的理解

https://en.wikipedia.org/wiki/Vandermonde_matrix
对于多项式$$y = f(x) = 2 + 5x + 3x^2$$ （系数就是我们要保存的数据2、5、3）
令x=1、2、3 ,y= 10、24、44,假设我们规定1、2、3.是固定的数字，
那么只要记录10,24,44就能反解出系数a、b、c为2，5，3
$$\left\{ \begin{array}{l} a +b+c=10 \\ a\times 2^0+b\times 2^1+c\times 2^2=24 \\ a\times 3^0+b\times 3^1+c\times 3^2=44 \end{array} \right. $$
这就是范德蒙德矩阵的原理(其中一种理解高次曲线的系数和其上的点)
$$\left( \begin{array} {cccc} 1 & 1 & 1 \\ 2^0 & 2^1 & 2^2 \\ 3^0 & 3^1 & 3^2 \end{array} \right) $$
通式：
$$V=\left( \begin{array}{cccccc} 1 & x_1 & x_1^2 & \cdots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{n-1} \\ 1 & x_3 & x_3^2 & \cdots & x_3^{n-1} \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ 1 & x_m & x_m^2 & \cdots & x_m^{n-1}\end{array} \right) $$
$$\det(V)=\prod_{1 \leq i \lt j \leq n}(x_j - x_i)$$
只要xi≠xj(而我们取1、2、3...)，就能保证矩阵有逆。

三、伽罗瓦域

因为存在运算越界问题，引入伽罗瓦域
https://en.wikipedia.org/wiki/Finite_field

                ==> : 同类概念
                ──→ : 概念扩展
┌──────────┬─────────────────────────────────────────────────────────┐
│          │                                                         │
│          │ digits: 0~9          ==>  ┌→ GF(2): ℤ/(2) {0, 1}        │
│  finite  │                           │                             │
│     ↓    │  ↓                        │   ↓                         │
│ infinite │                           │                             │
│          │ integer: ℤ           ==>  │  GF(2)[X]:                  │
│          │ 10²a₂ + 10¹a₁ + a₀        │  a₂x² + a₁x + a₀            │
│ infinite │                           │                             │
│     ↓    │  ↓                        │   ↓               Goal!     │
│   fixed  │                           │                  ↙          │
│          │ GF(7): ℤ/(7) {0..6}  ==>  │  GF(2^8):  GF(2)[X]/(P8(X))  │
│          │ 5 ⊕ 4 = 2   ──────────────┘  (x+1) + (x) = 1            │
│          │ 3 ⊗ 5 = 1                    x¹⁴=x⁴ + x + 1             │
│          │                                                         │
└──────────┴─────────────────────────────────────────────────────────┘

四、伽罗华域Galois-Fiel: GF(7)

元素 0~6
加法 a ⊕ b --> (a + b) mod 7
0 在新世界 GF(7) 里被称为加法的单位元
减法 a ⊖ b --> a ⊕ (-b)
乘法 a ⊗ b --> $$ (a \times b) mod 7$$
模7新世界的乘法⊗来说, 1 是乘法的单位元
乘法逆元 a⁻¹ = b, 若 a ⊗ b = 1.
除法乘以逆元

建立一个简单的, 斜率为1的直线方程:
y=x⊕3
新世界里这个直线上的点是:
 (x,y) ∈ [(0,3), (1,4), (2,5), (3,6), (4,0), (5,1), (6,2)] 只有7个.

y = x ⊕ 3

  y
  ^
6 |     •
5 |   •
4 | •
3 •
2 |           •
1 |         •
0 +-------•-----> x
  0 1 2 3 4 5 6

设定1个斜率为2的直线方程:
y=2⊗x⊕3
新世界里这个直线上的点是: 
(x,y) ∈ [(0,3), (1,5), (2,0), (3,2), (4,4), (5,6), (6,1)] 这7个.

y = 2 ⊗ x ⊕ 3

  y
  ^
6 |          •
5 | •
4 |       •
3 •
2 |     •
1 |           •
0 +---•---------> x
  0 1 2 3 4 5 6

二次曲线的方程:
y=x2⊕x⊕2
这里 x² 表示 x ⊗ x
新世界里这个抛物线上的点集合是: 
(x,y) ∈ [(0, 2) (1, 4) (2, 1) (3, 0) (4, 1) (5, 4) (6, 2)]

y = x^2 ⊕ x ⊕ 2

  y
  ^
6 |
5 |
4 | •       •
3 |
2 •           •
1 |   •   •
0 +-----•-------> x
  0 1 2 3 4 5 6

可以看出它的图像也遵循了旧世界抛物线的特性: 这条抛物线是以3为轴对称的: 因为类似旧世界的多项式分解一样, 原方程也可以分解成:

五、GF(7) 的EC实现

假设模7新世界里我们的数据块 d₁ = 3, d₂ = 2, 对应上面的直线方程: y = 2 ⊗ x ⊕ 3
我们只要记住直线上2个点的位置, 就能把直线的方程恢复出来, 例如:
我们先记录直线上2个点: (1,5) 和 (3,2)
假设丢失的数据是 d₁, d₂ 用 u₁, u₂ 表示, 带入2个点的坐标, 得到一个二元一次方程组:

5=u2⊕u1
2=u2⊗3⊕u1

2个方程左右分别相减消元:

5⊕(−2)=u2⊗(1⊕(−3))⊕u1⊕(−u1)
5⊕5=u2⊗(1⊕4)
3=u2⊗5

最后得到 u₂ = 3 ⊗ 5⁻¹ = 3 ⊗ 3 = 2.
将 u₂ = 2 带入第1个方程:
5 = 2 ⊗ 1 ⊕ u₁
得到 u₁:
u₁ = 5 ⊕ (-2) = 3
是不是跟普通的一次方程组解法完全一样!
至此, 我们用模7新世界的四则运算实现了之前的 EC . 并且我们保证了校验数据的大小是可控的: 不会大于7! 距离我们的目标又接近了1步.
模7下的四则运算构成了1个伽罗华域 Galois-Field: GF(7). 简单来说, Galois-Field 是一个集合, 集合里的元素满足某种四则运算.

六、GF(2): 模2的新世界

只有2个元素{0,1}
加法(刚好和位运算的异或等价):

0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0

1的加法逆元就是1 本身.
乘法(刚好和位运算的与等价):

0 ⊗ 0 = 0
0 ⊗ 1 = 0
1 ⊗ 0 = 0
1 ⊗ 1 = 1

1的乘法逆元就是1 本身. 0 没有乘法逆元.

七、域的扩张

https://en.wikipedia.org/wiki/Field_extension
实数到虚数的扩张
以实数为系数的多项式中，如果选择一个多项式来构造方程：
$$x^2 + 1 = 0$$
这个方程在实数域里无解，但在复数范围内有解的：
$$x=\pm \sqrt{-1}=\pm i$$
通过一个实数系数、但在实数域中无根的方程，得到了复数Complex-Number的定义：
复数就是: 所有实系数多项式模$$x^2 + 1 $$ 的余多项式的集合：
C=R[x]/$$(x^2+1)$$
上面所有的余多项式可表示为：ax+b :a,b都是实数）。
这里ax+b就是我们熟悉的复数：多项式x对应虚数单位i，1对应实数单位1。
而任意2个多项式的四则运算也对应复数的四则运算，如：设：
$$P(x)=x^2+1$$

类似于将实数扩张到复数, 也可以将GF(2) 扩张到 GF($$2^8$$)。
$$P_8(x)=x^8+x^4+x^3+x+1$$

八、GF($$2^8$$)

以GF(2)为基础已经可以构建一个1-bit的EC算法了。
下一步我们希望构建1个1byte大小($$2^8$$个元素)的 Galois-Field GF($$2^8$$)，在这个 GF($$2^8$$)的EC中，每个dj和yi的取值范围可以是0~255。
0~9这10个自然数通过增加“进位”概念后扩展成能表示任意大小的多位十进制自然数，通过类似的方法可以把{0,1}这个GF(2)引入多项式,使用GF(2)的元素作为系数，定义1个多项式.（或者用实数域根式塔类比更恰当）
这些多项式和二进制数有一一对应关系，多项式中指数为i的项系数就是二进制数第i位的值.
类似的，需要1个质的多项式(Prime-Polynomial)，替代GF(7)中7的角色，并应用到GF(2)为系数的多项式的集合中，最终得到1个有256个元素的多项式的伽罗华域 GF($$2^8$$)。
详见：《加密算法AES与伽罗瓦域1-数学基础》
http://139.196.53.116/ml/index.php/archives/138/

发表新评论

纠删码EC与伽罗华域-数学基础