Wednesday, January 16, 2008

 

JSH: Update, factoring problem solved

There is a significant development to report which means I need to come back and give additional information to this group as I'm still concerned that mathematicians may fail in their duty to report these findings. That development is an easy proof that what I call the factoring congruences must work, and work well.

So now I can quickly and easily explain what the result is, and how and why it works.

What I did was study a system of two rather simple equations:

x^2 = y^2 + pr_1

and

z^2 = y^2 + nT

where T is the target to be factored, and all the variables must be integers. What I did to probe the equations was connect x and z together with

z = x + ak

where I used two variables for that when it might seem like you could use one (which I did at first).

Now I'll give you the information to help you understand how obvious it must be that the solution I found is correct, as there are an infinity of solutions with integers for the top equation given the bottom one.

For example with z^2 = y^2 + 21, I have that y=2 is a solution, which gives z = 5. Now with that y, there are an infinite number of integer solutions for pr_1, where I'll give a few with their factors to help readers understand several crucial points:

pr_1 = (5)(1) = 5, pr_1 = (6)(2) = 12, pr_1 = (7)(3) = 21,

pr_1 = (8)(4) = 32, pr_1 = (9)(5) = 45,

pr_1 = (10)(6) = 60, and pr_1 = (11)(7) = 77.

Remember, y = 2, so in each case adding 4 must give a square and it does. Notice importantly I just advance the factors by 1, and, of course, since you just step up by 1, every prime is a potential p, so there is an answer for every prime.

I did this stepping out yesterday and realized that several requirements I had put on nT were wrong, as it doesn't have to be odd and can have 3 as a factor. For each of those values above, it's trivial to find an x, as y is set, and, of course, for any integer x, and integer z, there must exist an integer z-x, so since z-x= ak, ak must exist.

So there are always solutions, for every prime p. Now I had to use ak, instead of just one variable because I also have as a key equation: k = 2ax mod p

Now that may seem to come out of the blue, but it's a deliberate introduction to force

z = x + ak

as consider that of course then 2ax = k mod p, and to make that explicit I'll let 2ax = k + pr_2

x^2 = y^2 + pr_1 and 2ax = k + pr_2

it makes sense to multiply the latter by k, so that you have

x^2 = y^2 + pr_1

and

2axk = k^2 + kpr_2

and then add them to get

x^2 + 2axk = y^2 + k^2 + p(r_1 + kr_2)

which just begs for completing the square by adding a^2 k^2 to both sides and simplifying a bit I get

(x+ak)^2 = y^2 + (1 + a^2) k^2 + p(r_1 + kr_2)

and compare with

z^2 = y^2 + nT

and you have that z=x+ak, when

nT = (1 + a^2) k^2 + p(r_1 + kr_2).

The skeptical among you can simply solve for k, using the quadratic formula and look to see when it is rational—remember that r_1 and r_2 are completely free integers.

Now it's trivial to get the main factoring congruences:

z = (2a)^{-1} (1 + 2a^2)k mod p

k^2 = (a^2+1)^{-1}(nT) mod p

and it's possible to also solve for y:

y = (1+2a^2)^{-1} z mod p, or y = -(1+2a^2)^{-1} z mod p.

Those results follow from that result that is so much about just completing the square so it's easy algebra, and that stepping out with values for pr_1 shows how you can get any prime.

But now you can easily show that the results solve the factoring problem, as given a T that is the product of two primes, it must be true that if p>sqrt(T), then p must be greater than the lesser prime unless T=p^2. And with z mod p and y mod p, you can get z-y mod p and z+y mod p, so you get residues modulo p of the factors since with

z^2 = y^2 + nT, you have trivially that (z-y)(z+y) = nT.

So, if you loop through all values for 'a' with n=1, then you have it with mathematical certainty that you will get cases where z-y mod p or z+y mod p just gives you one of the prime factors of T, directly.

Example: Let T=119, p=11. I find that a=2 will work and give me k=2 mod 11 as an answer.

Then z = 2(1+8)/4 mod 11 = 7/4 mod 11 = 10 mod 11.

And I can find y, from y^2 = 100 - 119 mod 11 = 3 mod 11 (or use the formulas above), so

y=5 mod 11 will work, and then z-y = 5 mod 11 and z+y = 4 mod 11, but I have something interesting here as I need to subtract 11, to get

z-y = -6 mod 11 and z+y = -7 mod 11.

The congruences will do the same thing without regard to the size of the number if n=1, and you loop through the a's that work, where the only other answers have to be for the trivial case where 119 is the factor, so it can only bounce between two sets of values, where one WILL factor your target.

But that is with n=1. You can also just set 'a' to some value and then pick an n that will give you a k, as remember:

k^2 = (a^2+1)^{-1}(nT) mod p

so (a^2+1)^{-1}(nT) must be a quadratic residue modulo p. But if you pick 'a' then you can ALWAYS find an n such that it is, but now you'd need a prime about the size of sqrt(nT), and then z-y mod p and z+y mod p would have to give residues of the factors of nT modulo p, where you'd just look for a case where the target got split.

That would be REALLY FAST as unlike the approach with n=1, where you have to resolve a quadratic residue and search through values for 'a', here you are picking the quadratic residue yourself, by setting 'a' and solving for n.

So that means the congruence relations solve the factoring problem, and proof that they must is fairly trivial to step through.

Remember, most of the mathematical work is just completing the square, and the two equations work together as a system. But mathematicians have traditionally studied just equations like z^2 = y^2 + nT as their full system and found various approaches to factoring in that way.

I added another equation to the system and found the mathematical laws governing its behavior, and can easily prove then how you factor with those laws. These laws were previously unknown to mathematicians.

So I used more information with a more robust system than mathematicians traditionally used, which is what people call thinking out of the box.

But rather than acknowledge this result, so far mathematicians have for the most part sat quietly, but if it is true—and you can check the easy algebra for yourself—then factoring is solved as a problem, but my understanding is that presuming it is a hard problem is the basis for RSA encryption and factoring the public key used in that system can allow you to decrypt messages encrypted with it.

If so, then I fear that as of now the RSA system is defunct, but so far no one is telling the world, but me.





<< Home

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