Re: Factoring problem, my assertion revisited

From: Rick Decker (rdecker_at_hamilton.edu)
Date: 02/08/05 

Date: Tue, 08 Feb 2005 17:06:02 -0500

Tim Peters wrote:

<snip>
>
>>So it seems that your idea depends on a false assumption. But probably, T
>>is no easier to factor than M.
>
>
> T factors at once as (M+j)*(M-j). Both factors are about the size of M, but
> j can be chosen in various special ways. For example, Décio Luiz Gazzoni
> Filho pointed out that it's probably possible to find a j efficiently such
> that M+j and M-j are both prime, and I noted quite a while ago that you
> could, e.g., pick j s.t. M+j is the next larger power of 2 (so M+j factors
> trivially, and then M and j are both odd so that 2 | M-j so we've peeled at
> least 1 bit off the largest integer remaining to be factored).

Right. However, there are problems with James' method that work against
making the factorization of T *too* easy. In particular, a candidate
factorization has to satisfy a condition involving quadratic residues
mod primes dividing M. That means that with too small a set of candidate
factors you might very well not get any useful ones at all.
>
> But I can't make head or tail out of JSH's method after the point T is
> factored. I can understand Rick Decker easily enough, but JSH keeps calling
> him a liar (for no reason I can discern, apart from JSH's frequently
> irrational online behavior); and JSH won't answer questions or even flesh
> out how he expects to factor 15 as a concrete example -- he's his best
> online buddy, and his worst online enemy.
>

I'm pretty sure I've posted a sample using James' method to factor 15.
I have another one factoring 391 if anyone's interested.

Regards,

Rick "the liar"

Loading