[13720] in cryptography@c2.net mail archive
Re: Feedback from the LibTomMath Book?
daemon@ATHENA.MIT.EDU (tom st denis)
Sat Jun 28 18:38:58 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Fri, 27 Jun 2003 15:04:19 -0700 (PDT)
From: tom st denis <tomstdenis@yahoo.com>
To: cryptography@metzdowd.com
In-Reply-To: <00a601c33cf1$a279c4e0$4300a8c0@p1038mobile>
[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 <astiglic@okiok.com> 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 majordomo@metzdowd.com
