N! modulo for large N

[Cyclamen Persicum]

Is there a fast algorithm to calculate N! modulo?

It is known that (N-1)! = -1 mod N -=*ONLY WHEN*=- N is prime itself. This identity is much better than the small Fermat theorem a^(N-1) = 1 mod N, which allows to find primes probabilisticly.
But N! modulo finds them deterministicly and doesn't requir many
tries with different witnesses.

[Maybeso]

I keep expecting one of the math gurus to field this one . . .

Actually, we can take it a step further:
(N-1)! = -1 mod N iff N is prime
(N-1)! == -1 mod N == (N-1) mod N
(N-1)!/(N-1) == 1 mod N
(N-2)! == 1 mod N iff N is prime

Let M = N-2
The slowest way to calculate M! is 2*3*4*5*...*(M-2)(M-1)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 speed-up.

I'm not trying to shoot you down, your idea does work. It's just not the fastest way, unless I'm missing something.

[xilman]

Originally posted by Cyclamen Persicum
Is there a fast algorithm to calculate N! modulo?

It is known that (N-1)! = -1 mod N -=*ONLY WHEN*=- N is prime itself. This identity is much better than the small Fermat theorem a^(N-1) = 1 mod N, which allows to find primes probabilisticly.
But N! modulo finds them deterministicly and doesn't requir many
tries with different witnesses.

If there were, there would be a fast algorithm to factor N into primes.

Think about it.

(Hint: calculate (2^i)mod N for i = 1, 2, ...,)


Paul