DCLXVI: Pairing computation on AMD64 processors

Do not use this code!
This implementation has been depricated by the Kim-Barbulescu attacks!

In the paper New software speed records for cryptographic pairings we describe an implementation of cryptographic pairings over a Barreto-Naehrig curve that sets new speed records for cryptographic pairings on many amd64 processors. We put the software into the public domain.
To download and build the latest version of the software do the following:

wget http://polycephaly.org/projects/dclxvi/data/dclxvi-20130329.tar.bz2
tar xjvf dclxvi-20130329.tar.bz2
cd dclxvi-20130329/

This will produce 10 binaries: bilintest-check, bilintest-c, bilintest-as, speedtest-check, speedtest-c, and speedtest-as, test_curvepoint_multiscalar-as, test_curvepoint_multiscalar-check, test_twistpoint_multiscalar-as, test_twistpoint_multiscalar-check.
The binaries ending on -check perform all arithmetic with included overflow check as described in the paper. The files ending on -c are non-optimized implementations in C and the implementations ending on -as have all speed-critical functions implemented in qhasm.
The bilintest binaries perform NTESTS bilinearity (and non-degeneracy) tests, the value NTESTS is defined in the Makefile. The speedtest binaries measure the cycles counts of the most speed-critical functions.
Since version 20130329, DCLXVI also has faster (but not timing-attack protected!) functions for scalar multiplication and multi-scalar multiplication on the curve and the twist. The test_curvepoint_multiscalar and test_twistpoint_multiscalar binaries perform simple tests of this multi-scalar multiplication on curve and twist, respectively.

Caution: The software as described in the printed version of the paper has a bug: The parameter u=1966080 used to construct the curve we use for the pairing does not generate a Barreto-Naehrig curve; the order of the group E(Fp) is not prime. We thank Francisco Rodríguez- Henríquez and Jean-Luc Beuchat for pointing out this bug.
The software from version 20100618 now uses a different curve generated with u=1868033, the speed of this updated software is similar, actually even slightly faster.
For verification of the performance numbers the old version of the software is still available as dclxvi-notsecure.tar.bz2; do not use this software for cryptographic purposes.

Update: An even faster pairing implementation has been presented by Jean-Luc Beuchat, Jorge Enrique González Díaz, Shigeo Mitsunari, Eiji Okamoto, Francisco Rodríquez-Henríquez and Tadanori Teruya.
But our software is a bit (read: one bit) more secure.

Do not use this code!
This implementation has been depricated by the Kim-Barbulescu attacks!