20031108, 11:28  #1 
Mar 2003
3^{4} Posts 
N! modulo for large N
Is there a fast algorithm to calculate N! modulo?
It is known that (N1)! = 1 mod N =*ONLY WHEN*= N is prime itself. This identity is much better than the small Fermat theorem a^(N1) = 1 mod N, which allows to find primes probabilisticly. But N! modulo finds them deterministicly and doesn't requir many tries with different witnesses. 
20031210, 00:22  #2 
Aug 2002
Portland, OR USA
2·137 Posts 
(N2)! == 1 mod N iff N is prime.
I keep expecting one of the math gurus to field this one . . .
Actually, we can take it a step further: (N1)! = 1 mod N iff N is prime (N1)! == 1 mod N == (N1) mod N (N1)!/(N1) == 1 mod N (N2)! == 1 mod N iff N is prime Let M = N2 The slowest way to calculate M! is 2*3*4*5*...*(M2)(M1)M. Using mod N will speed it up alot, but it's still really slow for large M. The three fastest algorithms use the prime factorization of M! to calculate it, which is all of the primes less than M each to a specific power. But to factor M you only need primes up to square root M. So in this case you would almost be factoring M^2 to generate M! to determine if M+2 is prime! If you're going to take the time to generate N!, it would be nice it end up with a prime ~= N!, rather than ~= N. That is why there is more interest in finding primes of the form N! +/ k, or N# +/ k, rather than using your equation. Now, if there is a fast algorithm to generate M! mod N in balanced base N, perhaps that would work. k = 2,3,..,M/2; F = F * k*k mod N. hmm, unless you can cancel out some of the iterations, I don't see much speedup. I'm not trying to shoot you down, your idea does work. It's just not the fastest way, unless I'm missing something. 
20031210, 10:52  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{5}×331 Posts 
Re: N! modulo for large N
Quote:
Think about it. (Hint: calculate (2^i)mod N for i = 1, 2, ...,) Paul 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Solving systems of equations modulo n  carpetpool  carpetpool  2  20170205 20:40 
Factorial modulo a prime  axn  Computer Science & Computational Number Theory  66  20110901 21:55 
modulo operation for polynomials?  smslca  Math  3  20110418 17:18 
Order of 3 modulo a Mersenne prime  T.Rex  Math  7  20090313 10:46 
The modulo operation, how is it computed?  eepiccolo  Math  7  20030108 03:07 