Side channel silent karatsuba / mpn_addmul_2 karatsuba

[Marco Bodrato]

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