Other mersenne progs, why so slow?

[cperciva]

You're right; it only works if you can find appropriate values for a and b. The usefulness comes from the fact that most big numbers we work with are already in that form: Mersenne numbers, Fermat numbers, Proth numbers, etc are all of the form [something big with a small number of distinct prime factors] +/- 1.

[Cyclamen Persicum]

What a crazy stupid rat paranoid am I!!!
Example modulo 1000 does not still work!

Let's multiply 123 by 543 mod 1000.
We are going to use 4-digit FFT.

1000=1024-24.
Then
a = 2^10,
b = 2^3*3

Radix vector is:
(1 4 16 32)

Weight wector is:
(1 6^(1/4) 6^(1/2) 3^(3/4)*2^(-1/4) ),
or
(1.00000000000000 1.56508458007329 2.44948974278318 1.91682931273882)


123 and 543 in radix form are:
(3 2 1 3)
and
(3 3 1 16)

Weighted convolution gives:
(138 72 84 67)

That's 3914

What's the hell?
Please, point me on errors...

[ewmayer]

Originally Posted by Cyclamen Persicum

Example modulo 1000 does not still work!

I suggest you work through the length-4 example in the Crandall/Fagin paper
(where the results are known) first, then see about generalizing to other types of moduli.

[cperciva]

Originally Posted by Cyclamen Persicum

What's the hell?
Please, point me on errors...

1024 and 24 are not relatively prime. You're correctly computing 543*123 modulo (1000/24), but since 1000 and 24 share a factor of 8, this only gives you the value modulo 125 instead of modulo 1000.

[Cyclamen Persicum]

1024 and 24 are not relatively prime

Thanks a lot! 3^7-1187 does really work.