NTL使用
NTL库的官方网站地址：
https://www.shoup.net/ntl/doc/tour-ex1.html
http://www.shoup.net/ntl/
该网站有详细的说明文档，下载下来的压缩包内也有详细的说明文档。
本帖以winxp下的VC 6.0为例说明NTL的使用方法。
1、我们将压缩包下载下来（不到1M，很快吧）
我们将下载的包解压缩后，要做的第一件事是：
找到WinNTL-5_4_2\include\NTL下的config.h文件，并打开，在里面搜索NTL_STD_CXX，将
#if 1
#define NTL_STD_CXX
改为
#if 0
#define NTL_STD_CXX
如果不修改这个地方，在第一次运行程序时，会出现floor is not a member of std的错误。NTL的文档中说道：
On older versions of Microsoft Visual C++, you may get error messages
like "floor is not a member of std". If that happens, you have to turn off the
NTL_STD_CXX flag by editing the file include/NTL/config.h.
2、生成一个库，用于以后编程使用
说明文档中有一节是：A Tour of NTL: Obtaining and Installing NTL for Windows and other Platforms
里面提到在windows的VC下生成该库的方法如下：（很简单，我就不翻译了）
注：下面提到的“c:\mystuff\WinNTL-xxx”是NTL解压缩后的路径，而“c:\Program Files\Microsoft
Visual Studio\MyProjects\ntl”是ntl这个project的路径，这两个路径都可以自己任选地方。
File -> New -> Projects
project name: ntl
location[default]: c:\Program Files\Microsoft Visual Studio\MyProjects\ntl
Click on Win32 static library
Click on OK
pre-compiled headers[default]: no
MFC support[default]: no
Click on Finish
Click on OK
Project -> Add to Project -> Files
select all files in c:\mystuff\WinNTL-xxx\src and click on OK.
Project -> Settings -> C/C++ //注：这一步骤中，如果除了debug模式外，你还会用到release模式，那么请在该窗口左上角的下拉菜单中选择release，也做相同设置。如果你不知道什么是release，即你用不着release模式，这一条可以不用管它。
Category: Preprocessor.
Additional include directories: c:\mystuff\WinNTL-xxx\include.
Click on OK.
Build -> build ntl.lib
此时，在debug文件夹下就有个ntl.lib了。把它复制出来，存好，以后要用的，比如存到NTL文件夹里。
3、测试第一个程序
官方文档中给出的方法是（建议您将官方给的方法和下面我给出的方法都试一下，体会一下。）：
File -> New -> Projects -> Win32 Console Application
project name: test
location[default]: c:\Program Files\Microsoft Visual Studio\MyProjects\ntl
Click on Win32 Console Application
Click on OK
What kind of windows application...? [default]: An empty project
Click on Finish
Click on OK
Project -> Add to Project -> Files
select the file c:\mystuff\WinNTL-xxx\tests\QuickTest.cpp
Click on OK
Project -> Add to Project -> Files
select the file
c:\Program Files\Microsoft Visual Studio\MyProjects\ntl\Debug\ntl.lib
Note: one must select Files of type: Library Files (.lib) to make this
file visible in the pop-up window.
Click on OK
Project -> Settings -> C/C++
Category: Preprocessor.
Additional include directories: c:\mystuff\WinNTL-xxx\include.
Click on OK.
Build -> build test.exe
Build -> execute test.exe
我并不赞同这个方法，我觉得把必须的include文件夹和ntl.lib库复制到你新建的工程里比较好，这样，即使拷贝到别的计算机上，也能够直接运行，而不需要再把ntl整个文件夹也复制过去了。
我的方法如下：
File -> New -> Projects -> Win32 Console Application
project name: test
location[default]: c:\Program Files\Microsoft Visual Studio\MyProjects\ntltest
Click on Win32 Console Application
Click on OK
What kind of windows application...? [default]: An empty project
Click on Finish
Click on OK
Project -> Add to Project -> Files
select the file
c:\Program Files\Microsoft Visual Studio\MyProjects\ntl\Debug\ntl.lib
Note: one must select Files of type: Library Files (.lib) to make this
file visible in the pop-up window.
Click on OK
将include文件夹拷贝到你新建的库的根目录下，然后设置：
Project -> Settings -> C/C++
Category: Preprocessor.
Additional include directories: include
Click on OK.
然后新建一个文件main.cpp，在里面写个程序如：
#include <NTL/ZZ.h>
NTL_CLIENT
void main()
{
ZZ a, b, c;
cin >> a;
cin >> b;
c = a+b;
cout << c << "\n";
}
然后编译执行即可。
实例1：数据的输入输出（参考文档：A Tour of NTL: Examples: Big Integers）
#include <NTL/ZZ.h>
NTL_CLIENT
void main()
{
ZZ a, b, c, d;
a = to_ZZ("100000000000000000000000000"); //凡是大于32比特的数都要这样输入
b = 1;
cout << "c=? ";
cin >> c;
d = a + b + c;
cout << "a=" << a << ", b=" << b << ", c=" << c << ", d=" << d << "\n";
}
实例2：随机数生成（参考文档：ZZ.txt）
#include <NTL/ZZ.h>
#include <time.h>
NTL_CLIENT
void main()
{
ZZ a,b,c;
SetSeed(to_ZZ(time(NULL)));
RandomLen(a, 32);
RandomLen(b, 32);
c = a + b;
cout << "a=" << a << ", b=" << b << ", c=" << c << "\n";
}
实例3：文件输入输出（参考文档：C++教材）
#include <fstream.h>
#include <NTL/ZZ.h>
NTL_CLIENT
void main()
{
ZZ a, b, c;
ifstream fin("input.txt");
fin >> a;
fin >> b;
c = a + b;
ofstream fout("output.txt");
fout << "a=" << a << ", b=" << b << ", c=" << c << "\n";
fin.close();
fout.close();
}
实例4：求GCD运算（参考文档：ZZ.txt）
#include <NTL/ZZ.h>
NTL_CLIENT
void main()
{
ZZ a, b, c;
a = 12;
b = 20;
GCD(c, a, b);
cout << "a=" << a << ", b=" << b << ", c=" << c << "\n";
}
注：常见的数论运算都可以用类似的方式实现。文档A Tour of NTL: Examples: Big Integers中给出下列说明，这些函数具体用法都可以在ZZ.txt中找到。
GCD -- computes greatest common divisor of two integers
XGCD -- extended Euclidean algorithm
AddMod, SubMod, NegateMod, MulMod, SqrMod, InvMod, PowerMod -- routines for modular arithmetic, including inversion and exponentiation
NumBits -- length of binary representation
bit -- extract a bit
ZZFromBytes, BytesFromZZ -- convert between octet strings and ZZs
RandomBnd, RandomBits, RandomLen -- routines for generating pseudo-random numbers
GenPrime, ProbPrime -- routines for generating primes and testing primality
power -- (non-modular) exponentiation
SqrRoot -- integer part of square root
Jacobi, SqrRootMod -- Jacobi symbol and modular square root
实例4.2：RSA加密解密——模指数实现及时间测量（参考文档：ZZ.txt）
#include <NTL/ZZ.h>
#include <fstream.h>
#include <time.h>
void main()
{
ZZ a, b, c, d;
clock_t tBegin, tEnd;
int i;
ifstream fin("input.txt");
fin >> a;
fin >> b;
fin >> c;
tBegin = clock();
for (i = 0; i < 100; i ++)
d = PowerMod(a, b, c);
tEnd = clock();
cout << d << "\n\n";
cout << "\n\n进行100次1024比特的模指数运算所消耗的时间为:" << tEnd - tBegin << "ms\n";
cin >> i; //用于暂停，观测数据
}
我用的3个1024比特的测试数据：（注：前两个必须比第三个小，否则报错！）
168754607097208466607536196336831490143297319598447554110804143238009375600872422291336951281773997686116009993968584112111426410086253277640320696754613733081060309023164073071560796450167545167774517559609257291340256279960415668127540709121569495880450861576697074771030030898312662221455914056004455351011
152773123054845528139673674019320635255252016079574118507432508809980357024976162874379504185191757100991726643401768734101843167004509186912718986365450065249891424448168124565445917864156150381454263226662793008149804384127662665891180200802009071133551594596625604790081201671018645418161188124945733864989
172524102448143402448919677103417185928260511210028527751170256609087941514397459058525689338048902066978995094970400276084529386638823568421232808086592023970152790577377124299876069755832508735292142435744832017256446637119623487066309686936677974670586458257416974406653862682994591678306768295448948326515
测试结果是100次模指数运算用时7953ms。该数据是用miracl库进行同样的运算所消耗时间的5-6倍左右。（参考http://www.mathmagic.cn/bbs/read.php?boardid=25&tid=7050。我的运行环境是P4 3.0，1G内存）
实例5：向量和矩阵的输入与输出（参考文档：vec_ZZ.txt和mat_ZZ.txt）
#include <NTL/vec_ZZ.h>
#include <NTL/mat_ZZ.h>
NTL_CLIENT
void main()
{
vec_ZZ a;
mat_ZZ b;
cin >> a;
cin >> b;
cout << a << "\n";
cout << b << "\n";
}
第一次运行：
输入：
[1 2 3]
[[1 2 3][4 5 6]]
输出：
[1 2 3]
[[1 2 3]
[4 5 6]
]
第二次运行（如果数很大，建议这样分行输入，其意义与前一方法相同）：
输入：
[
1
2
3
]
[
[1 2 3]
[4 5 6]
]
输出：
[1 2 3]
[[1 2 3]
[4 5 6]
]
实例6：LLL算法实现（参考文档：LLL.txt）
#include <NTL/ZZ.h>
#include <NTL/mat_ZZ.h>
#include <NTL/LLL.h>
#include <fstream.h>
NTL_CLIENT
void main()
{
ZZ det2;
mat_ZZ B;
ifstream fin("input.txt");
fin >> B;
//long LLL(ZZ& det2, mat_ZZ& B, long verbose = 0);
LLL(det2, B, 0);
cout << B << "\n";
}
用文件输入一个基：
[
[1 2 1]
[0 1 1]
[1 0 1]
]
输出它的约化基：
[[0 1 1]
[1 1 0]
[1 0 1]
]
实例7：多项式的表示与分解（参考文档：A Tour of NTL: Examples: Polynomials）
#include <NTL/ZZXFactoring.h>
#include <fstream.h>
NTL_CLIENT
void main()
{
ZZX f;
ifstream fin("input.txt");
fin >> f;
vec_pair_ZZX_long factors;
ZZ c;
factor(c, factors, f);
cout << c << "\n";
cout << factors << "\n";
}
输入：
[2 10 14 6]
（表示2 + 10*X + 14*x^2 +6*X^3）
输出：
2
[[[1 3] 1] [[1 1] 2]]
（表示2 * (1 + 3*X) * (1 + X)^2）
注：这里给出了一个pair_ZZX_long，它是NTL库里定义的一种“对”，即多项式系数构成的数列（如上例中的[1 3]）与该多项式整个外面的指数（如上例中的1）而构成的“对”（如上例中的[[1 3] 1]）。不理解这个概念也不会影响编程，仅仅是一种表示而已。该符号详见pair.txt中的pair_S_T说明。
实例8：多项式的创建、赋值与取值（参考文档：A Tour of NTL: Examples: Polynomials和ZZX.txt）
#include <NTL/ZZX.h>
#include <fstream.h>
NTL_CLIENT
void main()
{
ZZX t1;
SetCoeff(t1, 4, 1); //SetCoeff的优点：自动判断长度是否变化，即保证领项系数非0
t1.rep[2] = 2; //ZZX.rep的缺点：改变系数的同时不判断长度是否变化
SetCoeff(t1, 0, -1);
cout << t1 << "\n";
ZZX t2;
t2.rep.SetLength(6); //如果没有SetCoeff，使用ZZX.rep之前必须先用该句初始化长度
t2.rep[4] = 1;
t2.rep[0] = -1;
cout << t2 << "\n"; //注：此时领项系数是0
t2.normalize(); //作用：重新调整长度，以保证领项系数非0
cout << t2 << "\n";
//下面两种从多项式中取系数的值的方法等价
if (t1.rep[4] == 1)
cout << "11111111111" << "\n";
if (coeff(t1, 4) == 1)
cout << "22222222222" << "\n";
}
输出结果：
[-1 0 2 0 1]
[-1 0 0 0 1 0]
[-1 0 0 0 1]
11111111111
22222222222
Press any key to continue
- GCD -- computes greatest common divisor of two integers
- XGCD -- extended Euclidean algorithm
- AddMod, SubMod, NegateMod, MulMod, SqrMod, InvMod, PowerMod -- routines for modular arithmetic, including inversion and exponentiation
- NumBits -- length of binary representation
- bit -- extract a bit
- ZZFromBytes, BytesFromZZ -- convert between octet strings and ZZs
- RandomBnd, RandomBits, RandomLen -- routines for generating pseudo-random numbers
- GenPrime, ProbPrime -- routines for generating primes and testing primality
- power -- (non-modular) exponentiation
- SqrRoot -- integer part of square root
- Jacobi, SqrRootMod -- Jacobi symbol and modular square root