News Archive 11

I spent most of my time since the last release on a new test program confusingly named pbc. It allows interactive testing of the library. During the development I felt I may have been better off working on performance improvements instead of squandering time on a hand-written parser and interpreter, but now that it works, I’m pleased with the results. I have yet to document it. The following session shows how it can be used:

There are actually no prompts. I edited them in afterwards to show exactly what I was typing.

I made a couple of minor fixes so that mingw can compile PBC. The resulting binaries for Windows are on the download page.

I generally get worse times with the Windows binaries, and they seem to vary more from run to run.

I rewrote element_vfprintf() so it does not use GNU C extensions. PBC should now compile under mingw, though I have to test this.

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.