python有限域的运算——galois库（伽罗瓦群）

编程基础 • 2024-12-11 07:01 • 阅读 23

有限域的第一种表示方法称为多项式表示，这种表示是基于域的有限扩张，设p是素数， $q=p^{n}$ ，只要找到 $F_{q}$ 上一个n次不可约多项式f(x)，就有 $F_{q}=F_{p}[x]/(f(x))$ 。在信息安全领域，应用最多的有限域是 GF(2^n) 和素域 GF(p) 。

下面介绍有限域 GF(2^n) 的多项式表示：

选用 GF(2) 上的一个n次既约多项式 p(x) 扩成一个 GF(2^n) ，由模 p(x) 的全体余式的集合，即

$GF(2^n)=\{a_{n-1}x^{n-1}+...+a_{1}x+a_{0},a_{i}\in GF(2) \}$

每个域的素都可以表示为一个次数 $\le n-1$ 的多项式.

基本运算操作

举例:

注：以下皆为有限域的运算或有限域上的多项式运算。

1.创建有限域

GF=galois.GF(24,repr="poly")

repr="poly"指用多项式表示

2.访问有限域的不可约多项式

GF.irreducible_poly

3.构建有限域上的多项式

f = galois.Poly([1, 1, 1], field=GF)

Out: Poly(x^2 + x + 1, GF(2))

注：在有限域上构建多项式后，几乎任何多项式算术运算都可以使用 Python 运算符执行，例如f+g、f-g、f*g、加法逆-f、模余f%g、幂f3.

将多项式和有限域标量相加减乘除，标量被视为 0 次多项式，例：f + GF(3)。

4.函数divmod(f, g)：

将一个多项式除以另一个多项式并返回商和余数。

divmod(f, g)

5.求多项式最大公因数

 d = galois.gcd(f, g)

6.扩展的欧几里得除法求多项式最大公因数和逆

可用该函数求多项式在有限域中的逆。

 d, s, t = galois.egcd(f, g)

7.不可约多项式的因式分解

galois.factors(f) f.factors()

以上两种访问方法都可以，galois.factors(f) == f.factors()。

8.访问有限域的属性

print(GF.properties)

9.检索有限域的素

GF7.elements

10.输出有限域的算数表(加减乘）

以加法为例:

print(GF.arithmetic_table("+"))

11.有限域的生成

galois.primitive_root(7)#抽象有限域的生成组 g = GF.primitive_element#具体有限域的最小生成

12.计算有限域 $F_{p^{n}}$ 的 $|F_{p^{n}}^{*}|$ = $p^{n}-1$

有限域 $F_{p^{n}}$ 的生成g的定义多项式 f(x) 叫做本原多项式，设 f(x) 是 $F_{p}$ 上的n次本原多项式，则使得 $x^{e}\equiv1(modf(x))$ 的最小正整数 $e=p^{n}-1$ 。

g.multiplicative_order()

13.输出有限域的生成表

print(GF.repr_table())

实例

求 $F_{2^{8}}=F_{2}[x]/(x^8+x^4+x^3+x+1)$ 的生成 ,并计算 $g(x)^{t}$ , 和所有生成。

import galois f=galois.irreducible_poly(2,8) GF=galois.GF(28,repr="poly", irreducible_poly=f) print("f=",f) g=GF.primitive_element print("g=",g) g1=g.multiplicative_order() print(g1) print(GF.repr_table(g))

输出Out:

......

注：API参考网址：Arrays - galois (mhostetter.github.io)

今天的文章 python有限域的运算——galois库（伽罗瓦群）分享到此就结束了，感谢您的阅读。