[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]
