mersenneforum.org Other mersenne progs, why so slow?
 Register FAQ Search Today's Posts Mark Forums Read

 2003-03-24, 11:02 #34 cperciva   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.
 2003-03-25, 10:35 #35 Cyclamen Persicum     Mar 2003 34 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 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...
2003-03-25, 17:00   #36
ewmayer
2ω=0

Sep 2002
República de California

1167610 Posts

Quote:
 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.

2003-03-25, 18:37   #37
cperciva

Oct 2002

2B16 Posts

Quote:
 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.

2003-03-26, 09:34   #38
Cyclamen Persicum

Mar 2003

34 Posts

Quote:
 1024 and 24 are not relatively prime
Thanks a lot! 3^7-1187 does really work.

 Similar Threads Thread Thread Starter Forum Replies Last Post Unregistered Information & Answers 19 2012-04-17 03:12 R.D. Silverman GMP-ECM 55 2011-10-16 17:28 petrw1 Hardware 13 2008-11-10 23:25 Housemouse Hardware 7 2008-02-15 18:18 Doorbasher Hardware 5 2004-08-23 22:18

All times are UTC. The time now is 20:06.

Sat Dec 4 20:06:02 UTC 2021 up 134 days, 14:35, 1 user, load averages: 0.92, 0.95, 0.99