From: Matthew J Ghio <mg5n+@andrew.cmu.edu>

To: Cypherpunks Mailing List <cypherpunks@toad.com>

Message Hash: 79a4d0c21d5c1a7a73588c33900403562eaf6b4484127274bb3e9f0478d17e91

Message ID: <YiUmX4i00VohMD1kkn@andrew.cmu.edu>

Reply To: <199409231755.MAA03386@zoom.bga.com>

UTC Datetime: 1994-09-23 19:14:12 UTC

Raw Date: Fri, 23 Sep 94 12:14:12 PDT

```
From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
Date: Fri, 23 Sep 94 12:14:12 PDT
To: Cypherpunks Mailing List <cypherpunks@toad.com>
Subject: Re: Fast Modular Factorial?
In-Reply-To: <199409231755.MAA03386@zoom.bga.com>
Message-ID: <YiUmX4i00VohMD1kkn@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain
Jim choate <ravage@bga.com> 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.
```

Return to September 1994

- Return to “Jim choate <ravage@bga.com>”
- Return to “Matthew J Ghio <mg5n+@andrew.cmu.edu>”
- Return to “mpd@netcom.com (Mike Duvos)”
Return to “pstemari@bismark.cbis.com (Paul J. Ste. Marie)”

- 1994-09-23 (Fri, 23 Sep 94 09:37:02 PDT) - Fast Modular Factorial? -
*mpd@netcom.com (Mike Duvos)*- 1994-09-23 (Fri, 23 Sep 94 10:18:30 PDT) - Re: Fast Modular Factorial? -
*Matthew J Ghio <mg5n+@andrew.cmu.edu>*- 1994-09-23 (Fri, 23 Sep 94 10:56:02 PDT) - Re: Fast Modular Factorial? -
*Jim choate <ravage@bga.com>*- 1994-09-23 (Fri, 23 Sep 94 12:14:12 PDT) - Re: Fast Modular Factorial? -
*Matthew J Ghio <mg5n+@andrew.cmu.edu>* - 1994-09-26 (Mon, 26 Sep 94 10:25:39 PDT) - Fast Modular Factorial? -
*pstemari@bismark.cbis.com (Paul J. Ste. Marie)*

- 1994-09-23 (Fri, 23 Sep 94 12:14:12 PDT) - Re: Fast Modular Factorial? -
- 1994-09-23 (Fri, 23 Sep 94 12:25:56 PDT) - Re: Fast Modular Factorial? -
*mpd@netcom.com (Mike Duvos)*

- 1994-09-23 (Fri, 23 Sep 94 10:56:02 PDT) - Re: Fast Modular Factorial? -

- 1994-09-23 (Fri, 23 Sep 94 10:18:30 PDT) - Re: Fast Modular Factorial? -