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

*To*: Cypherpunks Mailing List <[email protected]>*Subject*: Re: Fast Modular Factorial?*From*: Matthew J Ghio <[email protected]>*Date*: Fri, 23 Sep 1994 15:13:08 -0400 (EDT)*In-Reply-To*: <[email protected]>*References*: <[email protected]>*Sender*: [email protected]

Jim choate <[email protected]> wrote: > 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. And there will always be such a value for m equal to kx where k is an integer less than n/x If x is non-prime, there may be factors f and g such that f*g=x. In that case, if n>f and n>g then n=0, hence finding the smallest value of n such that (n!)mod x =0, will yeild a factor of x. In that case, dividing by x would remove the factors f and g, yeilding a zero remainder. > 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. Yes, but if x is not prime, and x>n, (n!)mod x will not necessarily be zero, unless x>n>x/2 A few examples: mod 7: n 1 2 3 4 5 6 7 8 9 10 n! 1 2 6 3 1 6 0 0 0 0 mod 15: n 1 2 3 4 5 6 7 8 9 10 n! 1 2 6 9 0 0 0 0 0 0 Note that for mod 15, n=>5 produces only zeros, revealing the factor 5.

**References**:**Re: Fast Modular Factorial?***From:*Jim choate <[email protected]>

- Prev by Date:
**Re: IBM-Led Consortium. Any thoughts?** - Next by Date:
**Re: Fast Modular Factorial?** - Prev by thread:
**Re: Fast Modular Factorial?** - Next by thread:
**Fast Modular Factorial?** - Index(es):