2

所以目前我正在尝试仅使用多项式来实现有限域。因此，我不想使用 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

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

4

1 回答 1

1

The modulo function is just a divide that doesn't keep the quotient, but does keep the remainder, source_polynomial (dividend) % field_polynomial (divisor). I don't see the need to converting to int for compare. I don't know python, but the logic would be something like this (assuming that exponents are always kept in decreasing order, largest to smallest). The xor should just merge the two sets of exponents (keeping them in descending order), except that duplicate exponents would be dropped instead of copied (since xor would zero the 1 bit coefficient for these exponents).

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
}
于 2019-02-07T10:06:27.013 回答