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

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.

> 
> 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.
> 
Just some thoughts...

If x < n then (n!)modx will always be 0. Since n! is simply the product of
the numbers 1...n and is always a integer product dividing by x simply
removes the factor m such that we have the product of 1...m-1,m+1...n.

If x>n and x is not a prime then the result will again always be 0 since
we can break x down into factors smaller than n and the previous argument
removes the various factors.

If x is prime and x>n then we will get a result that is non-zero.

Take care.

Jim choate <ravage@bga.com> wrote:

> Just some thoughts...
> 
> If x < n then (n!)modx will always be 0. Since n! is simply the product of
> the numbers 1...n and is always a integer product dividing by x simply
> removes the factor m such that we have the product of 1...m-1,m+1...n.

And there will always be such a value for m equal to kx where k is an
integer less than n/x
If x is non-prime, there may be factors f and g such that f*g=x.  In
that case, if n>f and n>g then n=0, hence finding the smallest value of
n such that (n!)mod x =0, will yeild a factor of x.  In that case,
dividing by x would remove the factors f and g, yeilding a zero
remainder.

> If x>n and x is not a prime then the result will again always be 0 since
> we can break x down into factors smaller than n and the previous
> argument removes the various factors.
> 
> If x is prime and x>n then we will get a result that is non-zero.

Yes, but if x is not prime, and x>n, (n!)mod x will not necessarily be
zero, unless x>n>x/2


A few examples:

mod 7:
 n   1  2  3  4  5  6  7  8  9 10
 n!  1  2  6  3  1  6  0  0  0  0

mod 15:
 n   1  2  3  4  5  6  7  8  9 10
 n!  1  2  6  9  0  0  0  0  0  0


Note that for mod 15, n=>5 produces only zeros, revealing the factor 5.

> > 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.
> > 
> Just some thoughts...

	...

> If x>n and x is not a prime then the result will again always be 0 since
> we can break x down into factors smaller than n and the previous argument
> removes the various factors.

This doesn't work--(x > n) & x not prime doesn't imply that x has a
factor less than n.  That's only true if sqrt(x) >= n.

Matthew J Ghio <mg5n+@andrew.cmu.edu> writes:

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

I should mention that I am interested in the case (2^n)! mod p
where p is a prime and (2^n) << p.  In this case no individual
term of the factorial will be equal to zero mod p, and since the
non-zero residues form a group under multiplication, the result
can never be zero either.

The ability to solve this special case may also imply the ability
to factor large numbers in polynomial time, but in some less
obvious way.

-- 
     Mike Duvos         $    PGP 2.6 Public Key available     $