GF (2) 유한 필드의 파이썬 곱셈 역함계

Question

이 두 함수는 확장 유클리드 알고리즘을 수행 한 다음 곱셈 역함수를 찾습니다. 순서는 옳은 것처럼 보이지만, 시드니의 http://magma.maths.usyd.edu.au/calc/에서이 툴에 대해 기대하고있는 것과 같이 돌아 오지 않을 것입니다. 그리고 이것은 GF (2) 유한 필드에서 수행 되었기 때문에, 번역 할 핵심 단계가 빠져 있다고 생각합니다. 10 진수에서이 필드로 이동합니다.

이것은베이스 10에서 테스트되고 작업되었지만 이진 계수가있는 다항식을 취하는 것은 여기서 불가능할 수 있습니다. 그래서 내 질문은 파이썬의 어떤 부분이 GF (2)에서이 작업을 수행 할 수있는 기수 10에서 수행 할 수있는 기능을 수행하지 않을 수있는 // floor와 같은이 알고리즘에 잘못 적용되는 부분입니다.

이 도구는 위의이 같은 테스트 할 수 있습니다 :

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" 

Answer 1

모든 전환이 int("{0:b}".format(x))에 있기 때문에이 함수는 기본 -10으로 테스트했을 때 작동했습니다. x에 대한 효과 없음 :

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

파이썬의 Number 객체는 모두 base-10입니다. 숫자를 이진 문자열로 변환 한 다음 다시 정수로 변환해도 아무런 효과가 없습니다. 다음은 a 및 b에서 base-10 int로 사용할 수있는 함수의 대체 버전을 찾고 이진수로 반환합니다. bin() 함수를 제거하여 밑이 10 인 숫자를 반환하거나 lambda x: int("%d".format(x))과 같은 것을 사용하여 함수의 첫 번째 줄에서 a 및 b을 이진수에서 십진수로 변환 할 수 있습니다.

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 

,이 같은 함수에서 람다를 사용하지 않는 말했다 모든 - 당신 만의 인터페이스에서 바이너리로 /에서 변환 할 수있는 모두 바이너리를 사용하지 않도록하는 프로그램을 작성 좋을 것 소스 데이터가있는 프로그램.