From: mpd@netcom.com (Mike Duvos)
Date: Fri, 23 Sep 94 09:37:02 PDT
To: cypherpunks@toad.com
Subject: Fast Modular Factorial?
Message-ID: <199409231634.JAA05777@netcom15.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


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     $
     mpd@netcom.com     $    via Finger.                      $