Re: Tuning Karatsuba in LibTomMath

From: Tim Josling (tej_at_melbpc.org.au_rubbish_at_nospam.com)
Date: 04/25/03


Date: Fri, 25 Apr 2003 22:52:25 +1000


> Tim Josling <tej_at_melbpc.org.au_rubbish@nospam.com> wrote in message news:<3EA7C914.3080905@nospam.com>...
>
>> I am sure I remember seeing this discussed in the info file - I
>> installed it as part of Red Hat Linux 8.0.
>>
>> I thought the source code was relatively good, considering the fact it
>> is performance oriented code and the algorithms are often quite complex.
>>
>> Certainly the library us fast and has performed flawlessly for me. I
>> also found it easy to use.
>
>
> I didn't question the quality of the results produced. Certainly GMP
> is fast and definitely well tested.
>
> My comparison is based on the fact that LibTomMath uses very similar
> algorithms but doesn't sacrifice too much in terms of code
> readibility.
>
> While GMP is tons faster LibTomMath [actually its normally 2 to 4
> times faster at best] it is a heck of a lot easier to build and use
> right out of the box [its also much smaller if you exclude the
> pre-built PDF manual]. The LibTomMath code is also much easier to
> read since there are no conditionals all over the place.
>
> As for API they are similar. I'd say LibTomMath is a bit simpler but
> it also doesn't provide quite as much. For instance, GMP provides
> both signed and unsigned single digit functions [akin to my mp_add_d,
> mp_mul_d, etc...]. Though all of LibTomCrypt's three public key
> algorithms use the LibTomMath API and I can say it worked out well :-)
>
> Tom

Yes agree. I just wanted to be sure noone got the impression is was a
bad piece of work.

By the way,I found a comment in the 'lgorithms' section of the manual
that the cutover to Karabatsu (or whatever it is) 'cn be as little as 8
limbs'. This would translate to about 80+ digits, in the same ball park
as you.

The cutover to FFT method was huge, thousands of digits.

Tim Josling