From: chen@intuit.com (Mark Chen)
Date: Fri, 23 Sep 94 17:07:53 PDT
To: hfinney@shell.portal.com (Hal)
Subject: Re: Fast Modular Factorial?
In-Reply-To: <199409232305.QAA13709@jobe.shell.portal.com>
Message-ID: <9409240007.AA15297@doom.intuit.com>
MIME-Version: 1.0
Content-Type: text/plain



> 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