News Archive 10

I implemented finite fields using Montgomery representation. Multiplication is faster, though inversion slows down a little. This improves the running time of all pairings except E (this pairing type isn’t useful anyway).

I enjoyed the challenge of writing it, but I can’t help feel that there ought be an implementation of integer mod rings in GMP. After all, GMP already has Montgomery reduction in its mpz_powm() function, and it has modular inversion routines too. With a little more coding they could easily get a fast integer mod ring library. I would much rather focus on elliptic curves.

There are some changes which may break compatibility with previous releases. I had forgotten to write element_sgn for the new finite fields code (which broke a few things). I have now fixed this, but I have changed the way it works. This means compressed elements from earlier PBC versions will be incompatible.

Also, there are minor change in the element_from_hash() functions, and they behave differently now.

Besides minor bugfixes and cleanup, finite fields are now much faster, which benefits all pairings. I also added some optimizations for type F pairings in particular. I eliminated memset() calls (see previous post) in several places by introducing a flag.

I have also included a CMakeLists.txt file which allows the PBC to be built using CMake. I prefer CMake because it is faster and does not increase the package size [more on this].

I removed the list of things to do from this site, because it is outdated and probably not helpful to anyone but me. From now I’ll post items if I want to make my plans public.

I’ve been working on a faster implementation of finite fields. It is almost the same as the naive implementation that consists mostly of GMP wrappers, but is slightly more efficient because it avoids some dynamic memory allocation (once the modulus is known, the number of GMP limbs needed to store field elements is fixed) and can call low-level GMP functions.

The new implementation has some drawbacks: notably setting an element to a low integer, especially zero or one, is much slower because now a whole array has to be cleared, whereas before GMP would only need to change the _mp_size field. This slows down some of my pairing code. At the moment I’m removing such calls on F pairings (I have already fixed D pairings), and will release once that is done.

Next I want to implement finite fields using Montgomery reduction. I had already tried this once before, but due to bad coding it was slower than the simple implementation. With more experience with GMP internals, I’m confident I’ll be able to make it fast this time, which will benefit all pairings.

Preprocessing has been implemented for A and D pairings, the former benefiting greatly from this. See the benchmarks page.

Some minor bugfixes. Code cleanup: started removing include statements from header files that are used internally by PBC (see the last section in Rob Pike’s notes on programming in C). And the previous tarballs left out a header file.