mpz_t C++ wrapper

Heiko Wundram modelnine at modelnine.org
Wed Apr 30 20:26:40 CEST 2008


Hi all!

In a project I've been working on implementing ElGamal public-key 
cryptography, I found mpz_class' implementation of overloading the C++ 
arithmetic operators to be somewhat lacking, because chained operations 
require a temporary mpz_t as destination at many steps evaluating a slightly 
more complicated expression tree (especially expressions involving more than 
one mpz_class instance).

I know that mpz_class allows you to use the underlying mpz functions directly, 
thus optimizing the temporary usage explicitly, but especially with the 
ability to overload operators, I find this to be quite cumbersome to read in 
the end (and not very C++-like), and additionally this also generates 
convoluted code, because mpz_class does not override operator mpz_srcptr or 
mpz_ptr (requiring you to access the mpz_t pointer with get_mpz_t()), which 
is somewhat of a PITA.

Anyway, quite a few temporaries can be programmatically optimized out of an 
evaluation chain through meta-programming with templates, and I've basically 
reimplemented mpz_class using an "optimized" expression evaluation system, so 
that temporaries are only created when required to keep the general 
evaluation semantics of C++ (operators bind left, assignments bind right).

Currently, I've only got my implementation of the ElGamal algorithm to 
benchmark (which manages to execute a somewhat larger number of verifying 
operations per second with my mpz_class re-implementation, but I'd not be 
that hypocritical to generalize from there...), but if there's any code base 
out there using mpz_class extensively (or someone knows of one they can point 
me at; Google isn't especially helpful here), I'd happily give any interested 
party access to the source so that they can test how/if my reimplementation 
fares better for them.

I plan on releasing the code under a BSD-style license anyway, it's just that 
currently (because I only use _very_ limited parts of the wrapper in my 
application) it's probably broken in one aspect or another, and generally I 
can't actually say that there is any speed improvement in a "real-world" 
application of it (simply because I don't know what "real-world" terms look 
like). It shouldn't perform worse than mpz_class, anyway (except possibly at 
compilation speed), but I just want to escape all the NIH callers before 
releasing it... :-)

Anyway, just to give an (somewhat artificial) example:

mpz_class val, val2;
val = val * val2 * 3 + 10 * val;

produces with my mpz_class reimplementation with g++ -O3 (transcribed from the 
generated assembly):

mpz_init(tmp)
mpz_mul(tmp,val,val2)
mpz_mul_si(tmp,tmp,3)
mpz_init(tmp2)
mpz_mul_si(tmp2,val,10)
mpz_add(val,tmp,tmp2)
mpz_clear(tmp)
mpz_clear(tmp2)

with the default mpz_class implementation with g++ -O3 (transcribed from the 
generated assembly):

mpz_init(tmp)
mpz_init(tmp2)
mpz_mul(tmp2,val,val2)
mpz_mul_si(tmp,tmp2,3)
mpz_clear(tmp2)
mpz_init(tmp3)
mpz_mul_si(tmp3,val,10)
mpz_add(val,tmp,tmp3)
mpz_clear(tmp)
mpz_clear(tmp3)

Thanks for any feedback!

-- 
Heiko Wundram


More information about the gmp-discuss mailing list