[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Fast Modular Factorial?

[email protected] (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.