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]

```