Re: Fast Modular Factorial?

[Matthew J Ghio <mg5n+@andrew.cmu.edu>]

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.