Reverse engineering surrogate factoring

Discussion in 'Recreational Math' started by jstevh, Mar 3, 2005.

  1. jstevh

    jstevh Guest

    There actually is a direct way to research surrogate factoring and
    answer questions quickly, which is basically reverse engineering.

    The basic equations are

    yx^2 + Ax - M^2 = 0

    and

    yz^2 + Az - j^2 = 0

    so

    y = (M^2 - Ax)/x^2 = (j^2 - Az)/z^2

    and you can solve to get

    x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az)

    and

    z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)

    and in each case multiplying both sides by A gives you

    Ax = Az(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az)

    and

    Az = Ax(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)

    and you can pick an M for which you know the prime factors, and solve
    for Az.

    Then you just use that with

    y/A^2 = (M^2 - Ax)/A^2 x^2 = (j^2 - Az)/A^2 z^2

    as I've just divided my equation for y above through by A^2

    and focusing on

    y/A^2 = (j^2 - Az)/A^2 z^2

    you can just look at the denominator after dividing off shared factors
    in the numerator and denominator.

    There are three possibilities:

    1. The prime factors are all related in some way to M

    2. The prime factors are all related to the particular prime factor of
    M that you are using, so it's crap.

    3. There is no relationship between the prime factors of the
    denominator of y besides the prime factor of M that you are using.

    If 1. then there should be some way to generalize to a full, perfect
    algorithm.

    If 2. then bad news, surrogate factoring needs to know the prime
    factor of M already to work consistently, so it's crap.

    If 3. then surrogate factoring provides the first known perfect random
    number generator.

    Those are the only possibilities, and notice that there MUST be an
    integer solution for Az that contains prime factors of M in whatever
    combination you want, so you can check.

    It looks kind of like a statistical thing to me, and I don't like doing
    statistics, so I've concentrated on an upfront approach, which
    basically assumes that 1. is the correct choice, and that the prime
    factors of the denominator of y are either factors of M, j or T^6.

    Those algorithms actually do factor at lot at small M, like under 60
    bits, but for some reason they get worse and worse as you get over 60
    bits, and I have to figure that some other primes are in there.

    They are either related to M, individual prime factors of M, or are
    random.

    So you have 1., 2. or 3., and the person who can crack the code, if
    it's 1., can basically factor anything. If it's 2. then that's just
    it, surrogate factoring can't work. If it's 3. then it *may* still
    work, but heavily probabilistically, but the world has its first
    perfect random number generator outside of quantum.

    That basically covers things in a nutshell. If someone has done the
    reverse engineering then they may already know. I've looked curious to
    see if anyone might post on this topic, and I haven't seen anything,
    which lead me and my paranoid self to believe that 1. is the case, and
    that someone out there in this wide world has the full solution, and is
    smiling very broadly.

    If I liked statistics more I might explore the reverse engineering
    myself, but I just don't. I'm still mostly thinking about surrogate
    factoring from the theoretical side, with a few factorizations here and
    there with my test programs.


    James Harris
     
    jstevh, Mar 3, 2005
    #1
    1. Advertisements

  2. jstevh

    Tim Peters Guest

    [JSH]
    I already reported on computer experiments that ignored M entirely when
    picking a T, instead always adding one small prime at a time to T (first 2,
    then 3, then 5, ...), then checking gcd(f-g, M) across all integer f*g=T^6
    with f >= g >= 1. In all, that worked better than random-gcd in terms of
    number of gcds needed, and (by the same measure) better than any method
    tested to date that tried to choose T as a function of M. For products of
    randomly chosen 20-bit primes, across 1000 trials it never needed to go
    beyond T=2*3*5*7*11*13*17*19 to find a factor.
    #3 doesn't follow.
     
    Tim Peters, Mar 3, 2005
    #2
    1. Advertisements

  3. jstevh

    boattug Guest

    ** SF plonk! **
     
    boattug, Mar 3, 2005
    #3
  4. jstevh

    oðin Guest

    There are three possibilities:
    What is a perfect algorithm? You mean one that always works and terminates
    in poly-time? If that is what you mean, you have never proved this, which
    makes you a liar. If it is not what you mean, then it is crap, and again,
    you are a liar..
    And if it is crap that means that you are a liar.
    That is nonsense. You have been told many times that any algorithm executing
    on a deterministic computer cannot generate random numbers. You are an
    idiot.
    But how fast? There are already plenty of ways to factor anything given
    enough time.
    No idiot...
     
    oðin, Mar 3, 2005
    #4
  5. jstevh

    C. Bond Guest

    Note that you do not answer any significant questions in your post.

    [snip]...
    You still have no idea what a *perfect random number generator* is. Add
    that lapse to the growing list of things you make stupid comments about.
    Item 3. was not a possibility. It should have read, 3. I am an ineducable
    moron.
     
    C. Bond, Mar 3, 2005
    #5
  6. Really? By algorithmic methods? Boy, you are even more ignorant than I
    thought. How do you manage to remain so thoroughly ignorant? How come you
    are not embarrassed to make a public display of your ignorance, time and
    again? Are you ill?
     
    Felix Rawlings, Mar 3, 2005
    #6
  7. jstevh

    mensanator Guest

    That's why he's considered a troll. He's only pretending to be ignorant
    to see how many responses he gets.
     
    mensanator, Mar 3, 2005
    #7
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.