如何在F_{2^8}中进行加法和乘法

Question

我想在F_{2^8}中进行加法和乘法

我目前有这段代码似乎适用于加法但不适用于乘法；问题似乎是，当我对 100011011（代表 x^8 + x^4 + x^3 + x + 1）取模时，它似乎并没有这样做。另一个想法是使用 numpy.polynomial 但它不那么直观。

def toBinary(self, n):
    return ''.join(str(1 & int(n) >> i) for i in range(8)[::-1])

def add(self, x, y):
    """
     "10111001" + "10010100" = "00101101"
    """

    if len(x)<8:
        self.add('0'+x,y)
    elif len(y)<8:
        self.add(x,'0'+y)

    try:
        a = int(x,2); b = int(y,2)
        z = int(x)+int(y)
        s = ''
    
        for i in str(z):
            if int(i)%2 == 0:
                s+='0'
            else:
                s+='1'
    except:
        return '00000000'

    return s
    
def multiply(self, x, y):
    """
    "10111001" * "10010100" = "10110010"
    """
    if len(x)<8:
        self.multiply('0'+x,y)
    elif len(y)<8:
        self.multiply(x,'0'+y)

    result = '00000000'

    result = '00000000'
    while y!= '00000000' :
        print(f'x:{x},y:{y},result:{result}')
        if int(y[-1]) == 1 :
            result = self.add(result ,x)
            y = self.add(y, '00000001')
        x = self.add(self.toBinary(int(x,2)<<1),'100011011')
        y = self.toBinary(int(y,2)>>1) #b = self.multiply(b,inverse('00000010'))
    return result

Answer 1

Python 加法（与减法相同）、乘法、除法和逆运算的示例。假设输入参数是 8 位值，并且没有检查除以 0.

def add(x, y):                  # add is xor
    return x^y

def sub(x, y):                  # sub is xor
    return x^y

def mpy(x, y):                  # mpy two 8 bit values
    p = 0b100011011             # mpy modulo x^8+x^4+x^3+x+1
    m = 0                       # m will be product
    for i in range(8):
        m = m << 1
        if m & 0b100000000:
            m = m ^ p
        if y & 0b010000000:
            m = m ^ x
        y = y << 1
    return m

def div(x, y):                   # divide using inverse
    return mpy(x, inv(y))        #  (no check for y = 0)

def inv(x):                      # x^254 = 1/x
    p=mpy(x,x)                   # p = x^2
    x=mpy(p,p)                   # x = x^4
    p=mpy(p,x)                   # p = x^(2+4)
    x=mpy(x,x)                   # x = x^8
    p=mpy(p,x)                   # p = x^(2+4+8)
    x=mpy(x,x)                   # x = x^16
    p=mpy(p,x)                   # p = x^(2+4+8+16)
    x=mpy(x,x)                   # x = x^32
    p=mpy(p,x)                   # p = x^(2+4+8+16+32)
    x=mpy(x,x)                   # x = x^64
    p=mpy(p,x)                   # p = x^(2+4+8+16+32+64)
    x=mpy(x,x)                   # x = x^128
    p=mpy(p,x)                   # p = x^(2+4+8+16+32+64+128)
    return p

print hex(add(0b01010101, 0b10101010))      # returns 0xff
print hex(mpy(0b01010101, 0b10101010))      # returns 0x59
print hex(div(0b01011001, 0b10101010))      # returns 0x55

对于GF(2^n)，加法和减法都是异或。这意味着乘法是无进位的，除法是无借位的。 X86 有一个用于 XMM 寄存器的无进位乘法，PCLMULQDQ。除以常数可以通过无进位乘以 2^64 / 常数并使用乘积的高 64 位来完成。逆常数是使用无借位除法循环生成的。

原因是 GF(2^n) 个元素是具有 1 位系数的多项式，（系数是 GF(2) 的元素）。

对于GF(2^8)，生成指数和对数表会更简单。示例 C 代码：

