cryptoanarchy.wiki

Arise, you have nothing to lose but your barbed wire fences!

1994-09-26 - Fast Modular Factorial?

Header Data

From: pstemari@bismark.cbis.com (Paul J. Ste. Marie)
To: ravage@bga.com
Message Hash: 248959edb7fe1a10acef63adbc52ca2734114dce53c2f85756b3f1d9737443e6
Message ID: <9409261722.AA27286@focis.sda.cbis.COM>
Reply To: <199409231755.MAA03386@zoom.bga.com>
UTC Datetime: 1994-09-26 17:25:39 UTC
Raw Date: Mon, 26 Sep 94 10:25:39 PDT

Raw message

From: pstemari@bismark.cbis.com (Paul J. Ste. Marie)
Date: Mon, 26 Sep 94 10:25:39 PDT
To: ravage@bga.com
Subject: Fast Modular Factorial?
In-Reply-To: <199409231755.MAA03386@zoom.bga.com>
Message-ID: <9409261722.AA27286@focis.sda.cbis.COM>
MIME-Version: 1.0
Content-Type: text/plain


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

Thread