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:
$ test/pbc
Pairing-Based Calculator
> a=rnd(G1)
> b=rnd(G2)
> c=pairing(a,b,A)
> c
[8123908995412397222629407861526403178767561618899656268507645810910469570940171
354920981464587606639849486738202862428348258236992210185732214124221043399 1895
53814264885989040711088624722149213923285853653986751240825585711288561007379288
8682665226785064897799276077038762941403815137279201878124496544381814]
> r=rand(Zr)
> c^r
[3657835355267111517147932281225731429445945576520458069770856379924948048294629
981309298603543337841873858888814047590238596753897868865331802933313743255 5062
40043246682709738369359568183546905789682883656306401246404807118581570274256476
4691903194225678537056515561674449527079685938158385917551215894965196]
> ar=a^r
> pairing(ar, b)
expect three arguments
runtime error (error code = 0)
> pairing(ar,b,A)
[3657835355267111517147932281225731429445945576520458069770856379924948048294629
981309298603543337841873858888814047590238596753897868865331802933313743255 5062
40043246682709738369359568183546905789682883656306401246404807118581570274256476
4691903194225678537056515561674449527079685938158385917551215894965196]
> br=b^r
> pairing(a,br,A)
[3657835355267111517147932281225731429445945576520458069770856379924948048294629
981309298603543337841873858888814047590238596753897868865331802933313743255 5062
40043246682709738369359568183546905789682883656306401246404807118581570274256476
4691903194225678537056515561674449527079685938158385917551215894965196]
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.
Fri Sep 29 12:33:33 PDT 2006
I rewrote element_vfprintf() so it does not use GNU C extensions.
PBC should now compile under mingw, though I have to test this.
Thu Sep 28 15:06:39 PDT 2006
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.
Thu Sep 28 13:31:56 PDT 2006
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].
Wed Sep 27 17:18:05 PDT 2006
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.
Wed Sep 27 02:37:24 PDT 2006