mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2011-08-13, 11:28   #1
axn
 
axn's Avatar
 
Jun 2003

2·5·479 Posts
Question 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?
axn is online now   Reply With Quote
Old 2011-08-13, 11:47   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11000111010002 Posts
Default

I don't know anything cleverer than

http://citeseerx.ist.psu.edu/viewdoc...=rep1&type=pdf
fivemack is offline   Reply With Quote
Old 2011-08-14, 19:02   #3
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

23×11 Posts
Default

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
MrRepunit is offline   Reply With Quote
Old 2011-08-14, 20:16   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
careful, this site is in Spanish only, project is well hidden).
google chrome can translate it on the fly I bet.
science_man_88 is offline   Reply With Quote
Old 2011-08-14, 20:32   #5
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

23×11 Posts
Default

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.
MrRepunit is offline   Reply With Quote
Old 2011-08-14, 20:36   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-08-14, 23:52   #7
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

23·11 Posts
Default

Well, I just noted that they created an English web page, so ignore my last statements on this.
http://www.ibercivis.net
MrRepunit is offline   Reply With Quote
Old 2011-08-15, 05:57   #8
axn
 
axn's Avatar
 
Jun 2003

2·5·479 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
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 View Post
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.
axn is online now   Reply With Quote
Old 2011-08-15, 08:43   #9
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

23·11 Posts
Default 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
File Type: zip WilsonPrimeSearch.zip (18.5 KB, 169 views)
MrRepunit is offline   Reply With Quote
Old 2011-08-15, 09:58   #10
axn
 
axn's Avatar
 
Jun 2003

112668 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
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?
axn is online now   Reply With Quote
Old 2011-08-15, 14:48   #11
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

23×797 Posts
Default

Quote:
Originally Posted by axn View Post
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
fivemack is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
World Record Factorial Prime Found rogue Lounge 8 2012-03-02 16:41
square root modulo prime Raman Math 1 2010-02-16 21:25
Order of 3 modulo a Mersenne prime T.Rex Math 7 2009-03-13 10:46
Period of Lucas Sequence modulo a prime T.Rex Math 7 2007-06-04 21:30
Conjecture about multiplicative order of 3 modulo a Mersenne prime 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.