Fast Modular Factorial?
Paul J. Ste. Marie
pstemari at bismark.cbis.com
Mon Sep 26 10:25:39 PDT 1994
> > 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.
More information about the Testlist
mailing list