Re: Factorizaton idea, revisited

From: Gary Shannon (fiziwig_at_yahoo.com)
Date: 04/29/04 

Date: 29 Apr 2004 13:42:46 -0700

jstevh@msn.com (James Harris) wrote in message news:<3c65f87.0404290446.73a1c6e4@posting.google.com>...

<snip>

>
> > I hate to be such a bother, but I'm not real strong on theory. I have
> > to see a solved example before I'll believe it.
>
> There's nothing to believe, and I hope you haven't spent a lot of time
> on this, as I'm kind of speculating.

I spend about 2 minutes with UBASIC.

> See I figured that it'd be
> easier to factor some number off of M, the number to be factored, so
> I've been trying out these factorizations.
>
> This one looked kind of nice so I've posted about it.

If you want to find a fast way to factor a number all you have to do
is find a fast way to generate (x! mod y) without having to perform x
multiplications. Then a number could be instantly factored by
computing gcd(N, sqrt(N)! mod N).

Algebraic factorization of the type you are playing with has been very
thoroughly explored and is of limited usefulness at best.

Check Prime Numbers and Computer Methods for Factorization by Hans
Riesel, my favorite book on the subject. He hypothesizes that if a
REALLY fast general factorization algorithm is every discovered it
will probably be based on finding modular factorials or modular
binomial coefficients quickly.

--gary