[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected] (Matthew J Ghio)*Subject*: Re: Fast Modular Factorial?*From*: Jim choate <[email protected]>*Date*: Fri, 23 Sep 1994 12:55:34 -0500 (CDT)*Cc*: [email protected]*In-Reply-To*: <[email protected]> from "Matthew J Ghio" at Sep 23, 94 01:13:02 pm*Sender*: [email protected]

> > 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. Take care.

**Follow-Ups**:**Re: Fast Modular Factorial?***From:*Matthew J Ghio <[email protected]>

**Fast Modular Factorial?***From:*[email protected] (Paul J. Ste. Marie)

**References**:**Re: Fast Modular Factorial?***From:*Matthew J Ghio <[email protected]>

- Prev by Date:
**Re: National Research Council** - Next by Date:
**crypt program** - Prev by thread:
**Re: Fast Modular Factorial?** - Next by thread:
**Re: Fast Modular Factorial?** - Index(es):