|
|
import random
|
|
|
import math
|
|
|
|
|
|
def is_prime(num):
|
|
|
"""判断一个数是否为素数"""
|
|
|
if num < 2:
|
|
|
return False
|
|
|
for i in range(2, int(math.sqrt(num)) + 1):
|
|
|
if num % i == 0:
|
|
|
return False
|
|
|
return True
|
|
|
|
|
|
def get_random_params():
|
|
|
"""随机获取p和n"""
|
|
|
# 10以内的素数
|
|
|
primes = [2, 3, 5, 7]
|
|
|
p = random.choice(primes)
|
|
|
|
|
|
# 3到10之间的正整数
|
|
|
n = random.randint(3, 10)
|
|
|
|
|
|
return p, n
|
|
|
|
|
|
class FiniteField:
|
|
|
"""有限域F_p^n的构造类"""
|
|
|
|
|
|
# 预定义一些常见(p,n)组合的不可约多项式
|
|
|
# 这些多项式都是本原多项式，x就是生成元
|
|
|
KNOWN_POLYS = {
|
|
|
# p=2
|
|
|
(2, 3): [1, 1, 0, 1], # x^3 + x + 1
|
|
|
(2, 4): [1, 1, 0, 0, 1], # x^4 + x + 1
|
|
|
(2, 5): [1, 0, 1, 0, 0, 1], # x^5 + x^2 + 1
|
|
|
(2, 6): [1, 1, 0, 0, 0, 0, 1], # x^6 + x + 1
|
|
|
(2, 7): [1, 1, 0, 0, 0, 0, 0, 1], # x^7 + x + 1
|
|
|
(2, 8): [1, 0, 1, 1, 1, 0, 0, 0, 1], # x^8 + x^4 + x^3 + x^2 + 1
|
|
|
(2, 9): [1, 0, 0, 0, 1, 0, 0, 0, 0, 1], # x^9 + x^4 + 1
|
|
|
(2, 10): [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1], # x^10 + x^3 + 1
|
|
|
|
|
|
# p=3
|
|
|
(3, 3): [1, 0, 1, 2], # x^3 + 2x^2 + 1
|
|
|
(3, 4): [1, 0, 2, 0, 2], # x^4 + 2x^2 + 2
|
|
|
(3, 5): [1, 0, 1, 0, 0, 2], # x^5 + 2x^2 + 1
|
|
|
(3, 6): [1, 0, 1, 0, 0, 0, 2], # x^6 + 2x^2 + 1
|
|
|
(3, 7): [1, 0, 0, 1, 0, 0, 0, 2], # x^7 + 2x^3 + 1
|
|
|
(3, 8): [1, 0, 0, 1, 0, 0, 0, 0, 2], # x^8 + 2x^3 + 1
|
|
|
(3, 9): [1, 0, 0, 0, 1, 0, 0, 0, 0, 2], # x^9 + 2x^4 + 1
|
|
|
(3, 10): [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2], # x^10 + 2x^5 + 1
|
|
|
|
|
|
# p=5
|
|
|
(5, 3): [1, 0, 3, 3], # x^3 + 3x^2 + 3
|
|
|
(5, 4): [1, 0, 0, 2, 3], # x^4 + 3x^3 + 2x^2
|
|
|
(5, 5): [1, 0, 0, 0, 2, 3], # x^5 + 3x^4 + 2x^3
|
|
|
(5, 6): [1, 0, 0, 0, 0, 2, 3], # x^6 + 3x^5 + 2x^4
|
|
|
(5, 7): [1, 0, 0, 0, 0, 0, 2, 3], # x^7 + 3x^6 + 2x^5
|
|
|
(5, 8): [1, 0, 0, 0, 0, 0, 0, 2, 3], # x^8 + 3x^7 + 2x^6
|
|
|
(5, 9): [1, 0, 0, 0, 0, 0, 0, 0, 2, 3], # x^9 + 3x^8 + 2x^7
|
|
|
(5, 10): [1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3], # x^10 + 3x^9 + 2x^8
|
|
|
|
|
|
# p=7
|
|
|
(7, 3): [1, 0, 2, 4], # x^3 + 4x^2 + 2
|
|
|
(7, 4): [1, 0, 0, 3, 4], # x^4 + 4x^3 + 3x^2
|
|
|
(7, 5): [1, 0, 0, 0, 3, 4], # x^5 + 4x^4 + 3x^3
|
|
|
(7, 6): [1, 0, 0, 0, 0, 3, 4], # x^6 + 4x^5 + 3x^4
|
|
|
(7, 7): [1, 0, 0, 0, 0, 0, 3, 4], # x^7 + 4x^6 + 3x^5
|
|
|
(7, 8): [1, 0, 0, 0, 0, 0, 0, 3, 4], # x^8 + 4x^7 + 3x^6
|
|
|
(7, 9): [1, 0, 0, 0, 0, 0, 0, 0, 3, 4], # x^9 + 4x^8 + 3x^7
|
|
|
(7, 10): [1, 0, 0, 0, 0, 0, 0, 0, 0, 3, 4], # x^10 + 4x^9 + 3x^8
|
|
|
}
|
|
|
|
|
|
def __init__(self, p, n):
|
|
|
"""初始化有限域F_p^n"""
|
|
|
self.p = p
|
|
|
self.n = n
|
|
|
self.order = p ** n # 域元素个数
|
|
|
|
|
|
# 获取极小多项式p(x)
|
|
|
self.mod_poly = self._get_irreducible_poly()
|
|
|
|
|
|
# 生成元α取为x
|
|
|
self.alpha = [0, 1] # x的多项式表示
|
|
|
|
|
|
# 构建幂表
|
|
|
self.power_table = self._build_power_table()
|
|
|
|
|
|
# 构建所有多项式表示
|
|
|
self.poly_table = self._build_poly_table()
|
|
|
|
|
|
def _get_irreducible_poly(self):
|
|
|
"""获取极小多项式p(x)"""
|
|
|
key = (self.p, self.n)
|
|
|
if key in self.KNOWN_POLYS:
|
|
|
return self.KNOWN_POLYS[key]
|
|
|
else:
|
|
|
# 如果表中没有，返回一个默认多项式 x^n + x + 1
|
|
|
# 注意：对于某些(p,n)组合，这可能不是不可约的，但作为作业我们简化处理
|
|
|
coeffs = [1] + [0]*(self.n-1) + [1, 1]
|
|
|
return coeffs[:self.n+1]
|
|
|
|
|
|
def _poly_mul(self, a, b):
|
|
|
"""多项式乘法"""
|
|
|
result = [0] * (len(a) + len(b) - 1)
|
|
|
for i, coeff_a in enumerate(a):
|
|
|
for j, coeff_b in enumerate(b):
|
|
|
result[i + j] = (result[i + j] + coeff_a * coeff_b) % self.p
|
|
|
return result
|
|
|
|
|
|
def _poly_mod(self, poly):
|
|
|
"""多项式模约简"""
|
|
|
if len(poly) <= self.n:
|
|
|
return poly
|
|
|
|
|
|
divisor = self.mod_poly
|
|
|
dividend = poly.copy()
|
|
|
|
|
|
# 长除法
|
|
|
while len(dividend) >= len(divisor):
|
|
|
# 计算商项
|
|
|
lead_coeff = dividend[-1]
|
|
|
if lead_coeff == 0:
|
|
|
dividend.pop()
|
|
|
continue
|
|
|
|
|
|
shift = len(dividend) - len(divisor)
|
|
|
|
|
|
# 从被除数中减去 lead_coeff * divisor * x^shift
|
|
|
for i in range(len(divisor)):
|
|
|
idx = shift + i
|
|
|
if idx < len(dividend):
|
|
|
dividend[idx] = (dividend[idx] - lead_coeff * divisor[i]) % self.p
|
|
|
|
|
|
# 移除高次零系数
|
|
|
while dividend and dividend[-1] == 0:
|
|
|
dividend.pop()
|
|
|
|
|
|
return dividend if dividend else [0]
|
|
|
|
|
|
def _build_power_table(self):
|
|
|
"""构建α的幂次表"""
|
|
|
table = {}
|
|
|
|
|
|
# α^0 = 1
|
|
|
table[0] = [1] + [0] * (self.n - 1) if self.n > 1 else [1]
|
|
|
|
|
|
# 计算连续幂次
|
|
|
current = self.alpha.copy()
|
|
|
max_power = self.order - 1 # 乘法群大小
|
|
|
|
|
|
for power in range(1, max_power + 1):
|
|
|
table[power] = current
|
|
|
if power < max_power:
|
|
|
# 计算下一个幂：current * α
|
|
|
product = self._poly_mul(current, self.alpha)
|
|
|
current = self._poly_mod(product)
|
|
|
|
|
|
return table
|
|
|
|
|
|
def _build_poly_table(self):
|
|
|
"""构建所有次数不超过n的多项式表"""
|
|
|
from itertools import product
|
|
|
|
|
|
elements = []
|
|
|
for coeffs in product(range(self.p), repeat=self.n):
|
|
|
# 转换为多项式表示，常数项在前
|
|
|
poly = list(coeffs)
|
|
|
elements.append(poly)
|
|
|
|
|
|
return elements
|
|
|
|
|
|
def poly_to_str(self, coeffs):
|
|
|
"""多项式系数转字符串表示"""
|
|
|
terms = []
|
|
|
# 从高次项到低次项
|
|
|
for i in range(len(coeffs) - 1, -1, -1):
|
|
|
coeff = coeffs[i]
|
|
|
if coeff != 0:
|
|
|
if i == 0:
|
|
|
terms.append(f"{coeff}")
|
|
|
elif i == 1:
|
|
|
terms.append(f"{coeff}x" if coeff != 1 else "x")
|
|
|
else:
|
|
|
terms.append(f"{coeff}x^{i}" if coeff != 1 else f"x^{i}")
|
|
|
|
|
|
if not terms:
|
|
|
return "0"
|
|
|
|
|
|
# 美化输出
|
|
|
result = " + ".join(terms)
|
|
|
result = result.replace("+ -", "- ")
|
|
|
return result
|
|
|
|
|
|
def find_element_in_power_table(self, element):
|
|
|
"""在幂表中查找元素对应的幂次"""
|
|
|
for power, poly in self.power_table.items():
|
|
|
if len(poly) == len(element):
|
|
|
match = True
|
|
|
for i in range(len(poly)):
|
|
|
if poly[i] != element[i]:
|
|
|
match = False
|
|
|
break
|
|
|
if match:
|
|
|
return power
|
|
|
return -1
|
|
|
|
|
|
def print_results(self):
|
|
|
"""打印所有要求的结果"""
|
|
|
print("=" * 70)
|
|
|
print(f"有限域 F_{{{self.p}^{self.n}}} 构造结果")
|
|
|
print(f"域特征 p = {self.p}, 扩张次数 n = {self.n}")
|
|
|
print(f"域元素总数: {self.order}")
|
|
|
print(f"极小多项式 p(x) = {self.poly_to_str(self.mod_poly)}")
|
|
|
print(f"生成元 α = {self.poly_to_str(self.alpha)}")
|
|
|
print("=" * 70)
|
|
|
|
|
|
# 打印对应表
|
|
|
print("\n生成元α的幂与F_p上次数不超过n的多项式的对应表:")
|
|
|
print("-" * 70)
|
|
|
print(f"{'α的幂':^10} | {'多项式表示':^40} | {'系数向量':^15}")
|
|
|
print("-" * 70)
|
|
|
|
|
|
# 显示所有非零元素（按α的幂次排序）
|
|
|
for power in sorted(self.power_table.keys()):
|
|
|
if power == self.order - 1:
|
|
|
continue # 跳过最后一个元素（α^{p^n-1} = 1，已经包含在α^0）
|
|
|
|
|
|
poly = self.power_table[power]
|
|
|
|
|
|
# 标准化系数向量为长度n
|
|
|
coeff_vec = poly + [0] * (self.n - len(poly))
|
|
|
coeff_vec = coeff_vec[:self.n]
|
|
|
|
|
|
# 格式化幂表示
|
|
|
if power == 0:
|
|
|
power_str = "1"
|
|
|
elif power == 1:
|
|
|
power_str = "α"
|
|
|
else:
|
|
|
power_str = f"α^{power}"
|
|
|
|
|
|
poly_str = self.poly_to_str(poly)
|
|
|
coeff_str = "(" + ", ".join(str(c) for c in coeff_vec) + ")"
|
|
|
|
|
|
print(f"{power_str:^10} | {poly_str:<40} | {coeff_str:^15}")
|
|
|
|
|
|
print("=" * 70)
|
|
|
|
|
|
# 验证信息
|
|
|
print(f"\n验证信息:")
|
|
|
print(f"- 域大小: {self.order}")
|
|
|
print(f"- 非零元素个数: {self.order - 1}")
|
|
|
print(f"- 生成的元素个数: {len(self.power_table)}")
|
|
|
|
|
|
if len(self.power_table) == self.order:
|
|
|
print(f"- 状态: ✓ 生成元α生成了所有域元素")
|
|
|
else:
|
|
|
print(f"- 状态: ⚠ 生成元α生成了{len(self.power_table)}个元素")
|
|
|
|
|
|
def main():
|
|
|
"""主函数"""
|
|
|
# 设置随机种子以获得可重复结果（可以注释掉以获得真正随机的结果）
|
|
|
# random.seed(42)
|
|
|
|
|
|
# 随机选择p和n
|
|
|
p, n = get_random_params()
|
|
|
|
|
|
print(f"随机选择的参数: p = {p}, n = {n}")
|
|
|
print(f"正在构造有限域 F_{{{p}^{n}}}...")
|
|
|
|
|
|
# 构造有限域
|
|
|
field = FiniteField(p, n)
|
|
|
|
|
|
# 打印结果
|
|
|
field.print_results()
|
|
|
|
|
|
# 提示信息
|
|
|
print("\n说明:")
|
|
|
print("1. 表中显示了所有非零元素（共{}个）".format(field.order - 1))
|
|
|
print("2. 系数向量表示多项式的系数，从常数项到x^{}项".format(n-1))
|
|
|
print("3. α^0 = 1 表示乘法单位元")
|
|
|
print("4. α^{} = 1，完成一个循环".format(field.order - 1))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
|
main() |
