Fast Modular Factorial?
Mark Chen
chen at intuit.com
Fri Sep 23 17:07:53 PDT 1994
> 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 at 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
More information about the cypherpunks-legacy
mailing list