From: mpd@netcom.com (Mike Duvos)
Date: Fri, 23 Sep 94 12:25:56 PDT
To: cypherpunks@toad.com
Subject: Re: Fast Modular Factorial?
In-Reply-To: <EiUkmS600awSE3EGMO@andrew.cmu.edu>
Message-ID: <199409231923.MAA19299@netcom12.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Matthew J Ghio <mg5n+@andrew.cmu.edu> writes:

 > Nope.  The ability to take fast modular factorials as you
 > suggest implies the ability to factor large numbers in
 > polynomial time.

 > If (n!)mod x = 0 then there is a factor of x which is less
 > than n.  If you can solve modular factorials, then you can
 > solve for the largest factor of x in logarithmic time.
 > Obviously, nobody has found a method to do either.

I should mention that I am interested in the case (2^n)! mod p
where p is a prime and (2^n) << p.  In this case no individual
term of the factorial will be equal to zero mod p, and since the
non-zero residues form a group under multiplication, the result
can never be zero either.

The ability to solve this special case may also imply the ability
to factor large numbers in polynomial time, but in some less
obvious way.

-- 
     Mike Duvos         $    PGP 2.6 Public Key available     $