### Re: Feedback from the LibTomMath Book?

[Originally I was going to make this a private reply but since I have a cool explanation of Karatsuba I'll share it with the group] --- Anton Stiglic [EMAIL PROTECTED] wrote: I think it looks pretty good!. Here are some comments: On page 82 you mention Fourier Transform based solutions, but don't describe any later on. It would be nice if you did. Two problems 1. I don't fully understand the FFT based solutions 2. I personally don't see the need for FFT in common day algorithms. Heck even Toom-Cook won't kick in until the numbers are very large. Recently I needed a fast Square-root routine, and found that not many libraries have one (OpenSSL has a mod square but not a straightforward square root function, GMP has a square-root but it doesn't seem to be fast, bc is faster than GMP for that...). If you could write something about that it would be nice. I think Karatsuba square root is good for that: http://www.inria.fr/rrrt/rr-3805.html Oddly enough, Zimmermann implemented this in GMP but I don't know why it's slow... I do include a Newton based root function which is fairly fast [haven't timed it against others]. I'll look into others. In section 6.2.4, equation 6.6., you wrote: f(x)*g(x) = acx^2 + ((a -b)(c-d) + ac + bd)x + bd That doesn't seem to work, since it gives acx^2 + a(c-d)x - b(c-d)x + acx + bdx + bd = acx^2 +acx -adx -bcx +bdx +acx + bdx +bd = acx^2 +2acx +2bdx -adx -bcx +bc Examine the terms. ac = W(oo) = 1W_2 + 0W_1 + 0W_0 bd = W(0) = 0W_2 + 0W_1 + 1W_0 The middle term (a - b)(c - d) can be written as (a_1 - a_0)(b_1 - b_0) = (-a(-1))(-b(-1)) = -\Zeta_{-1} Where a(x) = a_1*x + a_0 [same for b(x)] So -a(-1) == -(a_1 * -1 + a_0) == a_1 - a_0 This would give where W(x) == w_2 * x^2 + w_1 * x + w_0 -W(-1) = (-a(-1))(-b(1)) = -(w_2 * 1 + w_1 * -1 + w_0) = -w_2 + w_1 -w_0 Which combined gives you the matrix W(0) = 0 0 1 -W(-1) = -1 1 -1 W(oo) = 1 0 0 This means adding the two terms gives you the middle w_1 term. Hence the polynomial is actually correct. Alternatively you can use W(1) = w_2 + w_1 + w_0 = a(1)b(1) and subtract the first and third row from the middle. On the primality test section, maybe you should not that the Miller-Rabin test doesn't have any candidates that will pass the test for all bases (such as Carmichael numbers for the Fermat test). You should also talk about the probabilities, HAC, see in particular note 4.47 so as not to make the same mistake that allot of people make... You should understand that note very well. Will do. I wanted to get the book out the door quick so I just finished the pseudo code ... Continue the good work! Thanks, Tom __ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! http://sbc.yahoo.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Feedback from the LibTomMath Book?

Close to 100 people have downloaded the book so far [which is alot given the nature of the book] and although it has only been two days I was wondering if anyone has any initial impressions [good or bad]. I'm going to start the editing phase of the text fairly soon so I'd like to know what people thought of it before I got started. I won't repost the url since I don't want to spam the list [if you want it just email me in private]. Thanks, Tom __ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! http://sbc.yahoo.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]