GF (2) sonlu alanında Python çarpımsal tersi

Question

Bu 2 işlev, Genişletilmiş Öklid Algoritmasını gerçekleştirir ve sonra çarpımsal tersini bulur. Sipariş doğru görünüyor, ama bu araç için U Sydney http://magma.maths.usyd.edu.au/calc/ dan beklediğim ile geri gelmiyor ve bu GF (2) sonlu alanda yapılır beri, ben çevirmek bazı önemli adım eksik düşünüyorum 10'dan bu alana. Bu, test edildi ve temel 10 üzerinde çalışıldı, ancak ikili katsayıları olan polinomları almak burada mümkün olmayabilirdi. Bu yüzden benim sorum, Python'un parçalarının, // tabanı gibi, fonksiyonun temel 10'da ne yapabildiğini taşımayan // zemin gibi, bu algoritmaya yanlış uygulayabileceğidir (2).

aracı üzerinde gibi test edilebilir:

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; 

fonksiyonları:

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 

Böyle polinomlar ama tabii ikili biçimde test ettik:

Answer 1

int("{0:b}".format(x)) numaralı dönüşümlerinizin tümü baz-10 ile test edildiğinde işe yaradı. xl üzerinde etkisi yok:

Pitondaki sayı nesnelerinin hepsi taban-10'dur. Sayılarınızı ikili dizelere dönüştürme, daha sonra tamsayılara geri dönüşü yoktur. İşte fonksiyonunuzun alternatif bir versiyonu a ve b temel-10 ints olarak çalışmalı ve bunları ikili olarak döndürmelisiniz. Sayıları base-10'da döndürmek için bin() işlevini kaldırabilir veya a ve b dönüştürmelerini lambda x: int("%d".format(x)) gibi bir işlevi kullanarak, işlevin ilk satırında onluktan ikiliye dönüştürebilirsiniz.

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 

, böyle bir işlev lambdas kullanmayın söyledi Hepsi - Ben sadece ara yüzünde ikili/dan dönüştürerek yapabilirsiniz tamamen ikili kullanmaktan kaçının programınızı, yazma öneririm Programınızı kaynak verilerle.