Re: Surrogate factoring explained

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

Date: Thu, 24 Feb 2005 15:06:08 -0300

ođin wrote:
> <snip>
>
>> The entire point of surrogate factoring is to render that useless by
>> what is esentially a back-door attack of shifting the factorization
>> from the hard target to an easier surrogate, which is factored, and its
>> factors are then used to factor the target.
>
> 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.

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.

Décio

Relevant Pages

  • Reality check, surrogate factoring
    ... Surrogate factoring is meant to beat the tactic of picking two hard ... and it will be really big for a big target. ... of the time for rationals x's. ...
    (sci.math)
  • Reality check, surrogate factoring
    ... Surrogate factoring is meant to beat the tactic of picking two hard ... and it will be really big for a big target. ... of the time for rationals x's. ...
    (sci.crypt)
  • Re: JSH: Surrogate factoring, periodic behavior
    ... That is the primary decision relation that determines if a surrogate ... Remember the surrogate factorization involves factoring a target ... as human curiosity is such a wonderful thing. ... You are the cruel jocks picking on the kid you call nothing. ...
    (sci.math)
  • Re: surrogate factoring
    ... "surrogate factoring" doesn't really mean anything specific. ... distinct (maybe odd) primes, and you want to find p and/or q. ...
    (sci.math)
  • Re: Surrogate factoring, update on research
    ... >numbers by instead factoring some surrogate number. ... >but didn't factor the target. ... That's an amazing breakthrough. ...
    (sci.crypt)