Factorial modulo a prime

[axn]

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?

[fivemack]

I don't know anything cleverer than

http://citeseerx.ist.psu.edu/viewdoc...=rep1&type=pdf

[MrRepunit]

Hi, I also just wanted to add something:

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

[science_man_88]

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.

[MrRepunit]

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.

[science_man_88]

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

[MrRepunit]

Well, I just noted that they created an English web page, so ignore my last statements on this.
http://www.ibercivis.net

[axn]

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.

Originally Posted by MrRepunit

I programmed both methods, the fast but memory intensive variant using gmp and the reduced scheme from the paper.
<snip>
If somebody is interested I can post my C++ source code and executables here for both variants I programmed.

/raises hand.
I am interested.

[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.

Cheers,
Danilo

[axn]

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?

[fivemack]

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.