[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Fast Modular Factorial?
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?
--
Mike Duvos $ PGP 2.6 Public Key available $
[email protected] $ via Finger. $