Re: Critiquing surrogate factoring

jstevh_at_msn.com
Date: 03/31/05 

Date: 30 Mar 2005 15:11:14 -0800

Pubkeybreaker wrote:
> I have, by and large, stayed out of all of these discussions.
> However, I must
> point out that the idea of "surrogate factoring" is a valid
technique.
> However,
> it is not new, and for James to claim it as his own is disingenuous.
> All he has done is
> to supply the label "surrogate factoring".

The method I outline with a theorem no less shows a direct connection
between factors of a surrogate, which is Tj^2, and factors of M^2.

They are directly linked by a few equations which you can see for
yourself.

The idea is to use this direct link to pull out a non-trivial
factorization of M.

What is not in doubt is that the theorem itself is correct, as it is a
theorem.

As to how effective the methods that follow from the theorem are,
that's another question.

The theorem itself, being a theorem, is perfect.

> The continued fraction algorithm, QS, and NFS all work via
> "surrogate factoring".
> Instead of factoring N directly, we factor (or attempt to factor)
> MANY smaller
> numbers that are algebraically related to N. Most of these numbers
are
> not successfully factored. These get thrown away. We then take
those
> that ARE successfully factored and combine them using large scale
> linear algebra to then factor
> N.

Hey, if it's surrogate factoring, then you've simply expanded the area
covered by that phrase "surrogate factoring".

I still have the right to call a method of mine that uses factorization
of a surrogate--surrogate factoring--while you have the right to say
that surrogate factoring itself has been around for a while.

The phrase applied this way has not.

> The concept is not new and has been used since 1970. It was first
> invented by
> Brillhart and Morrison. (and had been suggested but never fully
> developed by
> Lehmer as far back as the 1930's. It was not realizable until modern
> computers became available)
>

I'm curious enough that I'll probably check into the subject in more
detail, as it basically just sounds interesting.

> It is extremely unlikely that the simple use of a small number of
> auxiliary quadratics
> will lead to a practical method. One must conduct an extensive
search
> for
> parameters that allow the factorization to succeed. The search space
> in all attempts
> so far is exponential in the size of the problem. What CFRAC, QS,
NFS
> do is
> to use a VERY LARGE NUMBER of auxiliary congruences, and do a "small
> effort"
> search on each one, thowing away those efforts that do not succeed.

Well guesses, wags, etc. are not against the idea I have here of
critiquing, so I don't challenge your statement.

I will remind that what I presented here in my original post is a
theorem, and being a theorem, it's not arguable as to its correctness.

That theorem shows that you get rational factors of M^2 from using the
factorization of Tj^2, where T = M^2 - j^2, and j is a number you
select, with the requirement that j^2 > M^2.

Those are the facts to work from, a theorem, and consequences from that
theorem.

The critique would continue even if the algorithms that follow from the
theorem don't work well, as either way I want to know why.

James Harris

Relevant Pages

  • Proper evaluation of surrogate factoring
    ... Surrogate factoring is just kind of a wild idea that means you have to ... I am being very serious here, modern mathematicians lie a lot. ...
    (sci.crypt)
  • Re: SF: Areas of confusion, infinity
    ... > notably the set of rationals. ... choosing any integer is the same as the probability of any other ... That's what make the factoring problem interesting, i.e., not ... > is naive with the surrogate factoring theorem. ...
    (sci.crypt)
  • Re: What surrogate factoring theory now says
    ... Surrogate factoring theory says that you can turn factoring a hard ... once the engineering is figured out that is achievable. ... Mainly I just added one more congruence to the difference of squares. ...
    (sci.crypt)
  • Re: What surrogate factoring theory now says
    ... Surrogate factoring theory says that you can turn factoring a hard ... once the engineering is figured out that is achievable. ... Mainly I just added one more congruence to the difference of squares. ...
    (sci.crypt)
  • Surrogate factoring, theory versus implementation
    ... the surrogate factoring method is itself being called to ... Now the discussions can go on indefinitely as posters who reply to me ... It's in its failures that my primary interest lies. ...
    (sci.math)