[Previous] [Up] [Next]

A Tour of NTL: Using NTL with the GF2X library


gf2x is a library for fast multiplication of polynomials over GF(2). The gf2x library was developed by Emmanuel Thomé, Paul Zimmermmann, Pierrick Gaudry, and Richard Brent. You can get more information about it, as well as the latest version from here.

Unlike NTL, which only imlements a version of Karatsuba multiplication, gf2x implements other algorithms that are faster for very large degree polynomials. If you use NTL if the gf2x library, then multiplication, division, GCD, and minimum polynomal calculations for the GF2X class will be faster for large degree polymials.

Note: you will need version 1.2 or later of gf2x for a thread-safe build of NTL.

Downloading and building gf2x

Download gf2x from here. You will get a file gf2x-XXX.tar.gz.

Now do the following:

   % gunzip gf2x-XXX.tar.gz
   % tar xf gf2x-XXX.tar
   % cd gf2x-XXX
   % ./configure --prefix=$HOME/sw
   % make
   % make check
   % make install
This will build, test, and install gf2x in $HOME/sw. Of course, change $HOME/sw to whatever you want (the default is /usr/local). You will find the gf2x header files in $HOME/sw/include and the compiled binaries in $HOME/sw/lib.

You can also supply the option --disable-shared to the configure script, if you only want static libraries. However, if you ultimately want to build NTL as a shared library, then you must also build gf2x as a shared library.

You must ensure that NTL and gf2x have the same ABI. gf2x's configuration script might need some help to select the right one. For example, you may have to pass

   ABI=64 CFLAGS="-m64 -O2"
to gf2x's configure script to force a 64-bit ABI.

Building and using NTL with gf2x

When building NTL with gf2x, you have to tell NTL that you want to use it. The easiest way to do this is by passing the argument NTL_GF2X_LIB=on to the NTL configuration script when you are installing NTL. Assuming you installed gf2x in $HOME/sw as above, and you also want to install NTL in $HOME/sw, you execute:

   % ./configure PREFIX=$HOME/sw NTL_GF2X_LIB=on  GF2X_PREFIX=$HOME/sw
You can write this more simply as
   % ./configure DEF_PREFIX=$HOME/sw NTL_GF2X_LIB=on 
Here, DEF_PREFIX is a variable that is used to specify the location of all software, and it defaults to /usr/local.

If you installed gf2x in /usr/local (or some other standard system directory where your compiler will look by default) then simply

   % ./configure PREFIX=$HOME/sw NTL_GF2X_LIB=on
does the job. Moreover, if NTL is also to be installed in /usr/local, then
   % ./configure NTL_GF2X_LIB=on
does the job.

When compiling programs that use NTL with gf2x, you need to link with the gf2x library. If gf2x is installed as above in $HOME/sw, rather than in a standard system directory, this just means adding -L$HOME/sw/lib -lgf2x to the compilation command. If you installed gf2x in a standard system directory, then just -lgf2x does the job. Note that -lgf2x must come after -lntl on the command line. Finally, if NTL and gf2x are installed as shared libraries, then you don't even need -lgf2x.


[Previous] [Up] [Next]