[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Fast Modular Factorial?
> 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.