Итак, в настоящее время я пытаюсь реализовать конечные поля, используя только полиномы. Так что я не хочу работать с двоичными числами, используя такие операции, как 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
Результат будет таким же, как код работает в своем текущем состоянии, но мне нужно, чтобы он работал по-другому, прежде чем я смогу двигаться дальше.
