Saturday, May 06, 2006


Another try, another factoring method

Looking over replies to the factoring idea of mine previous to this one, there is still the problem of too much complexity for most.

So it's yet another factoring idea of mine too complicated, but I have another which is simple enough that most of you should be able to understand it. Don't know how well it works though.

I have from my quadratic residue result that

8T + k^2 = r mod n

where T is the target to factor, k is a difference of factors of 2T, n is a natural number such that n<T, and r is a quadratic residue modulo n.

First you find 8T mod n, so let c = 8T mod n, and now you can just find k, such that

c + k^2 is a square,

as then you have a possible difference, as you have another quadratic residue.

Here's a demonstration factoring 65 = 5(13), using n = 9.

(It seems to me that you want an n that is greater than floor(T/8) for obvious reasons, and it has to be less than T.)

8(65) mod 9 = 7, and with c = 7, I have 7+ k^2, and k=3, witll work as that gives

7 + 9 = 16

and 13 - 2(5) = 3, so I found a difference. To check a difference you plug it into

sqrt(k^2 + 8T), and notice that sqrt(9 + 8(65)) = 23.

Then you have 23-3 = 20, giving you 5, with the gcd with 65, and 23+3 = 26, giving you 13.

If your k doesn't work with your c, you can add n to it, and try again.

That is, with

x = sqrt(k^2 + 8T), you have that the gcd of x+k with your target T, will give one factor, and the gcd of x - k with the target will give the other.

Of course you have to factor c to get all the k's, so it's what I call a surrogate factoring method.

With my other idea, I forced k=1, and then you go looking for this m, which may or may not work well, I don't know. Hell, I don't know if this idea works well either, but it may be less frustrating to play with, as there is a lot less tweaking involved.

You see, the problem with a lot of my ideas is that for most people they are too damn complicated to figure out how to get to work. This one should be simple enough though, so you can play with it, and if it does work well, I'll be surprised.

But at least you can get it to work. My ideas are so freaking complicated in their simplicity that the world gets befuddled. Maybe this one will be different.

<< Home

This page is powered by Blogger. Isn't yours?