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.