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