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