直接处理多项式而不是二进制数时，是否有更好的方法在有限域中进行取模？

Question

所以目前我正在尝试仅使用多项式来实现有限域。就像，我不想使用 AND 等操作对二进制数进行操作。相反，我想用多项式来完成整个事情。

我在这方面已经走得很远了，乘法（这里没有必要包括在内）、加法等都在工作。问题是当我对素数多项式取模时，我必须将多项式转换为整数以比较它们的大小。我想避免这样做，有没有办法解决这个问题并以不同的方式进行取模？

import collections
from math import log
import itertools

def XorAsPolynomial(a,b):  #basically, we merge the terms of 2 polynomials together, and if a term repeats an even number of times, remove all of them, and if its an odd number of times, remove all but 1. this is the same as xor
    c = a+b

    counter=collections.Counter(c)
    Values = list(counter.values())
    Keys = list(counter.keys())

    for i in range(len(Values)):
            if (Values[i])%2 == 0:
                for q in range(Values[i]):
                    del c[c.index(Keys[i])]
            if (Values[i])%2 == 1:
                for q in range(Values[i]-1):
                    del c[c.index(Keys[i])]
    return c

def MultAsPolys(a,b,k):
    c = []
    d = []
    if len(a) < len(b):
        a,b = b,a
    for i in range(len(b)):
        for s in range(len(a)):
                c.append((a[s]+b[i])) #So far we have done multiplication without collecting any like terms. This is important




    counter=collections.Counter(c)
    Values = list(counter.values())
    Keys = list(counter.keys())

    for i in range(len(Values)): #basically, now we pretend we collected the terms, but modulo them by 2. So "3x" becomes "x", and "2x" becomes 0
            if (Values[i])%2 == 0: #of course, we never did actually collect the terms in the list since this wouldnt keep data about how many "x"s we have.
                for q in range(Values[i]): # So instead what we have done is, we have counted how many of each term we have in the list and modulo'd that number by 2,
                    del c[c.index(Keys[i])] # we have then just removed all terms like it in cases where there was an even number of them, and we have removed all but 1 term when there was an odd number
            if (Values[i])%2 == 1:
                for q in range(Values[i]-1):
                    del c[c.index(Keys[i])]


    return c

def ModuloAsPolynomial(t,b): #this is the modulo operation, the focus of the question
    for i in range(len(b)):
        b[i] = b[i] + 64

    for i in range(65):
        tt = XorAsPolynomial(t , b)

        if (PolyToInt(tt)) < (PolyToInt(t)): #THIS is the line in particular thats an issue. It works, but I want to be able to do this line without having the "IntToPoly" part. This is because the next part of this project will involve things that will break this code if i do it like this.
            t = tt #basically, instead of seeing if tt is less than t, i need another way of doing it that keeps both as polynomials

        for i in range(len(b)):
            b[i] = b[i] - 1
    return t

def IntToPoly(bInt): #turns numbers into polynomial lists
    exp = 0
    poly = []
    while bInt:
        if bInt & 1:
            poly.append(exp)
        exp += 1
        bInt >>= 1
    return poly[::-1]

def PolyToInt(a): #turns polynomial lists back into numbers
    k = 0
    for i in range(len(a)):
        k = k+(2**a[i])
    #k = round(k.real,8) + (round(k.imag,8)*1j) #ignore that
    return k

def Test():

    PrimePolynomial = [8, 6, 5, 3, 0] #this is our prime polynomial. In decimal form it is 361

    TenSquared = [12, 10, 4] #this is the number we are doing the modulo on. In decimal form its 5136, which is 10^2 using our multiplication method outlined in the function ModuloAsPolynomial

    output = ModuloAsPolynomial(TenSquared,PrimePolynomial) #the output is [6, 4, 1], which is 82 as a decimal number. This is the intended output

#Sorry if their are any spelling errors here. I am dyslexic and this has no spell check

结果将与代码在其当前状态下工作的结果相同，但我需要它以另一种方式工作，然后才能继续。

Answer 1

取模函数只是除法，不保留商，但保留余数，source_polynomial（被除数）%field_polynomial（除数）。我不认为需要转换为 int 进行比较。我不知道 python，但逻辑应该是这样的（假设指数始终保持降序，从大到小）。 xor 应该只是合并两组指数（保持它们按降序排列），除了重复的指数将被删除而不是复制（因为 xor 会将这些指数的 1 位系数归零）。

while(true){
    e = dividend[0] - divisor[0]       // e = exponent of dividend - exponent of divisor
    if(e < 0)break;                    // break if dividend < divisor
    temp = divisor;
    for(i = 0; i < len(divisor); i++)  // create "shifted" copy of divisor
        temp[i] += e;
    dividend = dividend xor temp;      // "subtract" temp from dividend
                                       // this reduces size of dividend
    if(len(dividend) == 0)break;       // break if dividend == 0
}

直接处理多项式而不是二进制数时，是否有更好的方法在有限域中进行取模？

Is there a better way to do modulo in a finite field when directly working on polynomials rather than binary numbers?

python

modular-arithmetic

finite-field