From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
Date: Fri, 23 Sep 94 10:18:30 PDT
To: mpd@netcom.com (Mike Duvos)
Subject: Re: Fast Modular Factorial?
In-Reply-To: <199409231634.JAA05777@netcom15.netcom.com>
Message-ID: <EiUkmS600awSE3EGMO@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain


mpd@netcom.com (Mike Duvos) wrote:

> A small question about large integer math...
> 
> We are all familar with the fact that x^(2^n) mod p may be
> evaluated with only n modmults which accumulate
> geometrically increasing powers of x.
> 
> Does a similar fast algorithm exist for computing (2^n)! mod p?
> 
> The only difference here is that one is accumulating a huge
> product of consecutive integers instead of the same integer
> multiplied many times.  I am interested in values of n
> around several hundred.
> 
> I have played with this quite a bit and am unable to see any
> easy exploitable symmetry which would lead to an efficient
> algorithm.
> 
> Any ideas?

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.