|
|
import random
|
|
|
import sympy as sp
|
|
|
import numpy as np
|
|
|
|
|
|
def find_irreducible_polynomial(p, n):
|
|
|
"""在F_p上寻找一个n次不可约多项式"""
|
|
|
# 生成所有可能的n次多项式（首项系数为1）
|
|
|
max_coeff = p ** n
|
|
|
for i in range(p ** n):
|
|
|
coeffs = []
|
|
|
num = i
|
|
|
for j in range(n):
|
|
|
coeffs.append(num % p)
|
|
|
num //= p
|
|
|
|
|
|
# 首项系数设为1
|
|
|
coeffs.append(1)
|
|
|
coeffs = coeffs[::-1] # 反转，使高次在前
|
|
|
|
|
|
# 创建多项式
|
|
|
poly = sp.Poly(coeffs, sp.Symbol('x'), modulus=p)
|
|
|
|
|
|
# 检查是否不可约
|
|
|
if sp.ntheory.isprime(p) and poly.is_irreducible:
|
|
|
# 使用sympy的不可约检查
|
|
|
try:
|
|
|
# 转换为有限域上的多项式进行检查
|
|
|
if poly.is_irreducible:
|
|
|
return poly
|
|
|
except:
|
|
|
continue
|
|
|
|
|
|
# 如果没找到，使用一些已知的不可约多项式
|
|
|
x = sp.Symbol('x')
|
|
|
if p == 2:
|
|
|
if n == 3:
|
|
|
return sp.Poly(x**3 + x + 1, x, modulus=p)
|
|
|
elif n == 4:
|
|
|
return sp.Poly(x**4 + x + 1, x, modulus=p)
|
|
|
elif n == 5:
|
|
|
return sp.Poly(x**5 + x**2 + 1, x, modulus=p)
|
|
|
elif p == 3:
|
|
|
if n == 3:
|
|
|
return sp.Poly(x**3 + 2*x + 1, x, modulus=p)
|
|
|
elif p == 5:
|
|
|
if n == 3:
|
|
|
return sp.Poly(x**3 + x + 2, x, modulus=p)
|
|
|
|
|
|
# 默认返回一个
|
|
|
return sp.Poly(x**n + x + 1, x, modulus=p)
|
|
|
|
|
|
def find_generator(poly, p, n):
|
|
|
"""在有限域F_{p^n}中寻找一个生成元"""
|
|
|
x = sp.Symbol('x')
|
|
|
field_size = p ** n
|
|
|
|
|
|
# 测试所有可能的非零多项式（次数小于n）
|
|
|
for i in range(1, field_size):
|
|
|
# 将i转换为多项式
|
|
|
coeffs = []
|
|
|
num = i
|
|
|
for _ in range(n):
|
|
|
coeffs.append(num % p)
|
|
|
num //= p
|
|
|
|
|
|
# 创建多项式
|
|
|
a_poly = sp.Poly(coeffs, x, modulus=p)
|
|
|
|
|
|
# 检查阶是否为p^n - 1
|
|
|
if is_generator(a_poly, poly, p, n, field_size - 1):
|
|
|
return a_poly
|
|
|
|
|
|
# 如果没找到，返回x
|
|
|
return sp.Poly(x, x, modulus=p)
|
|
|
|
|
|
def is_generator(element, poly, p, n, order):
|
|
|
"""检查元素是否是生成元"""
|
|
|
x = sp.Symbol('x')
|
|
|
current = sp.Poly(1, x, modulus=p) # 单位元
|
|
|
|
|
|
# 计算元素的阶
|
|
|
for i in range(1, order + 1):
|
|
|
# 多项式乘法并取模
|
|
|
current = sp.rem(current * element, poly, modulus=p)
|
|
|
|
|
|
# 如果i < order但已经得到1，则不是生成元
|
|
|
if i < order and current == sp.Poly(1, x, modulus=p):
|
|
|
return False
|
|
|
|
|
|
# 如果i == order且得到1，则是生成元
|
|
|
if i == order and current == sp.Poly(1, x, modulus=p):
|
|
|
return True
|
|
|
|
|
|
return False
|
|
|
|
|
|
def construct_field(p, n):
|
|
|
"""构造有限域F_{p^n}"""
|
|
|
print(f"构造有限域 F_{{{p}^{n}}} = F_{{{p**n}}}")
|
|
|
print("=" * 50)
|
|
|
|
|
|
# 1. 寻找极小多项式
|
|
|
poly = find_irreducible_polynomial(p, n)
|
|
|
print(f"极小多项式 p(x) = {poly}")
|
|
|
print()
|
|
|
|
|
|
# 2. 寻找生成元
|
|
|
alpha = find_generator(poly, p, n)
|
|
|
print(f"生成元 α = {alpha}")
|
|
|
print()
|
|
|
|
|
|
# 3. 生成所有非零元素
|
|
|
field_size = p ** n
|
|
|
elements = []
|
|
|
x = sp.Symbol('x')
|
|
|
|
|
|
# 生成α的幂
|
|
|
current = sp.Poly(1, x, modulus=p) # α^0
|
|
|
elements.append((0, current.copy()))
|
|
|
|
|
|
for i in range(1, field_size - 1):
|
|
|
current = sp.rem(current * alpha, poly, modulus=p)
|
|
|
elements.append((i, current.copy()))
|
|
|
|
|
|
# 4. 显示对应表
|
|
|
print(f"有限域 F_{{{p**n}}} 的非零元素表:")
|
|
|
print("=" * 60)
|
|
|
print(f"{'α的幂':<10} | {'多项式表示':<30} | {'向量表示'}")
|
|
|
print("-" * 60)
|
|
|
|
|
|
for power, poly_repr in elements:
|
|
|
# 获取多项式系数
|
|
|
coeff_dict = poly_repr.as_dict()
|
|
|
coeffs = [0] * n
|
|
|
|
|
|
for deg, coeff in coeff_dict.items():
|
|
|
if len(deg) > 0:
|
|
|
coeffs[deg[0]] = coeff % p
|
|
|
|
|
|
# 构建向量表示
|
|
|
vector = "(" + ", ".join(str(c) for c in coeffs[::-1]) + ")" # 高次在前
|
|
|
|
|
|
print(f"α^{power:<7} | {str(poly_repr):<30} | {vector}")
|
|
|
|
|
|
print("=" * 60)
|
|
|
print(f"注意: α^{field_size-1} = α^0 = 1")
|
|
|
|
|
|
return poly, alpha, elements
|
|
|
|
|
|
def main():
|
|
|
"""主函数"""
|
|
|
print("有限域构造实验")
|
|
|
print("=" * 50)
|
|
|
|
|
|
# 随机选择参数
|
|
|
random.seed() # 使用当前时间作为种子
|
|
|
|
|
|
# 10以内的素数
|
|
|
primes = [2, 3, 5, 7]
|
|
|
p = random.choice(primes)
|
|
|
|
|
|
# 3到10之间的正整数
|
|
|
n = random.randint(3, 10)
|
|
|
|
|
|
print(f"随机选择的参数: p = {p}, n = {n}")
|
|
|
print()
|
|
|
|
|
|
# 构造有限域
|
|
|
poly, alpha, elements = construct_field(p, n)
|
|
|
|
|
|
# 验证域的性质
|
|
|
print("\n验证:")
|
|
|
print(f"1. 域的大小: {p**n}")
|
|
|
print(f"2. 非零元素个数: {p**n - 1}")
|
|
|
print(f"3. 生成元的阶: {p**n - 1}")
|
|
|
print(f"4. p(x)的次数: {sp.degree(poly)}")
|
|
|
print(f"5. p(x)在F_{p}上不可约")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
|
main() |
