bodr...@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.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
