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.
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.
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.
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 $
participants (4)
-
Jim choate -
Matthew J Ghio -
mpd＠netcom.com -
pstemari＠bismark.cbis.com