sec_karatsuba

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> I tried to write a _sec_ version of Karatsuba multiplication. It is not
> intended for 5.2, of course, but it is ready and I like to share it. It is
> attached.

Cool.

> It obviously is slower than the non_sec toom22, but not terribly:
>
> 18        0.000000635       #0.9079        1.0035
> 19        0.000000677       #0.9722        1.0510
> 20        0.000000761       #0.8829        0.9771
> 21        0.000000833       #0.9291        0.9859

So threshold around 20 limbs, or 1280 bits. So 4096-bit rsa (with
2048-bit secret primes) is one potential application.

> I used evaluation in +1 instead of -1, to avoid branches due to the
> sign,

For the -1 point, one could use mpn_sub + mpn_cnd_neg to compute
|a-b|. And then also conditonally negate and sign-extend the
corresponding product. I don't know what's best, it's a couple of
negations vs an extra limb in the product.

> By the way, if you have the time to look at the code and comment, I'll
> appreciate.

I haven't read it very carefully, so only one minor point, 

>   ASSERT (an >= bn);
> 
>   s = an >> 1;
>   n = an - s;
>   t = bn - n;
> 
>   ASSERT (mpn_sec_mul_itch (an, bn) >= 4*n + 4);
>   if (UNLIKELY (s + t <= n))
>     {
>       mpn_mul_basecase (rp, ap, an, bp, bn);
>       return;
>     }

I think I'd prefer to do the check for the too unbalanced case earlier,
and not rely on t being signed.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.