标签: galois-field

我试图在Python中实现一个Reed-Solomon编码器解码器,支持解码擦除和错误,这让我发疯.

该实现目前仅支持解码错误或仅解码,但不能同时解码两者(即使它低于2*错误+删除的理论界限<=(nk)).

从Blahut的论文(这里和这里),似乎我们只需要用擦除定位多项式初始化错误定位多项式,以隐式计算Berlekamp-Massey内的勘误定位多项式.

这种方法部分适用于我:当我有2*错误+删除<(nk)/ 2时它可以工作,但事实上在调试之后它只能起作用,因为BM计算错误定位多项式,它获得与擦除定位多项式完全相同的值(因为我们低于仅错误校正的限制),因此它被galois字段截断,我们最终得到了擦除定位多项式的正确值(至少我理解它的方式,我可能是错的).

然而,当我们超过(nk)/ 2时,例如如果n = 20且k = 11,那么我们有(nk)= 9个擦除的符号我们可以纠正,如果我们输入5个擦除然后BM就会出错.如果我们输入4个擦除+ 1个错误(我们仍然远低于界限,因为我们有2*错误+删除+ 2 + 4 = 6 <9),BM仍然出错.

我实现的Berlekamp-Massey的精确算法可以在本演示文稿中找到(第15-17页),但是在这里和这里可以找到非常相似的描述,在这里我附上了数学描述的副本:

现在,我将这个数学算法几乎完全复制到Python代码中.我想要的是扩展它以支持擦除,我尝试通过使用擦除定位器初始化错误定位器sigma:

