Pikonowa odwrotność multiplikatywna w GF (2) skończone pole

Question

Te 2 funkcje wykonują Rozszerzony algorytm Euklidesowy, a następnie znajdują odwrotność multiplikatywną. Kolejność wydaje się właściwa, ale nie powraca z tym, czego się spodziewam, zgodnie z tym narzędziem z U of Sydney http://magma.maths.usyd.edu.au/calc/, a ponieważ jest to zrobione w skończonym polu GF (2), myślę, że brakuje mi jakiegoś kluczowego kroku, który tłumaczy z bazy 10 do tego pola.

Zostało to przetestowane i działało na podstawie 10, ale przyjmowanie wielomianów o współczynnikach binarnych może nie być tutaj możliwe. Tak więc moje pytanie brzmi, jakie części Pythona niepoprawnie stosuję do tego algorytmu, na przykład // floor, które mogą nie przenosić tego, co funkcja była w stanie wykonać w bazie 10, aby móc to zrobić w GF (2).

Narzędzie powyżej mogą być testowane tak:

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; 

funkcjami:

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 of 101010111... form 
    a,mod = prepBinary(a,mod) 
    bitsa = int("{0:b}".format(a),2); bitsb = int("{0:b}".format(mod),2) 
    #return bitsa,bitsb,type(bitsa),type(bitsb),a,mod,type(a),type(mod) 
    gcd,s,t = extendedEuclideanGF2(a,mod); s = int("{0:b}".format(s)) 
    initmi = s%mod; mi = int("{0:b}".format(initmi)) 
    print ("M Inverse %d * %d mod %d = 1"%(a,initmi,mod)) 
    if gcd !=1: return mi,False 
    return mi # returns modular inverse of a,mod 

Byłem testowania z wielomianów takich jak ten, ale w postaci binarnej przedmiotu:

p = "x**13 + x**1 + x**0" 
q = "x**12 + x**1" 

Answer 1

Funkcja działała, gdy testowano z base-10, ponieważ wszystkie konwersje int("{0:b}".format(x)) mają nie ma wpływu na X:

37 == int("{0:b}".format(37), 2) # >>> True 

Obiekty numeryczne w Pythonie są wszystkie base-10. Konwersja liczb na ciągi binarne, a następnie powrót do liczb całkowitych nie daje żadnego efektu. Oto alternatywna wersja twojej funkcji, która powinna działać na a i b jako wtyczki base-10 i zwracać je w postaci binarnej. Możesz usunąć funkcję bin(), aby zwrócić liczby w bazie-10, lub użyć czegoś podobnego do lambda x: int("%d".format(x)), aby przekształcić a i b z binarnego na dziesiętny w pierwszym wierszu funkcji.

def extendedEuclideanGF2(a, b): # extended euclidean. a,b are values 10110011... in   integer form 
    inita, initb = a, b # if a and b are given as base-10 ints 
    x, prevx = 0, 1 
    y, prevy = 1, 0 
    while b != 0: 
     q = a//b 
     a, b = b, a%b 
     x, prevx = prevx - q*x, x 
     y, prevy = prevy - q*y, y 
    print("Euclidean %d * %d + %d * %d = %d" % (inita, prevx, initb, prevy, a)) 
    i2b = lambda n: int("{0:b}".format(n)) # convert decimal number to a binary value in a decimal number 
    return i2b(a), i2b(prevx), i2b(prevy) # returns gcd of (a,b), and factors s and t 

Wszystko, co powiedział, nie używaj lambdy w funkcji takich jak ten - Sugeruję pisanie programu, aby uniknąć stosując binarny ogóle, co można zrobić tylko konwersja z/do pliku binarnego w interfejsie twój program z danymi źródłowymi.