Re: I was right, surrogate factoring proof

From: Tim Peters (tim.one_at_comcast.net)
Date: 02/14/05 

Date: Sun, 13 Feb 2005 18:33:18 -0500

[ođin]
>> Factor T and j? How do you do it and hop long dos it take? You have not
>> proved that it is easier than factoring M.

[Décio Luiz Gazzoni Filho]
> If every valid j is allowed (other than requiring j to be even, JSH
> claims that any j will do),

Sorry, JSH fooled you this time: the algorithm he posted actually requires
j to be odd:

    Select j. ...

    If j is even, add 1.

So that destroys any method for finding M+j and M-j both prime, and in
particular nullifies your RSA2048 example (which used even j, as that
approach must use).

The smallest composite I found for which his new algorithm fails is M=25
with j=13 (the j he suggested using). But it does better than the last
method overall, presumably because it's trying twice as many gcd candidates.

If there's some reason for why squares "can't work", another small example
of failure is at M = 551 = 19*29 with j=3, where I get gcd=1 92 times and
gcd=551 4 times.

Remember that JSH seemingly never verifies his claims before posting them
with 100% confidence -- starting at the small end always finds
counterexamples quickly.

BTW, I've been running my M = 112554401 * 221667653 example in the
background while typing this, trying j after j after j, and it still hasn't
found one that works. Under the older method, the only success it had for
any j<=8000 for this M was at j=624. But this time even j aren't allowed,
so it's gotten well beyond the 600s this time without any success.

> then I have posted a polynomial-time algorithm for finding an admissible
> j.

Yup.

> However, it appears that not every j will yield a non-trivial
> factorization.

It's certain that it doesn't in the new method either, if he specified it
corrrectly and I programmed it correctly (and you know as well as I that
despite claims to the contrary, it's easy to implement).

> So, please, either find a valid point to complain about, or go back to
> meaningless insults. That one is no longer allowed.

Fully agreed that worrying about the factorization of T has long been
irrelevant in these threads.

Relevant Pages
Quantcast