GF（2）有限域中的Python乘法逆

Question

这两个函数执行扩展的欧几里德算法，然后求乘法逆。顺序似乎是正确的，但它并没有返回我所期望的，根据这个工具，从悉尼的U http://magma.maths.usyd.edu.au/calc/，而且由于这是在GF（2）有限域中完成的，我想我遗漏了一些关键步骤，从基数10转换成这个域。在

这一点已经过测试，并以10为基数进行了工作，但是在这里不可能接受具有二元系数的多项式。所以我的问题是，Python的哪些部分不正确地应用到这个算法中，比如//floor，它们可能没有从函数在基10中所能实现的功能（GF（2）中实现）。在

上面的工具可以这样测试：

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;

功能：

^{pr2}$

我一直在测试这样的多项式，当然是二进制形式：

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

python中的Number对象都是以10为基数的。将数字转换为二进制字符串，然后再转换回整数没有效果。这里是您的函数的另一个版本，它应该以a和{}作为基数10整数，并以二进制形式返回它们。您可以删除bin()函数以返回以10为基数的数字，或者使用类似于lambda x: int("%d".format(x))的方法将a和{}从二进制转换为十进制。在

^{pr2}$

尽管如此，不要在这样的函数中使用lambdas—我建议您编写程序时避免完全使用二进制，这只需在程序与源数据的接口处从/转换为二进制即可。在