当前位置: 首页 > 工具软件 > ntl > 使用案例 >

NTL之多项式模块GF2X

阎鸿煊
2023-12-01

在经过了漫长的怠工之后,琪琪子继续为大家更新NTL库,今天主要是NTL中的伽罗瓦域GF2上的模2多项式模块,在这里我们先给出官方文档,随后给出在sage软件中封装好GF2X模块,由于sage的语法更加类似python,我们甚至不需要直接使用NTL lib。
/**************************************************************************\

模块名:GF2X
摘要:
GF2X中实现了mod2的多项式。多项式计算的方法中,使用了经典过程和Karatsuba算法。

**************************************************************************/

#include <NTL/GF2.h>
#include <NTL/vec_GF2.h>

class GF2X {
public:

GF2X(); //GF2X(),初始化多项式,多项式的初始值为0.

GF2X(const GF2X& a); // 拷贝构造函数,该构造函数会传入一个GF2X的对象a的引用
explicit GF2X(long a); // 显式构造函数,该构造函数的参数为一个long类型对象a
explicit GF2X(GF2 a); // 显式构造函数,该构造函数的参数为一个GF2X类型的对象a

GF2X& operator=(const GF2X& a); // 等号,赋值函数,返回对GF2X对象的引用
GF2X& operator=(GF2 a);//等号, 赋值函数,返回对GF2X对象的引用
GF2X& operator=(long a);//等号,传入long类型,返回GF2X类型的引用

~GF2X(); // 析构函数

GF2X(GF2X&& a);//该函数只有C++11才支持,需要首先设置NTL_EXCEPTIONS,声明这样的变量才不会引发异常

#ifndef NTL_DISABLE_MOVE_ASSIGN
GF2X& operator=(GF2X&& a);//在没有定义NTL_DISABLE_MOVE_ASSIGN的情况下,
// move assignment (C++11 only) 移除赋值符号,仅在C++11下才支持,需要在设定了NTL_EXCEPTIONS flag下才不会抛出异常
#endif

GF2X(INIT_MONO_TYPE, long i, GF2 c);//初始化多项式的某一项,假设某一项的系数为c,次数为i,则使用该函数进行初始化
GF2X(INIT_MONO_TYPE, long i, long c);//直接使用long类型的c也可以为某一项进行赋值
// initialize to c*X^i, invoke as GF2X(INIT_MONO, i, c)

GF2X(INIT_MONO_TYPE, long i);//初始化为cX**i,调用方式为GF2X(INIT_MONO,i)

//类型定义,以便辅助通用编程(generic programming
typedef GF2 coeff_type;//将GF2定义为coeff_type(系数类型)
typedef GF2E residue_type;//将GF2E定义为余数类型
typedef GF2XModulus modulus_type;//将GF2XModulus定义为模数类型

// …

};

/**************************************************************************\

访问系数

多项式f的次数可以通过deg(f)的方式获取,根据定义,如果f是零多项式的话,其次数为-1。多项式f被表示为系数向量,系数可以通过两种方式进行访问。

安全的高层方法是调用函数coeff(f.i),以便获取Xi的系数,并且调用函数SetCoeff(f,i,a)以便设置Xi的系数为标量a。

我们也可以通过一个低层的接口来访问参数,多项式f的系数我们可以使用下标方式f[i]访问到。 此外,人们可以使用下标表示法f[i]得到。此外,人们可以写到f.setLength(n)以便设置底层向量n的长度,以及f.SetMaxLength(n)以便为n格系数分配空间,并且并不修改系数参数自身。

在使用底层接口设置参数之后,人们一定要能够确保系数向量的首项的0被移除,该项操作可以通过f.normalize()实现。

注意:和我们的多项式类不一样,GF2X中的系数向量拥有特殊的表示,会将系数打包到字中,这会导致两个直接结果,首先,对非常数的多项式f使用索引表示法的时候,返回的格式是ref_G2,而不是GF2&。 大部分情况下,一个ref_GF2可以用作GF2&—详情请见GF2.txt。 第二点,当我们对多项式f使用f.SetLength(n)的时候,本质上的效果就是将全体i>=n的X**i的系数设置为0.

#include <NTL/GF2X.h>
using namespace std;
using namespace NTL;

int main()
{
	
	long poly = 100;
	//init a new polynomial , and its initial value(degree 0,constant item)
	//now the function is f=1(f=5 actually, but f=5 mod 2 = 1)
	GF2X f = GF2X((long)5);
	cout << "I have created a new polynomial, it is : " << f << endl;
	//return -1,since currently,polynomial f is a 0 polynomial
	cout << "The degree of f is: " << deg(f) << endl;

	//now we set f(x)=3*x**2,c=3,i=2
	//you have read more to get INIT_MONO_TYPE definition.
	int i = 2, c = 3;
	SetCoeff(f, 2, 3);//3x**2,after modulo 2,now the funtion is f(x)=x**2+1
	cout << "now the polynomial is: " << f << endl;
	//now we are going to test high level and low level 
	//function to get coefficients of polynomial f
	cout << "The degree of f is: " << deg(f) << endl;

	cout << "low level test of getting coefficient f[i]" << endl;
	for (int i = 0; i < deg(f); i++) {
		cout << "the " << i << "th coefficient of polynomial f is:" << f[i] << endl;
	}

	cout << "high level test of getting coefficient f[i]: coeff(f,i)" << endl;
	for (int i = 0; i < deg(f); i++) {
		cout << "the " << i << "th coefficient of polynomial f is:" << coeff(f,i) << endl;
	}
	cout << "now we are going to set the length of f by f.setLength ,degree of f would be 10" << endl;
	int n = 10;
	f.SetLength(n);
	SetCoeff(f, 10, 1);
	cout << "current f: " << f << endl;
	cout << "degree of f: " << deg(f) << endl;
	cout << "now we are going to clear the leading 0 coefficients of f by f.normalize" << endl;
	f.normalize();
	cout << "current f: " << f << endl;
	cout << "degree of f: " << deg(f) << endl;

	return 0;
}
 类似资料: