mersenneforum.org Factorial modulo a prime
 Register FAQ Search Today's Posts Mark Forums Read

 2011-08-13, 11:28 #1 axn     Jun 2003 3·5·17·19 Posts Factorial modulo a prime 1. What is the fastest known algorithm for computing a factorial modulo a prime? 2. What is the state-of-the-art in implementing such an algorithm?
 2011-08-13, 11:47 #2 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 6,379 Posts I don't know anything cleverer than http://citeseerx.ist.psu.edu/viewdoc...=rep1&type=pdf
2011-08-14, 19:02   #3
MrRepunit

Mar 2011
Germany

23×11 Posts

Hi, I also just wanted to add something:

Quote:
 1. What is the fastest known algorithm for computing a factorial modulo a prime? 2. What is the state-of-the-art in implementing such an algorithm?
If you mean just the normal wilson prime test (p-1)! = -1 (mod p) then this paper might be of interest for you:

If you really mean the Wilson Prime Test (p-1)! = -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 2011-08-14 at 19:05

2011-08-14, 20:16   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by MrRepunit careful, this site is in Spanish only, project is well hidden).
google chrome can translate it on the fly I bet.

2011-08-14, 20:32   #5
MrRepunit

Mar 2011
Germany

23×11 Posts

Quote:
 google chrome can translate it on the fly I bet.
Yes, but not everything, give it a try.
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.

2011-08-14, 20:36   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by MrRepunit Yes, but not everything, give it a try. 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.
well I get everything that isn't a picture mostly or titles to links

 2011-08-14, 23:52 #7 MrRepunit     Mar 2011 Germany 1308 Posts Well, I just noted that they created an English web page, so ignore my last statements on this. http://www.ibercivis.net
2011-08-15, 05:57   #8
axn

Jun 2003

3×5×17×19 Posts

Quote:
 Originally Posted by MrRepunit There is a way to speed up everything if you want to calculate a whole range, assuming you have enough memory.
I'm looking at the profitability of doing trial factoring on a single/small group factorial prime candidate.

Quote:
 Originally Posted by MrRepunit I programmed both methods, the fast but memory intensive variant using gmp and the reduced scheme from the paper. If somebody is interested I can post my C++ source code and executables here for both variants I programmed.
/raises hand.
I am interested.

2011-08-15, 08:43   #9
MrRepunit

Mar 2011
Germany

10110002 Posts
Wilson Prime Search Source Code

Okay, here you are.
Wilson-fast 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
Attached Files
 WilsonPrimeSearch.zip (18.5 KB, 181 views)

2011-08-15, 09:58   #10
axn

Jun 2003

3·5·17·19 Posts

Quote:
 Originally Posted by MrRepunit Okay, here you are. Wilson-fast 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.
Do you have benchmark numbers for these programs?

2011-08-15, 14:48   #11
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

6,379 Posts

Quote:
 Originally Posted by axn I'm looking at the profitability of doing trial factoring on a single/small group factorial prime candidate.
If you're doing this you'll have written already an efficient 'compute the product of this large set of small numbers' routine, and I would suspect that getting GMP to compute GCD(103040!+1, product of primes between 10^9 and 10^9+10^6) might well be quicker than computing 103040! mod P by stupid multiplication for each P in the range.

(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 trial-factor to 2^31 or so ... of course trial-factoring factorial primes has GPU written all over it in twelve-foot 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 2011-08-15 at 14:49

 Similar Threads Thread Thread Starter Forum Replies Last Post rogue Lounge 8 2012-03-02 16:41 Raman Math 1 2010-02-16 21:25 T.Rex Math 7 2009-03-13 10:46 T.Rex Math 7 2007-06-04 21:30 T.Rex Math 9 2007-03-26 17:35

All times are UTC. The time now is 08:58.

Sat Jan 23 08:58:17 UTC 2021 up 51 days, 5:09, 0 users, load averages: 1.75, 1.67, 1.62