#define POLY (0x11b)
/* all non-zero elements are powers of 3 for POLY == 0x11b */
typedef unsigned char BYTE;
/* ... */
static BYTE exp2[512];
static BYTE log2[256];
/* ... */
static void Tbli()
{
int i;
int b;
    b = 0x01;                   /* init exp2 table */
    for(i = 0; i < 512; i++){
        exp2[i] = (BYTE)b;
        b = (b << 1) ^ b;       /*  powers of 3 */
        if(b & 0x100)
            b ^= POLY;
    }

    log2[0] = 0xff;             /* init log2 table */
    for(i = 0; i < 255; i++)
        log2[exp2[i]] = (BYTE)i;
}
/* ... */
static BYTE GFMpy(BYTE m0, BYTE m1) /* multiply */
{
    if(0 == m0 || 0 == m1)
        return(0);
    return(exp2[log2[m0] + log2[m1]]);
}
/* ... */
static BYTE GFDiv(BYTE m0, BYTE m1) /* divide */
{
    if(0 == m0)
        return(0);
    return(exp2[log2[m0] + 255 - log2[m1]]);
}

Answer 2

我创建了一个 Python 包 galois，它在有限域上扩展了 NumPy 数组。使用 GF(2^8) 非常简单，请参阅下面的示例。

In [1]: import galois

In [2]: GF = galois.GF(2**8, irreducible_poly="x^8 + x^4 + x^3 + x + 1")

In [3]: print(GF.properties)
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: x^8 + x^4 + x^3 + x + 1
  is_primitive_poly: False
  primitive_element: x + 1

# Your original values from your example
In [4]: a = GF(0b10111001); a
Out[4]: GF(185, order=2^8)

In [5]: b = GF(0b10010100); b
Out[5]: GF(148, order=2^8)

In [6]: c = a * b; c
Out[6]: GF(178, order=2^8)

# You can display the result as a polynomial over GF(2)
In [7]: GF.display("poly");

# This matches 0b10110010
In [8]: c
Out[8]: GF(x^7 + x^5 + x^4 + x, order=2^8)

您也可以使用数组。

In [12]: a = GF([1, 2, 3, 4]); a
Out[12]: GF([1, 2, 3, 4], order=2^8)

In [13]: b = GF([100, 110, 120, 130]); b
Out[13]: GF([100, 110, 120, 130], order=2^8)

In [14]: a * b
Out[14]: GF([100, 220, 136,  62], order=2^8)

它是开源的，因此您可以查看所有代码。这是 GF(2^m) 中的乘法片段。所有的输入都是整数。以下是使用具有特征 2 的整数执行“多项式乘法”的方法。

    def _multiply_calculate(a, b, CHARACTERISTIC, DEGREE, IRREDUCIBLE_POLY):
        """
        a in GF(2^m), can be represented as a degree m-1 polynomial a(x) in GF(2)[x]
        b in GF(2^m), can be represented as a degree m-1 polynomial b(x) in GF(2)[x]
        p(x) in GF(2)[x] with degree m is the irreducible polynomial of GF(2^m)

        a * b = c
            = (a(x) * b(x)) % p(x) in GF(2)
            = c(x)
            = c
        """
        ORDER = CHARACTERISTIC**DEGREE

        # Re-order operands such that a > b so the while loop has less loops
        if b > a:
            a, b = b, a

        c = 0
        while b > 0:
            if b & 0b1:
                c ^= a  # Add a(x) to c(x)

            b >>= 1  # Divide b(x) by x
            a <<= 1  # Multiply a(x) by x
            if a >= ORDER:
                a ^= IRREDUCIBLE_POLY  # Compute a(x) % p(x)

        return c

同样的例子运行如下。

In [72]: _multiply_calculate(0b10111001, 0b10010100, 2, 8, 0b100011011)
Out[72]: 178

In [73]: bin(_multiply_calculate(0b10111001, 0b10010100, 2, 8, 0b100011011))
Out[73]: '0b10110010'

如何在F_{2^8}中进行加法和乘法

How to perform addition and multiplication in F_{2^8}

python

finite-field