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"

Relevant Pages

  • Re: Factoring problem, my assertion revisited
    ... making the factorization of T *too* easy. ... I can understand Rick Decker easily enough, but JSH keeps calling ... > online buddy, ... Rick "the liar" ...
    (sci.crypt)
  • Re: I was right, surrogate factoring proof
    ... JSH fooled you this time: the algorithm he posted actually requires ... The smallest composite I found for which his new algorithm fails is M=25 ... so it's gotten well beyond the 600s this time without any success. ... Fully agreed that worrying about the factorization of T has long been ...
    (sci.crypt)
  • Re: JSH: Mathematical proof of factoring problem solution
    ... JSH writes: ... factorization just gives you two cases for the factors: ... You know that when you submit this for publication the reviewers are ...
    (sci.crypt)