Small-base modexp
Marco Bodrato
bodrato at mail.dm.unipi.it
Sat Sep 21 06:48:07 UTC 2019
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>
More information about the gmp-devel
mailing list