def _berlekamp_massey(self, s, k=None, erasures_loc=None):
    '''Computes and returns the error locator polynomial (sigma) and the
    error evaluator polynomial (omega).
    If the erasures locator is specified, we will return an errors-and-erasures locator polynomial and an errors-and-erasures evaluator polynomial.
    The parameter s is the syndrome polynomial (syndromes encoded in …

我试图在极其有限的嵌入式平台上生成QR码.在一切的规范,似乎除了产生错误纠正码字相当简单.我已经看了一堆现有的实现,他们都试图实现一堆直接超越我的头的多项式数学,特别是关于Galois域.在数学复杂性和内存需求方面,我能看到的最简单的方法是在规范本身中列出的电路概念:

通过他们的描述,我相信我可以实现这一点,除了标有GF(256)加法和GF(256)乘法的部分.

他们提供这个帮助:

QR码的多项式算法应使用逐位模2算术和逐字模100011101算法计算.这是2 ^ 8的伽罗瓦域,其中100011101表示场的素数模数多项式x ^ 8 + x ^ 4 + x ^ 3 + x ^ 2 + 1.

这对我来说几乎都是希腊人.

所以我的问题是:在这种伽罗瓦域算术中执行加法和乘法的最简单方法是什么？假设两个输入数字都是8位宽,我的输出也需要是8位宽.几个实现预先计算,或硬编码在两个查找表中以帮助解决这个问题,但我不确定如何计算这些,或者我将如何在这种情况下使用它们.我宁愿不为这两个表采用512字节内存命中,但它实际上取决于替代方案.我真的需要帮助了解如何在此电路中执行单个乘法和加法运算.

你知道C++ 中Galois域算法的实现吗？至少应包括GF(2 ¹⁶)和GF(2 ³²)等案例.性能是一个问题,因此实现应该考虑优化其操作.

我更喜欢一个通用的计算库或一个专门用于此任务的小型库.缺乏这些,我也欢迎一些可读的源代码.

AVX-512 指令集扩展之一是AVX-512 + GFNI，“伽罗华域新指令”。

伽罗瓦理论是关于域扩展的。这与处理矢量化整数或浮点值有什么关系？指令应该执行“Galois 域仿射变换”，它的逆，以及“Galois 域乘以字节”。

那些是什么领域？这些说明实际上做了什么，它有什么用？

这两个函数执行扩展欧几里德算法,然后找到乘法逆.这个顺序似乎是正确的,但它并没有按照悉尼大学的这个工具回复http://magma.maths.usyd.edu.au/calc/,因为这是在GF(2)完成的. )有限域,我想我错过了从基数10转换到这个字段的一些关键步骤.

这在基数10上进行了测试和处理,但是在这里可能无法接收具有二进制系数的多项式.所以我的问题是我错误地应用于这个算法的Python的哪些部分,例如// floor,可能无法承载基本10中的函数能够在GF(2)中执行此操作.

上面的工具可以像这样测试:

R<x>:=PolynomialRing(GF(2));
p:=x^13+x+1; q:=x^12+x;
g,r,s:=XGCD(p,q);

g eq r*p+s*q;

g,r,s;

功能:

def extendedEuclideanGF2(self,a,b): # extended euclidean. a,b are values 10110011... in integer form
    inita,initb=a,b;  x,prevx=0,1;  y,prevy = 1,0
    while b != 0:
        q = int("{0:b}".format(a//b),2)
        a,b = b,int("{0:b}".format(a%b),2);
        x,prevx = (int("{0:b}".format(prevx-q*x)), int("{0:b}".format(x,2)));  y,prevy=(prevy-q*y, y)
    print("Euclidean  %d * %d + %d * %d = %d" % (inita,prevx,initb,prevy,a))
    return a,prevx,prevy  # returns gcd of (a,b), and factors s and t

def modular_inverse(self,a,mod): # a,mod are integer values …

我的GCM SP-800-38D文档中puting开块的乘法(Alogrithm 1)C代码这里.第11-12页.

完成代码后,我想看看是否有任何方法可以测试代码.您可以在我提供的代码下面找到附件.请注意,我使用24位块代替128位块,仅用于测试目的.如有必要,我将不胜感激.

void BLK_MUL (u8 *val_1,u8 *val_2, u8 *out_val)
{ 

    u8 xdata R_val = 0xE1;     
    u8 xdata Z_val[3],V_val[3];
    u8 mask_b   = 0x80;        
    u16 i;  u8 j;           
    bit rnd;                

    for(j=0;j<3;j++,++val_2)    
    {
        Z_val[j]=0x00;      
        V_val[j]=*val_2;    
    }       


    for(i=0;i<24;i++)
    { 
        if (*val_1 & mask_b)
        {
            for(j=0;j<3;j++)    
                Z_val[j]^=V_val[j]; 
        }
        if (!(V_val[2] & 0x01))
        {//if LSB of V_val is 0
            for(j=0;j<3;j++)
            { //V_val = rightshift(V_val)
                if (j!=0)
                    if (V_val[2-j] & 0x01)
                        V_val[3-j] |= 0x80;
                V_val[2-j]>>=1;          
            }
        }
        else
        {//if LSB of V_val is …

我希望能够计算

g^x = g * g * g * ... * g     (x times)

其中 g 位于有限域 GF(2^m) 中。这里 m 相当大，m = 256、384、512 等，因此查找表不是解决方案。我知道有类似想法的快速算法，modpow for Z/nZ（参见HAC第 619-620 页）。

1. 什么是快速、非基于表格的计算周期的方法（即 g^x）？
2. 这绝对是一个一厢情愿的问题，但问题来了：蒙哥马利乘法/求幂的想法可以“回收”到伽罗瓦域吗？我想这样认为，因为同构特性，但我真的不知道。

备注：这是我在 math.stackoverflow.com 上的帖子，我认为这是提出这个问题的最佳社区。

我想在galois字段(GF4)上使用numpy数组.所以,我将GF4类设置为数组元素.它适用于数组+整数计算,但它不适用于数组+数组计算.

import numpy

class GF4(object):
    """class for galois field"""
    def __init__(self, number):
        self.number = number
        self.__addL__ = ((0,1,2,3),(1,0,3,2),(2,3,0,1),(3,2,1,0))
        self.__mulL__ = ((0,0,0,0),(0,1,2,3),(0,2,3,1),(0,3,1,2))
    def __add__(self, x):
        return self.__addL__[self.number][x]
    def __mul__(self, x):
        return self.__mulL__[self.number][x]
    def __sub__(self, x):
        return self.__addL__[self.number][x]
    def __div__(self, x):
        return self.__mulL__[self.number][x]
    def __repr__(self):
        return str(self.number)

a = numpy.array([GF4(numpy.random.randint(4)) for i in range(18)]).reshape(3,6)
b = numpy.array([GF4(numpy.random.randint(4)) for i in range(18)]).reshape(3,6)

""""
In [261]: a
Out[261]: 
array([[1, 1, 2, 0, 2, 1],
       [0, 3, 1, 0, 3, 1],
       [1, 2, 0, 3, …

我想在有限域的点上使用python插值多项式，并在该域中获取具有系数的多项式。当前，我正在尝试使用SymPy并专门进行插值（来自sympy.polys.polyfuncs），但是我不知道如何强制在特定gf中进行插值。如果没有，可以使用其他模块来完成吗？

编辑：我对Python实现/库感兴趣。

我正在撰写关于为后量子安全签名编写的代码的硕士论文（计算机科学）。整个事情都可以在这里找到，但在这里并不重要。在我的论文中，我试图解释一个“简单”的函数，它根本不是那么简单。

该函数测试，如果一个变量在伽罗瓦域GF(16) 中是非零的。（这里的GF(16)可以理解为4位无符号整数）。该函数如下所示：

static inline uint8_t gf16_is_nonzero(uint8_t a) {
    unsigned a4 = a & 0xf; // mask lowest 4 bits of a
    unsigned r = 0u - a4;  // set 4 high bits if a is nonzero
    r >>= 4;               // right-shift high bits into low bits
    return r & 1;          // return lowest bit
}

我明白它是如何工作的，但我不明白为什么这个功能需要这么复杂。这有什么好的理由吗？很好的理由可能是性能或安全性（例如针对定时攻击的安全性）的好处。因为如果没有这样的好处，那么以简单的方式编写该函数不是更聪明，例如：

static inline uint8_t gf16_is_nonzero(uint8_t a) {
    return (a & 15) != 0;
} …