Re: Simple answer, surrogate factoring

From: Tim Peters (tim.one_at_comcast.net)
Date: 03/04/05 

Date: Fri, 4 Mar 2005 17:50:17 -0500

[fiziwig, presumably to JSH]
> I've followed your postings off and on for several years. I, too, am
> an amateur interested in the factoring problem, and probably more
> willing than most to give you the benefit of the doubt. I suspect that
> there is a very fast factoring algorithm just waiting to be discovered,
> and it's likely it might come from a completely unexpected direction.
> I don't see any compelling reason why it might not be discovered by an
> amateur such as your or me. I've pondered this problem since my high
> school days in 1960 but haven't accomplished anything more exciting
> that re-inventing Pollard's rho before I knew of it's existence.

Cool! Pollard's rho is easy to understand once it's explained, but it takes
genuine insight to discover it.

> But, fool that I am, I keep studying and trying new approaches.

More power to you. Sounds like we're about the same age, and I keep
unreasonable optimism alive too <wink>.

> But I have to ask one question. As I recall, I think I asked you this
> question a year or two ago and didn't get an answer. The question is
> simply this: Could you take a reasonably small number, say 8 or 10
> digits, and DEMONSTRATE, step by step how your method would be applied
> to factoring that number. Can I see how you use it to factor an easy
> number like 50,985,511 for example?

James doesn't give numeric examples. It's been suggested many times, also
that he _try_ numeric examples before insisting a proof is correct. Doesn't
sink in; he seems to think it's beneath him (or something like that -- his
faith in his ability to draw correct conclusions from pages of pushing
symbols around is truly astonishing, especially since the conclusions are
almost always shown incorrect via small numeric examples).

I'll work out your example for him. He'll jump in to rant if I misinterpret
his intent, and that's about the only way to approximate "a discussion"
here. The number to be factored is called "M", so we start here with

    M = 50985511 = 4547 * 11213

Sometimes he says M has to be odd, and other times adds that M can't be the
square of a prime. We're in no trouble on either count here.

Next (and I'll intersperse his original post, starting with "#"):

# j is some non-zero natural usually chosen to be less than M,

Pick

    j = 5

here. Why? Because I searched until I found a j that actually works for
this M <wink -- but most j don't work, despite the "proof" that all j
work -- or perhaps all j do work and the parts of his post explaining the
algorithm were wrong>.

# T = M^2 - j^2

Which equals (M+j)*(M-j), so here

    T = (50985511 + 5)*(50985511 - 5) = 2599522331931096 =
        2**3* 3* 11* 13* 17* 47* 293* 853* 3793

# you solve for Ax using
#
# Ax = +/-(f_1 - f_2) + 2j^2
#
# where f_1 f_2 = Tj^2, and you iterate through all possible integer
# f_1 and f_2,

    Tj^2 = T * 5**2 = 2**3* 3* 5**2 * 11* 13* 17* 47* 293* 853* 3793

in this case. There are 4*2*3*2*2*2*2*2*2*2 = 3072 ways to split Tj^2 as
the product of two integers each >= 1. It so happens that

    f_1 = 251965921350 = 2* 3* 5**2* 11* 13* 47* 293* 853
    f_2 = 257924 = 2**2* 17* 3793

is the one you need here (obtained by computer search). If it were actually
true than any j worked, there are very efficient ways to choose a j that
minimizes the number of possible splittings (in fact, if any j worked, this
method would be a huge breakthrough).

# and take the gcd of Ax with M

    Ax =
    +(f_1 - f_2) + 2j^2 =
    (251965921350 - 257924) + 2*5**2 =
    251965663476

and

    gcd(251965663476, M) = 11213

Bingo -- a factor was found.

Relevant Pages

  • Re: Simple answer, surrogate factoring
    ... > an amateur interested in the factoring problem, ... > there is a very fast factoring algorithm just waiting to be discovered, ... > amateur such as your or me. ... genuine insight to discover it. ...
    (sci.math)
  • Re: Simple answer, surrogate factoring
    ... > an amateur interested in the factoring problem, ... > there is a very fast factoring algorithm just waiting to be discovered, ... > I don't see any compelling reason why it might not be discovered by an ... > amateur such as your or me. ...
    (sci.math)
  • Re: Simple answer, surrogate factoring
    ... > an amateur interested in the factoring problem, ... > there is a very fast factoring algorithm just waiting to be discovered, ... > I don't see any compelling reason why it might not be discovered by an ... > amateur such as your or me. ...
    (sci.crypt)
  • Re: Simple answer, surrogate factoring
    ... > an amateur interested in the factoring problem, ... > amateur such as your or me. ... be self derogatory on a cryptology or math newsgroup, ...
    (sci.math)
  • Re: Proof factoring solution is closed form
    ... >> your proliferation of redundant threads that you don't pay attention ... Remember I'm the inventor of surrogate factoring. ... But are you implying that if Rick were the inventor, ... > the factoring problem as there was every reason to believe that I would ...
    (sci.math)