जीएफ (2) परिमित क्षेत्र में पायथन गुणात्मक उलटा

Question

ये 2 फ़ंक्शंस विस्तारित यूक्लिडियन एल्गोरिदम निष्पादित करते हैं, और फिर गुणात्मक उलटा पाते हैं। आदेश सही लगता है, लेकिन यह सिडनी http://magma.maths.usyd.edu.au/calc/ से इस उपकरण के अनुसार मैं जो उम्मीद कर रहा हूं उसके साथ वापस नहीं आ रहा है और चूंकि यह जीएफ (2) परिमित क्षेत्र में किया जाता है, मुझे लगता है कि मुझे कुछ महत्वपूर्ण कदम याद आ रहे हैं जो अनुवाद करते हैं आधार 10 से इस क्षेत्र में।

यह परीक्षण 10 पर परीक्षण और काम किया गया था, लेकिन यहां बाइनरी गुणांक वाले बहुपदों को लेना संभव नहीं हो सकता है। तो मेरा सवाल यह है कि पाइथन के कुछ हिस्सों में मैं इस एल्गोरिदम के लिए गलत तरीके से आवेदन कर रहा हूं, जैसे कि // फर्श, जो कि जीएफ (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" 

Answer 1

फ़ंक्शन -10 के साथ परीक्षण करते समय फ़ंक्शन काम करता था क्योंकि आपके सभी रूपांतरण int("{0:b}".format(x)) हैं x:

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

पायथन में संख्या ऑब्जेक्ट्स सभी आधार -10 हैं। अपनी संख्या को बाइनरी स्ट्रिंग में कनवर्ट करना, फिर पूर्णांक पर वापस कोई प्रभाव नहीं पड़ता है। यहां आपके फ़ंक्शन का एक वैकल्पिक संस्करण है जो a और b पर बेस -10 इनट्स के रूप में काम करना चाहिए और उन्हें बाइनरी में वापस करना चाहिए। आप बेस -10 में संख्याओं को वापस करने के लिए bin() फ़ंक्शन को हटा सकते हैं, या a और b को फ़िन की पहली पंक्ति में बाइनरी से दशमलव में कनवर्ट करने के लिए lambda x: int("%d".format(x)) जैसे कुछ का उपयोग कर सकते हैं। मैं पूरी तरह द्विआधारी का उपयोग कर से बचने के लिए अपने कार्यक्रम है, जो आप केवल के इंटरफेस पर द्विआधारी से/परिवर्तित करके ऐसा कर सकते हैं लिखने के सुझाव देंगे -

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 

सब ने कहा, इस तरह एक समारोह में lambdas का उपयोग नहीं करते

स्रोत डेटा के साथ आपका कार्यक्रम।