Re: Surrogate factoring explained

From: Décio Luiz Gazzoni Filho (decio_at_decpp.removethis.net)
Date: 02/24/05 

Date: Thu, 24 Feb 2005 17:18:00 -0300

Tim Peters wrote:

> [ođin]
> [...]
>>> Can you prove that the surrogate is easy? Is it just that you are saying
>>> that the surrogate are not specially chosen? I doubt that the surrogate
>>> is
>>> easier, especially given that it is much bigger.
>
> [Décio Luiz Gazzoni Filho]
>> You're about as stubborn as James itself.
>>
>> First of all, the surrogate can be factored algebraically as (M + j)
>> (M - j), so it's no more than twice as hard to factor as M itself. If j
>> is chosen at random, each of M + j and M - j will have a few small
>> factors, and after dividing those out, it's likely that factoring both M
>> + j and M - j by NFS will be easier than factoring M. But that's the
>> brute-force way; if j is chosen wisely (and I've shown time and time
>> again that it's possible to do this with low cost), then both M + j and M
>> - j are very easy to factor.
>>
>> As I've pointed out elsewhere, even with a very inefficient sieve
>> programmed in PARI/GP, it's a matter of a couple of minutes to find a
>> suitable surrogate for RSA-2048, for instance.
>>
>> James' algorithms has flaws, but this isn't one of them. So please drop
>> this argument already.
>
> Well, there are two parts to this. The part you're addressing is that you
> have in fact shown that finding a fully-factorable T can be done
> efficiently. That's been explained to ođin before, at least twice that I
> know of, so I'm at a loss to account for why he keeps saying he doubts
> it's possible.
>
> The other part is asking James whether he can prove this. I've seen no
> reason to believe that James has incorporated any of your smack-on-target
> sieving methods into his approach, or to believe that he followed your
> argument (he latched on to the "poly time" conclusion, but it's unclear
> that anything leading up to that registered).

Par for the course for James. He asks for help from the newsgroup, then
ignores any helpful replies and concentrates on the flamefests that ensue
instead.

> Indeed, in this very thread, his
> example uses a T that factors as
>
> (5)(23)(61)(30557)(137573)(143881)(214213)
> (22341796043767){12826012523870101)
>
> Any of your sieves would have found a more efficient T than that to work
> with -- I conclude he's not using them. So if we're talking about
> "James's algorithm" as meaning the code James actually uses (not an
> entirely unreasonable meaning <wink>), wondering about the feasibility of
> factoring M+j and M-j is still valid. "Décio's algorithm" is a different
> story (and would obviously be the method of choice if the specific j
> chosen were immaterial to success).

Still, if there happened to be a somewhat large class of j's that were
guaranteed to yield a factorization, and for these j's the values of M + j
and M - j behaved as random integers (as far as factorizations are
concerned), then there would still be no difficulty to find fully
factorable surrogates.

My instinct suggests the following procedure:
-trial divide a large amount of pairs (M + j, M - j) using Bernstein's
product tree,
-apply some Pollard p - 1 on the cofactors,
-if the previous steps don't produce a full factorization, but the cofactors
of some pair (M + j, M - j) are both within reach of practical MPQS effort,
then use MPQS.

Décio

Relevant Pages

  • Re: What puzzles me, discovery ignored
    ... Does James actually have a general solution, ... factorization, but have solutions. ... Factorization, 2 variable diophantine equations, Pell ... The following two transform pairs on and ...
    (sci.math)
  • Re: What puzzles me, discovery ignored
    ... I got one from James, ... No. James' factorization method relates to forms like: ... Factorization, 2 variable diophantine equations, Pell ... The following two transform pairs on and ...
    (sci.math)
  • Re: What puzzles me, discovery ignored
    ... Does James actually have a general solution, ... I found a way to convert them to the Pell - like ... factorization, but have solutions. ... The following two transform pairs on and ...
    (sci.math)
  • Re: What puzzles me, discovery ignored
    ... Common Divisor function GCDworking - can't remember if GCD ... Does James actually have a general solution, ... factorization, but have solutions. ... transforms with any integer value of v, ...
    (sci.math)
  • Re: What puzzles me, discovery ignored
    ... Does James mention that anywhere? ... Does James actually have a general solution, ... your decryption of his work focussing on factorisation? ... No. James' factorization method relates to forms like: ...
    (sci.math)