mersenneforum.org Factorial modulo a prime
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2011-08-13, 11:28 #1 axn     Jun 2003 2·5·479 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 11000111010002 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:
http://www.google.com/url?sa=t&sourc...fV5U-g&cad=rja

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

838410 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 23·11 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

2·5·479 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

23·11 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, 169 views)

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

Jun 2003

112668 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

23×797 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

 Thread Tools

 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 01:54.

Thu Dec 3 01:54:39 UTC 2020 up 83 days, 23:05, 1 user, load averages: 2.66, 2.36, 2.14

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.