Re: Gist of surrogate factoring theorem

jstevh_at_msn.com
Date: 04/10/05 

Date: 10 Apr 2005 06:13:57 -0700

Proginoskes wrote:
> jstevh@msn.com wrote:
> > N. Silver wrote:
> > > Rick Decker wrote:
> > [...]
> > Not really, as in factoring, for years a difference of
> > squares has been important, while the surrogate factoring
> > theorem gives you an *infinite* number of solutions to
> > a difference of squares with your target.
>
> Unfortunately, most of them are useless to solving the real factoring
> problem.
>

Stated without proof.

> > That is just given, as you take factors of Tj^2, and as
> > you can take rational factors, you have an infinite
> > supply, and for *each* set of factors f_1 and f_2 such
> > that
> >
> > f_1 f_2 = Tj^2
> >
> > you get factors g_1 and g_2 such that
> >
> > g_1 g_2 = TM^2
> >
> > where M is your target.
>
> I can do the same thing, by letting g_1 = M f_1 / j and
> g_2 = M f_2 / j, because if f_1 f_2 = Tj^2, then
>
> g_1 g_2 = (M f_1 / j) * (M f_2 / j) = M^2 / j^2 * f_1 f_2
> = M^2 / j^2 * T j^2 = T M^2.
>

As I mentioned before my work people could get difference of squares,
but only trivially, as you can see here, where encoded into the
factorizations the poster gives are trivial factors.

> The existence of a correspondence is not enough to say anything about
> factoring; you must find the right one and then take the step that
you
> seem not to have taken.
>

Yet, if you read up on known factoring methods like QS or the Number
Field Sieve, the same objections posters raise against the surrogate
factoring theorem, apply to them as well.

Yes, with QS you have to find the "right" difference of squares, and
the same applies for the Number Field Sieve.

James Harris