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