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 cypherpunks-legacy mailing list