C++数论库：NTL

NTL

官网：https://libntl.org/doc/tour.html

NTL is a high-performance, portable C++ library providing data structures and algorithms for arbitrary length integers; for vectors, matrices, and polynomials over the integers and over finite fields; and for arbitrary precision floating point arithmetic.

NTL provides high quality implementations of state-of-the-art algorithms for:

• arbitrary length integer arithmetic and arbitrary precision floating point arithmetic;
• polynomial arithmetic over the integers and finite fields including basic arithmetic, polynomial factorization, irreducibility testing, computation of minimal polynomials, traces, norms, and more;
• lattice basis reduction, including very robust and fast implementations of Schnorr-Euchner, block Korkin-Zolotarev reduction, and the new Schnorr-Horner pruning heuristic for block Korkin-Zolotarev;
• basic linear algebra over the integers, finite fields, and arbitrary precision floating point numbers.

类型介绍

The basic ring classes are:

• ZZ: big integers
• ZZ_p: big integers modulo p
• zz_p: integers mod “single precision” p
• GF2: integers mod 2
• ZZX: univariate polynomials over ZZ
• ZZ_pX: univariate polynomials over ZZ_p
• zz_pX: univariate polynomials over zz_p
• GF2X: polynomials over GF2
• ZZ_pE: ring/field extension over ZZ_p
• zz_pE: ring/field extension over zz_p
• GF2E: ring/field extension over GF2
• ZZ_pEX: univariate polynomials over ZZ_pE
• zz_pEX: univariate polynomials over zz_pE
• GF2EX: univariate polynomials over GF2E

使用

• 常用函数

SetSeed(const ZZ& s)：设置PRF种子

RandomBnd(ZZ& x, const ZZ& n)：

x

∈

{

0

,

1

,

⋯

n

−

1

}

x in {0,1,cdots n-1}

x∈{0,1,⋯n−1}，如果

n

≤

0

n le 0

n≤0 那么

x

=

0

x=0

x=0

RandomBits(ZZ& x, long l)：随机生成

l

l

l比特的整数

ZZ p(17)：初始化整数为17，这里参数类型是long

p = to_ZZ("123")：读入字符串，可输入大整数

GenPrime(p, 8)：随机生成8比特素数

ZZ_p::init(p)：初始化环

Z

p

Z_p

Zp​

ZZ_p a(2)：初始化为

2

m

o

d

  

p

2 mod p

2modp，这里参数类型是long

random(a)：随机生成

Z

p

Z_p

Zp​中元素

ZZ_pX m：

Z

p

[

x

]

Z_p[x]

Zp​[x]中的多项式，记录为向量

Z

p

n

Z_p^n

Zpn​

SetCoeff(m, 5)：将

x

5

x^5

x5系数置为 1

m[0]=1：将

x

0

x^0

x0系数置为 1

BuildIrred(m, 3)：随机生成3次不可约多项式

ZZ_pE::init(m)：初始化环

Z

p

[

x

]

/

(

m

(

x

)

)

Z_p[x]/(m(x))

Zp​[x]/(m(x))，若

p

p

p是素数且

m

(

x

)

m(x)

m(x)是d次不可约多项式，那么它同构于有限域

G

F

(

p

d

)

GF(p^d)

GF(pd)

ZZ_pEX f, g, h：

G

F

(

p

d

)

[

x

]

GF(p^d)[x]

GF(pd)[x]上的多项式，记录为向量

G

F

(

p

d

)

n

GF(p^d)^n

GF(pd)n

random(f, 5)：随机生成5次多项式

h = sqr(g) % f：计算

h

≡

g

2

m

o

d

  

f

h equiv g^2 mod f

h≡g2modf

• 环

  G

  F

  (

  p

  d

  )

  [

  x

  ]

  /

  (

  x

  n

  −

  1

  )

  GF(p^d)[x]/(x^n-1)

  GF(pd)[x]/(xn−1)上多项式运算：

#include <iostream>

#include <NTL/ZZ_p.h> // integers mod p
#include <NTL/ZZ_pX.h> // polynomials over ZZ_p
#include <NTL/ZZ_pE.h> // ring/field extension of ZZ_p
#include <NTL/ZZ_pEX.h> // polynomials over ZZ_pE
#include <NTL/ZZ_pXFactoring.h>
#include <NTL/ZZ_pEXFactoring.h>

using namespace std;
using namespace NTL;

#pragma comment(lib, "NTL")

int main()
{
	ZZ p(17); //初始化为17
    
    //群Z_p
    ZZ_p::init(p); 

    //随机生成Z_p[x]中的d次不可约多项式
    int d = 4;
    ZZ_pX m;
	BuildIrred(m, d); 
    
    //域GF(p^d) = Z_p[x]/m(x)
    ZZ_pE::init(m); 
    
    //GF(p^d)[x]中的多项式
    ZZ_pEX f, g, h; 
    
    // f(x) = x^8 - 1
	SetCoeff(f, 8); //将 x^8 系数置为 1
    SetCoeff(f, 0, -1); //将 x^0 系数置为 -1

    //随机生成5次多项式
	random(g, 5);

    // 环上多项式的运算：h = g^2 mod f
	h = sqr(g) % f; 
    
    cout << "p = " << p << endl;
    cout << "d = " << d << endl;
    cout << "m(x) = " << m << endl;
    
    cout << "f = " << f << endl;
	cout << "g = " << g << endl;
	cout << "h = " << h << endl;
    
    return 0;
}