Small-base modexp

[Marco Bodrato]

Ciao,

Il Gio, 19 Settembre 2019 10:39 pm, Marco Bodrato ha scritto:
>> Il Mer, 4 Settembre 2019 10:44 am, Niels Möller ha scritto:
>>> I think I've seen comments in the literature saying that 2^e mod m is
>>> "obviously" more efficient than general modular exponentiation. But as

> If nobody started or is willing to try... I'll try to write such a special
> function for base=2.

I tried... the attempt is attached.

I wrote the doubling-modulo step with 3 possible operations:
 if it can not overflow, simply lshift;
 otherwise choose between (x*2-m) and ((x-m)*2)

I had to write special code for size=1, because my first try was slower
than the generic code. The attached code is faster than the current (when
base=2)  for all sizes on my laptop.
But on shell it is not!

[bodrato at shell /var/tmp/bodrato/gmp-repo]$ tune/speed -rs1-10000 -f1.6
mpz_powm mpz_powm.2 mpz_powm.3
overhead 0.000000002 secs, precision 10000 units of 2.86e-10 secs, CPU
freq 3500.08 MHz
             mpz_powm    mpz_powm.2    mpz_powm.3
1         0.000004322       #0.8082        0.9884
2         0.000007201        1.0723       #0.9836
3         0.000013274       #0.9465        0.9928
4         0.000020143       #0.9408        0.9822
6         0.000033094       #0.8662        0.9964
9         0.000062521       #0.8396        0.9964
14        0.000137914       #0.8000        0.9996
22        0.000317164       #0.7911        1.0061
35        0.000779100       #0.7662        0.9771
56        0.001738323       #0.7941        1.0011
[...]
3798      0.839609000       #0.7757        0.9969
6076      1.513591000       #0.7794        1.0269
9721      2.472574000       #0.7542        0.9746

So, let's say that, asymptotically, «2^e mod m is "obviously" more
efficient than general modular exponentiation». For small sizes it is not
so easy to write specialised functions :-)

Ĝis,
m

-- 
http://bodrato.it/papers/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: gmp.diff
Type: text/x-patch
Size: 11020 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20190921/a6b54937/attachment-0001.bin>