Feedback from the LibTomMath Book?

[tom st denis]

[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 at 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 at metzdowd.com