20030324, 11:02  #34 
Oct 2002
43 Posts 
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.

20030325, 10:35  #35 
Mar 2003
3^{4} Posts 
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 4digit FFT. 1000=102424. 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... 
20030325, 17:00  #36  
∂^{2}ω=0
Sep 2002
República de California
11676_{10} Posts 
Quote:
(where the results are known) first, then see about generalizing to other types of moduli. 

20030325, 18:37  #37  
Oct 2002
2B_{16} Posts 
Quote:


20030326, 09:34  #38  
Mar 2003
3^{4} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
why is http://www.mersenne.org/ so slow  Unregistered  Information & Answers  19  20120417 03:12 
Slow Down?  R.D. Silverman  GMPECM  55  20111016 17:28 
How hot is too hot? Slow is too slow?  petrw1  Hardware  13  20081110 23:25 
Slow computer  Housemouse  Hardware  7  20080215 18:18 
Really slow machines?  Doorbasher  Hardware  5  20040823 22:18 