Re: Fast Modular Factorial?

[chen@intuit.com (Mark Chen)]

> I find that for the numbers I have tried, that (p-1)! mod p = (p-1) if
> p is prime, else it equals 0, with one exception (p=4).  So if this
> is true (probably a standard result; it sounds familiar) then it might
> actually be easier to find the factorial of a larger number mod a
> prime than a smaller one.

Using "~" to mean congruence, and "L()" as the Legendre symbol, the
general rule is:

(p - 1)! ~ -L(a/p)a^((p - 1)/2) mod p.

L(a/p) will equal 1 or -1, depending on whether or not a is a
quadratic residue mod p.

The result stems from Euler's criterion.

   - Mark -


--
Mark Chen 
chen@netcom.com
415/329-6913
finger for PGP public key
D4 99 54 2A 98 B1 48 0C  CF 95 A5 B0 6E E0 1E 1D