20110813, 11:28  #1 
Jun 2003
4939_{10} Posts 
Factorial modulo a prime
1. What is the fastest known algorithm for computing a factorial modulo a prime?
2. What is the stateoftheart in implementing such an algorithm? 
20110813, 11:47  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
13×491 Posts 

20110814, 19:02  #3  
Mar 2011
Germany
90_{10} Posts 
Hi, I also just wanted to add something:
Quote:
http://www.google.com/url?sa=t&sourc...fV5Ug&cad=rja If you really mean the Wilson Prime Test (p1)! = 1 (mod p^2) then the paper fivemack pointed to is to my knowledge the fastest way, but only if you want to calculate it for a single prime. There is a way to speed up everything if you want to calculate a whole range, assuming you have enough memory. I programmed both methods, the fast but memory intensive variant using gmp and the reduced scheme from the paper. Both are much faster than the simple scheme from the Wilson Prime search project on Boinc (http://www.ibercivis.es/ , careful, this site is in Spanish only, project is well hidden). Source code for this project you find here: https://github.com/Ibercivis/Wilson I wrote an email to the developer for simple but very effective changes in the code for speedup (factor 4), but did not get an answer yet. If somebody is interested I can post my C++ source code and executables here for both variants I programmed. Cheers, Danilo Last fiddled with by MrRepunit on 20110814 at 19:05 

20110814, 20:16  #4 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 

20110814, 20:32  #5  
Mar 2011
Germany
1011010_{2} Posts 
Quote:
There is also no status or progress update on this project, a few days ago it was the only running project from this site, at least it was the only project I got some workunits. 

20110814, 20:36  #6 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
well I get everything that isn't a picture mostly or titles to links

20110814, 23:52  #7 
Mar 2011
Germany
2·3^{2}·5 Posts 
Well, I just noted that they created an English web page, so ignore my last statements on this.
http://www.ibercivis.net 
20110815, 05:57  #8  
Jun 2003
11×449 Posts 
Quote:
Quote:
I am interested. 

20110815, 08:43  #9 
Mar 2011
Germany
1011010_{2} Posts 
Wilson Prime Search Source Code
Okay, here you are.
Wilsonfast is the fast but memory intensive algorithm written in C. WilsonPrimeSearch is the implementation of the paper in C++, parts of it are based on the Wilson Prime Search Project of ibercivis. Executables for Linux 64 Bit (compiled under Ubuntu 11.04 64 Bit) are included. If there are some questions do not hesitate to ask. Cheers, Danilo 
20110815, 09:58  #10  
Jun 2003
11·449 Posts 
Quote:


20110815, 14:48  #11  
(loop (#_fork))
Feb 2006
Cambridge, England
13×491 Posts 
Quote:
(I take 800 microseconds to compute 103040! mod (10^9+7) by the stupid method, and it looks as if gp will take about 27 hours to do a pseudoprime test on 103040!+1, which suggests you only have time to trialfactor to 2^31 or so ... of course trialfactoring factorial primes has GPU written all over it in twelvefoot letters of fire) ie I wonder if it would be better to look at lots of potential factors simultaneously using quick arithmetic. But I'm sure you've investigated this already. Last fiddled with by fivemack on 20110815 at 14:49 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
World Record Factorial Prime Found  rogue  Lounge  8  20120302 16:41 
square root modulo prime  Raman  Math  1  20100216 21:25 
Order of 3 modulo a Mersenne prime  T.Rex  Math  7  20090313 10:46 
Period of Lucas Sequence modulo a prime  T.Rex  Math  7  20070604 21:30 
Conjecture about multiplicative order of 3 modulo a Mersenne prime  T.Rex  Math  9  20070326 17:35 