Side channel silent karatsuba / mpn_addmul_2 karatsuba
Marco Bodrato
bodrato at mail.dm.unipi.it
Thu Dec 13 19:05:29 UTC 2018
Ciao,
Il Gio, 13 Dicembre 2018 1:54 pm, Niels Möller ha scritto:
> tg at gmplib.org (Torbjörn Granlund) writes:
>> nisse at lysator.liu.se (Niels Möller) writes:
>> My hope is to handle those extra bits for free as one adds parts
>> together. (I am sure Marco gave all this a thought, looking at his
>> solutions would be enlightening.)
Not much. My goal was to write a surely correct and hopefully not too slow
sec_mul. I simply handled the extra-bits with an (n+1)x(n+1) -> 2n+1
multiply...
In general I do not like the idea of cutting O(n) slices off a
small-o(n^2) algorithm... even if, I must admit that, for sizes around the
threshold this idea can be very interesting (around the threshold, the
algorithm still behave as big-O(n^2)).
[...]
> So +1 sounds better than -1. But it were still surprisingly many
> operations on the n=1 case.
I'm sure that n=1 is far below the threshold :-)
Ĝis,
m
More information about the gmp-devel
mailing list