# Side channel silent karatsuba / mpn_addmul_2 karatsuba

Torbjörn Granlund tg at gmplib.org
Fri Dec 14 07:43:31 UTC 2018

```"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

Found it:
https://gmplib.org/list-archives/gmp-devel/2016-December/004502.html

It used -1, and has an if (in the "Next message (by thread)", Niels
suggested how to remove it). Funny code :-)

Here is my code for halfword x halfword.  It evaluates in 0, +1, and
infinity.  (I non-obvious property here is that e1hc can become
"negative" but that works just fine.)

void
karascs (ulong p, ulong u, ulong v)
{
ulong a = u >> 32;
ulong b = u & 0xfffffffful;
ulong c = v >> 32;
ulong d = v & 0xfffffffful;

ulong e0 = b * d;
ulong ei = a * c;
ulong e1 =   ((a + b) & 0xfffffffful) * ((c + d) & 0xfffffffful);
ulong e1ha =-((a + b) >> 32)          & ((c + d) & 0xfffffffful);
ulong e1hb = ((a + b) & 0xfffffffful) &-((c + d) >> 32);
ulong e1hc = ((a + b) >> 32)          & ((c + d) >> 32);
ulong e1h = e1ha + e1hb;

ulong g = e1 + (e0 >> 32);
e1hc -= (g < e0);
g -= e0;
e1hc -= (g < ei);
g -= ei;

p = (g << 32) | (e0 & 0xfffffffful);
ei += (g >> 32) + e1h + (e1hc << 32);
p = ei;
}

Do you think that something alike could be translated to asm and be of
some use on any arch? But that naive code used the half x half -> full
register multiplication, you would use the reg x reg -> double-reg one,
right?

Yes, mp_limb_t x mp_limb_t -> mp_limb_t.

--
Torbjörn
Please encrypt, key id 0xC8601622
```

More information about the gmp-devel mailing list