NTL使用

谭梓
2023-12-01

 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
 类似资料: