Surrogate factoring, revisited

jstevh_at_msn.com
Date: 12/28/04 

Date: 27 Dec 2004 17:32:36 -0800

For some time now I've been exploring ideas having to do with what I
call surrogate factoring, where you try to factor one number by instead
factoring another, which I call the surrogate.

My work in this area has not been without difficulty, as I've had some
approaches that I've dropped, but now I have yet another approach I
think worth talking about, and this time I have a paper for you first.

It's easier for me to start a Yahoo! group to post papers, so it's at
such a place:

http://groups.yahoo.com/group/simplefact/

Also I'd like to include some text from my initial post on the group.

The essential mathematics can be worked out quickly, as consider

a_1 x + b_1 = f_1

and

a_2 x + b_2 = f_2

as I can easily substitute out x, and get the result

a_2(f_1 - b_1) = a_1(f_2 - b_2)

and if f_1, f_2, b_1 and b_2 are given integers, then I can, of course,
find integers a_1 and a_2. You might say, so what?

Well I can multiply my two original equations to get

(a_1 x + b_1)(a_2 x + b_2) = f_1 f_2

and a couple of weeks ago, I basically pursued that angle where f_1 f_2
was my target number that I was trying to factor, but it didn't work.

If you multiply out the left side you get

a_1 a_2 x^2 + (a_1 b_2 + a_2 b_1)x + b_1 b_2 = f_1 f_2

and it occurred to me that maybe I should let

b_1 b_2 - f_1 f_2

be my target number.

The method, which is in my paper on this site also has

a_1 b_2 + a_2 b_1

set, so I call that A, and consider what happens, as then I get

a_1 = (A - a_2 b_1)/b_2

and can actually solve for x, to get

x = (b_2 f_1 + b_1 f_2 - 2b_1 b_2)/A

and you may still say so what, but notice something odd here, as I have

a_1 a_2 x^2 + (a_1 b_2 + a_2 b_1)x + b_1 b_2 - f_1 f_2 = 0

so b_1 b_2 - f_1 f_2 MUST share factors with x, so I know that

b_2 f_1 + b_1 f_2 - 2b_1 b_2

must share factors with b_1 b_2 - f_1 f_2.

That is a fascinating result.

It's fun to play with some actual numbers as it's not the most
intuitive result.

For instance, let's let x=5, and use

x + 2 = 7
2x + 11 = 21

so a_1 = 1, a_2 = 2, b_1 = 2, b_2 = 11, f_1 = 7, f_2 = 21

and notice then that

x = (b_2 f_1 + b_1 f_2 - 2b_1 b_2)/A, gives

x = (75)/A, and you can get A, by multiplying out as you have

2x^2 + 15x + 22 = 7(21), so A=15, giving x = 5.

Big deal, right? Well, notice that 7(21) - 22 = 125, so I've factored

b_1 b_2 - f_1 f_2

and the difference between here and what's in my paper is in the paper
I set

b_1 b_2 = -j^2, and f_1 f_2 = T^2, where j^2 + T^2 = M^2,

and M is the number to be factored, x, in the paper is found, not given
like for this simple example.

The paper posted on the site basically tells you how you get all those
variables, where importantly you get x, and maybe a non-trivial
factorization.

To give you some idea of the complexity involved the key formula in the
paper is

z_1^2 = (2(A^2 + 4j^2y + 2Ty)Mj +/- sqrt((8j^2 M^2y + A^2(2j^2 + T))^2
-A^4 T^2))/(4Mjg_1^2)

where the z_1 in the paper is a_1 above, and g_1 in the paper is f_1
above.

Does it work?

I don't know. The theory is intriguing enough to talk about, and just
to be sure I did send the paper to some experts, as well as some people
in the US government.

I heard nothing back from them, so I still don't know.

This group should hopefully help me find out.

Oh, so if I think it might work, why talk about it?

Well, even if it works, it looks like it might be a bit of work to
implement, as you need to be able to factor one really big number to
get the engine running.

James Harris

Relevant Pages

  • Re: Surrogate factoring and the k/T ratio
    ... is your factoring percentage 100% or 1/1000th? ... method factored all 500 of the target numbers with zero errors. ... If surrogate factoring works then it works one way, ... Now if you are insane, yes, you can explain away mathematicians ...
    (sci.crypt)
  • 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: Surrogate factoring and the k/T ratio
    ... is your factoring percentage 100% or 1/1000th? ... method factored all 500 of the target numbers with zero errors. ... If surrogate factoring works then it works one way, ... Now if you are insane, yes, you can explain away mathematicians ...
    (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)
  • JSH: Results that are much more fun
    ... It's almost a relief now to have the results around residues as so ... used them with no success against the factoring problem. ... It's like taking over the definition of mathematical proof ... Ok, so I worked on surrogate factoring for years with little success, ...
    (sci.math)