Sunday, July 16, 2006

 

SF: Considering possible solutions

I put up a simple idea for factoring where some may think, if they checked it at all, that they have shown it to not work well, so here's a post that might help.

I start with

x^2 - y^2 = S - 2*x*k

and use a technique where I pick the residue of x, so I use a congruence equation that has x_res instead of x, to choose S and k.

But imagine a solution for x^2 - y^2 that has T as factor where x = x_res mod T, but with a given choice for S, which has given you k by the methods I've explained in other posts

x^2 - y^2 > S - 2*x*k

for ALL solutions possible?

Necessarily then you get bumped to another residue. It's trivially obvious.

The simple solution is, get this, use a bigger S.

I now hypothesize that as T increases in size S will tend to have a size roughly equal to T by absolute values.

Now then, to let you get a sense of how solid this theory is at this point, imagine that the mathematics really doesn't care about the congruences I've found, and I'm just deluding myself, so let's consider a hypothetical solution for

x^2 - y^2 = 0 mod T

where x has, say, 1 modulo T as a residue.

Then

S - 2*x*k = 0 mod T

as well—because it has to from where I start—so then solving out I find

k = S*(2x)^{-1) mod T

just like before, as it's forced by the relationships.

So then, there IS a solution for the given S and k, in contradiction to the idea that the method doesn't work.

At this point then, the only possible objection might be that there is a narrow range for S?

So that the S you pick is only the residue there as well?

Maybe, so then it would turn into some search using S = S_res mod T?

Not likely, as T is likely to be big relative to its factors, so by that reasoning S might have to be truly huge relative to them, but why mathematically, when all that has to happen is that

x^2 - y^2 balances with S - 2*x*k?

Remember, problems with small S where you don't have a solution may simply be a result of it not being possible for the two sides to balance for a given solution with x having a particular residue.

And even if someone thinks that maybe S is just a residue, you're searching then modulo T for an S that works.

You're searching modulo T, the target itself, so if it's huge, the range of search is huge as well with every multiple of T you add to your starting S, but why would the mathematics force such huge numbers here?

I suggest to you that it only needs S to be roughly the same size as T.





<< Home

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