[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
> 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.