Side channel silent karatsuba / mpn_addmul_2 karatsuba

Marco Bodrato bodrato at
Thu Dec 13 19:05:29 UTC 2018


Il Gio, 13 Dicembre 2018 1:54 pm, Niels Möller ha scritto:
> tg at (Torbjörn Granlund) writes:
>> nisse at (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

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 :-)


More information about the gmp-devel mailing list