求逆元
inv=inverse_mod(30,1373)print(30*inv%1373) #1
扩展欧几里得算法
d,u,v=xgcd(20,30)print("d:{0} u:{1} v:{2}".format(d,u,v))#d:10 u:-1 v:1
孙子定理(中国剩余定理)
计算参考：
/destiny1507/article/details/81751168
def chinese_remainder(modulus, remainders):Sum = 0prod = reduce(lambda a, b: a*b, modulus)for m_i, r_i in zip(modulus, remainders):p = prod // m_iSum += r_i * (inverse_mod(p,m_i)*p)return Sum % prodchinese_remainder([3,5,7],[2,3,2]) #23
求离散对数
2x2^x2x ≡≡≡ 131313 modmodmod 232323
x=discrete_log(mod(13,23),mod(2,23))#或discrete_log(13,mod(2,23))print(x)
取模求根
x2x^2x2 ≡≡≡ 555 modmodmod 414141
x=mod(5,41)r=x.nth_root(22)
欧拉函数
print(euler_phi(71)) #70
输出表达式近似值
result=pi^2result.numerical_approx()
素数分布（Pi(x)）
π(x)x/In(x)\frac{\pi(x)}{x/In(x)}x/In(x)π(x)
result=prime_pi(1000)/(1000/log(1000))result.numerical_approx() #1.16050288686900
创建整数域中的椭圆曲线
y2=x3+a4x+a6y^2=x^3+a_4x+a_6y2=x3+a4x+a6
a4=2;a6=3;F=GF(7);E=EllipticCurve(F,[0,0,0,a4,a6])print(E.cardinality()) #6print(E.points()) #[(0 : 1 : 0), (2 : 1 : 1), (2 : 6 : 1), (3 : 1 : 1), (3 : 6 : 1), (6 : 0 : 1)]
创建点
point1=E([2,1])point2=E([3,6])print(point1+point2)#(6 : 0 : 1)print(point1-point2)#(2 : 6 : 1)
