Benchmarks for modular multiplications

[Fabien.Herbaut at unice.fr]

Hi,

I'm Fabien Herbaut, I study cryptography in Toulon University, south of France 
with my friend Pascal Veron.

We wonder about the time to compute a modular multiplication with GMP (so we use 
mpz_mul and then mpz_mod). We did benchmarks and found strange results. We used 
gprof to measure the time to perform 2^28 multiplication between two n bits 
number with mpz_mul, and then reduce modulo a n-bits (prime) number using 
mpz_mod. 


We found :

112bits 11s
128bits 9.95s (!)
160bits 28.63s
192bits 27.37s
224bits 32.27s
256bits 37.6s 
384bits 45.03s

Please, would you know how to explain the slow-growing ? Or could you tell us a
reference about such benchmarks ?

Best regards,
Fabien Herbaut &
Pascal Veron