存档

文章标签 ‘有限域’

Finite Field Arithmetic

2014年6月28日 没有评论

[latexpage]
在分布式存储系统中,通常通过多副本的方式来保证数据的可靠性。Erasure编码,是分布式系统中用来在保证跟多副本同等可靠性的前提下,减少副本、节约成本的标准做法。有限域(Finite Field)上的四则运算是Erasure编码在分布式存储系统中应用的基础。今天这篇文章介绍一下有限域(Finite Field)及其上面的运算, 后续文章再介绍Erasure编码。

什么是有限域(Finite Field)

大小为$n$的集合,在其上的任何四则运算(加、减、乘、除)的结果仍在这个集合中,表示为$GF(n)$

有限域(Finite Field)有什么样的性质

对于有限域GF(n)中的元素A(0除外), 均存在:
1. $A+B=0$, $B$称之为$A$的加逆, $-A$(Addition inverse, 可以跟相反数据类比)
2. $A*B=1$, $B$称之为$B$的乘逆, $A^{-1}$(Multiplication inverse, 可以跟倒数类比)
由上面的性质可以推论,在有限域上的减法都可以转化为加法,除法都可以转化为乘法

$GF(n)$($n$为素数)有限域上的运算法则

对于$GF(n)$, 如果$n$是素数,可以这样来定义$GF(n)$,及其上的四则运算:
$GF(n) = {0, 1, 2, \dots, n-1}$
加: $A + B = (A + B) \mod n$
减: $A – B = (A + (-B)) \mod n$
乘: $A * B = (A * B) \mod n$
除: $A / B = (A * B^{-1}) \mod n$

阅读全文…