# Sage 相关库的使用

# 基本环和域

	ZZ #整数环
	QQ #有理数环
	RR #实数域
	CC #复数域

	Zn = IntegerModRing(n)

	F.<x>=PolyomialRing(ZZ) #定义在整数环上的多项式环，多项式的变量定义为 x
	P.<x, y> = PolynomialRing(Zmod(p)) #多变量
	# F 是多项式环的名字，自定义
	# x 是多项式环变量的名字，自定义



	G=GF(p) # 定义伽罗瓦域，阶是 p，并且 p 要是一个素数或者一个素数的幂次
	x=G(5) #定义在有限域 GF (p) 上的数 5，可以把 G 看做一个类型
	ZN=Zmod(N) #一般有限环

	#后续使用时，如果我们想要一个元素 x 在某个环或域上计算，直接 ZZ (x),QQ (x),ZN (X) 这样

	x, y = var('x, y') #定义形式变量，可以利用这个来得到带变量的方程

	d=gcd(a,b) #求 a,b 的 gcd
	lcm(a,b ) #求 a,b 的 lcm

	d,u,v=xgcd(a,b) #扩展欧几里得，返回三个参数，满足 au+bv=d ,gcd (a,b)=d

	y=inverse_mod(x,p) #返回 x 在模 p 下的逆元 y

	p=random_prime(a,b) #返回 [a,b) 之间的随机素数

	is_prime(p) #判断是否是素数

	nth_prime(n) #返回第 n 个素数

	next_prime(p) #素数 p 的下一个素数

	pow(x,y,p) #计算 x^y mod p

	euler_phi(n) #计算欧拉函数

	crt([a1,a2,...,an],[m1,m2,...,m3]) #中国剩余定义，其中 x=ai mod mi

	factorial(x) #求 x 的阶乘

	factor(x) #素数分解

	continued_fraction(n) #计算连分数

	euler_phi(n) #n 的欧拉函数
	binomial(n,m) #组合数
	moebius(n) #莫比乌斯函数
	Partitions(n).list() #n 的正整数划分
	divisors(x) #返回一个列表，包含 x 的所有因子
	prime_divisors #返回一个列表，包含 x 的所有素因子

	discrete_log(a,base,ord,operation) #离散对数
	discrete_log_rho(a,base,ord,operation) #Pollard-Rho 算法
	bsgs(base,a,bounds,operation) #BSGS 求离散对数

	#有限域开根，比如整数域上开根
	ZZ(7^64).nth_root(64) #得到 7
	ZN(x).nth_root(y,all=True) #得到所有满足 x=z^y mod N 的 z

	A=Matrix(ZZ,[[1,2,3],[1,2,3],[1,2,3]]) #声明一个在 ZZ 上的三行三列的矩阵 A
	A=matrix(Zmod(7),[[1,2,3],[1,2,3],[1,2,3]]) #声明一个在 Zmod (7) 上的三行三列的矩阵 A
	A=matrix(Zmod(7),n,m) #定义在 Zmod (7) 上大小为 nxm 的矩阵，并且初始值均为 0
	I=matrix.identity(n) #大小为 nxn 的单位矩阵
	# Matrix 和 matrix 一样
	print(A[i,j]) #取 A 第 i 行第 j 列的元素
	A.T #A 的矩阵转置
	A^(-1) #A 的逆矩阵
	A.rank() #A 的秩
	A.nrows() #将返回矩阵行数
	A.ncols() #将返回矩阵列数
	A.det() #A 的特征值
	A.eigenvalues() #特征值
	M.eigenvectors_right() #特诊向量
	A+B #矩阵加法
	A*B #矩阵乘法

	M=block_matrix([[A,B],[C,D]]) #定义分块矩阵，其中 A,B,C,D 都是在一个环或域上的矩阵

	v=vector(Zmod(7),[1,2,3,4,5,6,7,8,9]) #声明一个在 Zmod (7) 上的向量
	print(v[i]) #去 v 的第 i 个元素

	X=A.solve_right(B) #解线性方程组形如 AX=B ,X 在右边
	X=A.solve_left(B) #XA=B，X 在左边

	#矩阵空间 Matrix spaces
	M = MatrixSpace(QQ,n,m) #定义在有理数域上的 nxm 维矩阵空间
	B = M.basis()

	R = PolynomialRing(QQ, 't') #定义在有理数域上的多项式环，且变量为 t
	R.<t> = PolynomialRing(QQ)
	t=R.0 #R.0 就是这个多项式环上的未知量

	#多变量定义
	PolynomialRing(GF(5), 3, 'xyz')
	z = GF(5)['z0, z1, z2'].gens() #z=(z0, z1, z2)

	R, (x, y) = PolynomialRing(RationalField(), 2, 'xy').objgens()
	f = (x^3 + 2y^2x)^2
	g = x^2*y^2
	f.gcd(g) #求公因式

	lattice = IntegerLattice(A, lll_reduce=True) #定义一个格，其中 A 是一个内积空间矩阵，并且自动计算 lll_reduce (格规约)

	M.LLL() # LLL 算法

	#Babai 算法：需要手动实现，一般如下
	#输入格的基 basis 和目标向量 v
	def approximate_closest_vector(basis, v):
	"""Returns an approximate CVP solution using Babai's nearest plane algorithm.
	"""
	BL = basis.LLL()
	# 施密特正交化基
	G, _ = BL.gram_schmidt()
	_, n = BL.dimensions()
	small = vector(ZZ, v)
	for i in reversed(range(n)):
	c = QQ(small * G[i]) / QQ(G[i] * G[i])
	c = c.round()
	small -= BL[i] * c
	return (v - small).coefficients()