[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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 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.