6

これらの 2 つの関数は、拡張ユークリッド アルゴリズムを実行してから、乗法逆数を見つけます。順序は正しいように見えますが、シドニー大学http://magma.maths.usyd.edu.au/calc/からのこのツールによると、これは GF(2 ) 有限体、基数 10 からこの体に変換するいくつかの重要なステップが欠落していると思います。

これは基数 10 でテストされ、動作しましたが、ここではバイナリ係数を持つ多項式を取り込むことができない場合があります。したがって、私の質問は、Python のどの部分がこのアルゴリズムに誤って適用されているのかということです。たとえば、// floor など、GF(2) でこれを行うために、関数が基数 10 で実行できたものから実行できない可能性があります。

上記のツールは、次のようにテストできます。

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;

機能:

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

私はこのような多項式でテストしてきましたが、もちろんバイナリ形式です:

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

1 に答える 1

4

すべての変換int("{0:b}".format(x))が x に影響を与えないため、base-10 でテストした場合、関数は機能しました。

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

Python の Number オブジェクトはすべて base-10 です。数値をバイナリ文字列に変換してから整数に戻しても効果はありません。aこれは、b基数 10 の int で動作し、バイナリで返す関数の代替バージョンです。関数を削除しbin()て基数 10 の数値を返すか、関数の最初の行で 2 進数から 10 進数に変換lambda x: int("%d".format(x))するようなものを使用できます。ab

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

とは言っても、このような関数ではラムダを使用しないでください。バイナリを完全に使用しないようにプログラムを作成することをお勧めします。これは、プログラムとソース データのインターフェイスでバイナリとの間で変換するだけで実行できます。

于 2013-07-30T20:48:00.220 に答える