Python nghịch đảo nhân trong GF (2) lĩnh vực hữu hạn

Question

Hai chức năng này thực hiện thuật toán Euclide mở rộng, và sau đó tìm nghịch đảo nhân. Đơn hàng có vẻ đúng, nhưng nó không quay trở lại với những gì tôi mong đợi theo công cụ này từ U của Sydney http://magma.maths.usyd.edu.au/calc/ và vì điều này được thực hiện trong lĩnh vực hữu hạn GF (2), tôi nghĩ rằng tôi đang thiếu một số bước quan trọng mà dịch từ cơ số 10 vào trường này.

Điều này đã được thử nghiệm và làm việc trên cơ sở 10, nhưng việc sử dụng đa thức với hệ số nhị phân có thể không thực hiện được ở đây. Vì vậy, câu hỏi của tôi là những gì của Python tôi không chính xác áp dụng cho thuật toán này, chẳng hạn như // sàn, có thể không thực hiện từ những gì các chức năng có khả năng trong cơ sở 10 để có thể làm điều này trong GF (2).

Công cụ trên có thể được thử nghiệm như thế này:

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; 

Các chức năng:

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 

tôi đã thử nghiệm với đa thức như thế này nhưng ở dạng nhị phân của khóa học:

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

Answer 1

Hàm này hoạt động khi được thử nghiệm với base-10 vì tất cả các chuyển đổi của bạn int("{0:b}".format(x)) có không ảnh hưởng đến x:

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

Đối tượng số trong python là tất cả cơ sở-10. Chuyển đổi số của bạn thành chuỗi nhị phân, sau đó quay lại số nguyên không có hiệu lực. Dưới đây là một phiên bản thay thế của hàm của bạn nên hoạt động trên a và b làm base-10 ints và trả về chúng theo dạng nhị phân. Bạn có thể xóa hàm bin() để trả về các số trong cơ sở 10 hoặc sử dụng một số như lambda x: int("%d".format(x)) để chuyển đổi a và b từ nhị phân sang thập phân trong dòng đầu tiên của hàm.

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 

Tất cả những gì đã nói, không sử dụng lambdas trong một chức năng như thế này - Tôi muốn đề nghị bằng văn bản chương trình của bạn để tránh sử dụng nhị phân hoàn toàn, mà bạn có thể làm bằng cách chỉ chuyển đổi từ/đến nhị phân tại giao diện của chương trình của bạn với dữ liệu nguồn.