Re: Proof factoring solution is closed form

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

Date: Sat, 12 Feb 2005 02:00:15 -0500

[Tim Peters]
[...]
>> "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.

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

Right! If the composite is M=p*q with both factors prime and p != q, then
the probability that gcd(M, k) will reveal p or q, for a random integer k,
is approximately (precision depends on details of how k is chosen)
(p+q-2)/M. In an RSA-class composite, M is so large compared to p+q this is
negligible. But for the relatively small composites anyone here (including
JSH) has reported details about so far, the probability of factoring by pure
luck via random-gcd in a second of computer time is about 1.0 (but for an
RSA-class composite, is equally close to 0.0). I'll discuss a larger
example below.

In program experiments I wrote up (& posted here) for Rick, it was noted a
few times that the number of gcds performed by Rick's formulation of
"surrogate factoring" before finding a factor was larger than the number I
would have expected had I been picking gcd candidates at random. Of course
that doesn't prove anything, it's just suggestive (hence the "appears" in
"appears at least as effective" above) -- although if I were counting time
rather than # of gcds, poking at random would have been _much_ more
effective.

On the other hand ... last night I thought I'd try one non-utterly-trivial
composite just for fun, and out of thin air picked

M = 24949669904490853 = 112554401 * 221667653

After trying that with all j in 1 through 600, it hadn't found a factor, and
I was about to kill program. By that time:

+ It had fully factored 2*600 = 1200 other numbers about the size of M
  (all integers in [M-600, M+600] except for M -- & of course I used a
  different method for those factorizations).

+ It had computed 5,439,476 gcds while thrashing around with those
  1200 factorizations.

and all that is expensive. Then _just_ as I was reaching to hit Ctrl+C, it
found a factor, at j=624:

    gcd(24949669904490853, -5261514495380026 + # g1
                           46066796924142927777408 + # g2
                           778752) # 2j^2

is indeed 221667653. There are 2592 distinct ways to express -T*j^2 as
g1*g2 at j=624, and this was the only split that gave a factor at any j <=
624, but it was undeniably a success. The ~6 million gcds it took to get
there was a lot less than the ~75 million gcds I'd expect random poking to
take for this M.

So that was exciting -- or would have been, if I weren't so resigned to
skepticism by a seemingly endless lifetime of shattered dreams <wink>.

I let the program keep running, and through j=8000 that was _still_ the only
time the method succeeded. I gave up then. At that point it had done
122,375,356 gcds, and based on 1 success out of 122 million tries, the idea
that it behaves no better than random-gcd can't be rejected here after all.

[...]
> I do not discount the possibility that his idea might lead to
> a quick factorization of some fraction of RSA numbers.

Well, it's almost certain to, if we try enough of 'em <wink>.

> 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.

Sssshhhh! I don't want him harassing my employer when I cash the RSA
challenge checks.

> 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.

In the special case M=p^2 (a primed squared), I believe it can be proved(*)
that j is a winner if and only if p divides j. In that case, the set of
winning j is equal to the set of all k in 1..M-1 such that 1 < gcd(M, k) <
M. In other words, in this special case, the method succeeds at exactly the
same values random-gcd succeeds, and there's obviously no way to choose a
winning j without knowing p first. Random-gcd wins decisively then, because
it's very much faster: when you pick a winning j with random-gcd, you win
at once. But when you pick a winning j with this other method, you still
have to factor two other numbers, and plow through a potentially large
number of ways to split -j^2*T's factors until you hit one where the gcd
"works".

(*) It's easy to prove one direction of that, and I confirmed the other
    direction by computer for increasing p until I got bored. I don't
    believe it would be difficult to prove, but can't screw up enough
    interest to finish it.

Anyway, if that's right, the method is provably of no possible value in that
special case. Combined with that an increasing number of computer
experiments have found no reason to suspect it does better in other cases,
and especially with that there's no compelling reasoning in JSH's argument,
and the chance that it's not a pure waste of time have been diminishing
rapidly (IMO).

About an obvious proof, I don't expect one either -- the method is too
messy. Pop quiz: what's the core idea? It doesn't appear to contain more
substance than "push equations around introducing as many artificial
auxiliaries as needed until a polynomial _formally_ factors; then integer
factors must fall out of the formal factorization, because otherwise this
would look silly" <0.7 wink>. But it's messy enough to succeed at times
too, so isn't obviously useless either.

Relevant Pages

  • Re: Proof factoring solution is closed form
    ... In an RSA-class composite, M is so large compared to p+q this is ... JSH) has reported details about so far, the probability of factoring by pure ... rather than # of gcds, poking at random would have been _much_ more ... In other words, in this special case, the method succeeds at exactly the ...
    (sci.math)
  • Re: SF: Back to theory
    ... gcds to try. ... much more often in this method, and factoring is more expensive than doing ... It's not surprising that it's doing worse than random-gcd, ...
    (sci.math)
  • Re: SF: Back to theory
    ... gcds to try. ... much more often in this method, and factoring is more expensive than doing ... It's not surprising that it's doing worse than random-gcd, ...
    (sci.crypt)
  • Re: SF: Back to theory
    ... >> This is, certainly, surrogate factoring. ... > gcds to try. ... It's possibly surprising that it's doing ... > tested that performs better than random-gcd (well, ...
    (sci.math)
  • Re: Surrogate factoring, state of the art
    ... There's actually no 2-digit odd composite that isn't a square of a prime ... lot of gcds are tried, and factoring by looking at gcdfor random ...
    (sci.math)
Loading