Re: Proof factoring solution is closed form

From: Nora Baron (norabaron_at_hotmail.com)
Date: 02/11/05 

Date: 11 Feb 2005 11:52:31 -0800

Tim Peters wrote:
> [Nora Baron, to JSH]
> [...]
> > Whether your approach to factoring leads to anything remains to
> > be seen. You replace factoring a large number M with factoring of
> > a number T = M^2 - j^2, where in general you might choose j to be
> > relatively small. There are two possibilities regarding T which
> > need to be considered. One is that it has two or more extremely
> > large prime factors, very possibly with almost twice the
digit-length
> > of the factors of M itself.
>
> M^2-j^2 = (M+j)*(M-j), so nothing as large as 2*M remains to be
factored in
> T.
>

  Oops, you're right, of course.

> Pick any odd j, 0 < j < M, and both halves are even, and the largest
> remaining piece (after dividing out 2s) is smaller than M. Pick an
even j
> s.t. M+j and M-j are both prime (a strong argument was made by Décio
Luiz
> Gazzoni Filho that this can probably be done efficiently),
>

  I would think so, with an efficient prime-testing routine.

> and then there's
> nothing at all left in T to factor; this one would also address your
next
> point. Other interesting ways to pick j have been suggested too --
I'm not
> worried about factoring T (but then I don't think a factoring
algorithm has
> to be poly-time in all cases, or even succeed in all cases, to be a
major
> advance in the factoring art).
>

  Certainly I agree with that.

> [...]
> > Two is the possibility that T has a great many small prime factors.
> > In that case, the number of possible integer divisors of T could be
> > very large, and searching through all of them might take as much
> > time as factoring M in the first place, and may not work anyway.
>
> "May not work anyway" is the rub, of course. I'm not sure exactly
which of
> JSH's methods you have in mind, but the one Rick wrote about (which
is no
> longer the current one) definitely doesn't succeed for many <M, j>
pairs,
> and empirical evidence suggests it's harder to find a j that works
the
> larger M gets. Factoring by random trial gcd appears at least as
effective.
> JSH recently even seemed to agree that method doesn't always work.
>

  I don't think random trial division has much chance when you are
dealing with an RSA number, unless I am missing something.

> > You do not have a proof that it has to work.
>
> He says he does for the latest variation. Didn't look like a proof
to me,
> but what do I know; he said he had proofs for all the other
non-working
> variations too, and they didn't look like proofs to me either, so I'm
not
> crushed -- heh.
>

  He has never produced a rigorous proof of anything of importance.
It may take weeks to figure out what he is thinking - his own
exposition is worthless if not misleading - and prove it or disprove
it.

> > You do not have a proof that it has to work in polynomial time.
>
> Oh, come on. Here's a recent example of JSH O() analysis:
>
> Now I've actually calculated, while you appear to be trying to
> convince others to ignore my work without even bother to give
> mathematics, and my calculations show that if you form a number
by
> multiplying the first one thousand primes together you get about
> 150 million combinations by two's.
>
> From context "by two's" appears to mean the number of ways to express
the
> product of those 1000 primes as the product of 2 integers each > 1,
and
> counting a*b and b*a as being the same split. For 1000 primes, of
course
> there are 2^999-1 ~= 5.4*10^300 ways to do that (pick a subset and
call it
> L; put the leftovers in R; 2^1000 ways to do that; divide by 2
because we
> counted <L, R> and <R, L> as distinct but don't want to; subtract 1
to
> ignore the two original cases where L or R was empty). 150 million
is a bit
> more than 2^27, close to the right answer if there were only 28
primes.
>

  Right. That's a worst case.

> In another message:
>
> Now for some large number the number of combinations would be
> huge, but they'd be certain of success if they cycled through
> them all.
>
> And that's a polynomial time problem, as the equation defining
how
> many combinations of those factors there are is a polynomial one.
>

  He has no idea what polynomial time is. Maybe he thinks it's
like Miller time.

> AFAICT, he never revealed "the equation" he used to come up with
these goofy
> results, but in a world where 200+ orders of magnitude discrepancies
with
> reality don't bother you, ya, lots of things are arguably poly-time
<wink>.
> Or maybe he undertood that this is an O(2^n) process, simply blew the

> concrete calculation in the n=1000 example, and sincerely thinks 2^n
is "a
> polynomial in 2" in the intended sense. Don't know; don't really
care; but
> asking JSH to prove something he's so ill-equipped to even bluff
about would
> just be cruel.
>
> > The real test for you is, can you factor a sizeable RSA number?
>
> Not yet, but soon. Very soon. This time it's "easily implemented"
(not
> sure what that means, since the algorithm Rick gave was in fact very
easy to
> implement -- the only part that required any thought was generating
all the
> unique splittings of -j^2*T's factors efficiently in all cases). And
this
> time "the math is childishly simple" (not sure how that differs from
the
> claim for the last one either).
>

  I do not discount the possibility that his idea might lead to
a quick factorization of some fraction of RSA numbers. However,
he has now let so much of the cat out of the bag that it may well
be someone else who gets there first - someone who can program
more efficiently and make use of shortcuts, etc.. If I were him
right now I would be very worried that I had said too much.

  Conceivably it can be shown that his scheme is a variant of trial
division and has no advantage over it. I don't see an obvious
proof of that, but it is possible. I would guess not.

> [...]
>
> > You made a barbarically rude comment to Rick Decker. He has
> > been unfailingly polite and reasonsble and has done a far
> > better job than you have yourself of explaining what you are
> > trying to do. You pay him back with sheer meanness. You
> > should be ashamed, and you owe him an apology.
>
> 100% agreed on 100% of that.

  This too is a test. If someone else beats him to the factoring
punch and he is denied all the credit or at least the monetary prize,
it will be partly because he is so incredibly spiteful.

  Nora B.

Relevant Pages