### Wednesday, June 04, 2008

## Re-cap, why factoring is done

I'm going to shift variables to give you all something more familiar with factoring and explain the significance of a remarkable and simple congruence result:

Given

x^2 = y^2 + cN

where N is a target odd composite to factor, not divisible by 3, and c is a control variable that equals 1 if N mod 3 = 2 and 5 if N mod 3 = 1, it can be trivially proven that

x^2 = 8^{-1] (9cN) mod p

when 8^{-1] (9cN) is a quadratic residue for an odd prime p, where p < 2x/3.

For some of you it may be an extremely counter-intuitive result or terribly hard to understand, so I'll give an example and then talk about why it's significant.

Let N = 299 = 13(23), and since 299 mod 3 = 2, c=1. The only primes available (I'll leave the proof to the reader) are 3, 5, 7, 11 and 13 but since I know 13 is a factor I'll try, 11.

With p = 11, I check to see if the quadratic residue exists:

x^2 = 8^{-1} (9(299)) mod 11 = 7(7) mod 11, so that's easy and x = 7 mod 11 or -7 mod 11.

For those who wonder about the modular inverse 8^{-1} mod 11 = 7 because 7(8) = 1 mod 11.

Just knowing that x needs to be greater than p, you could try 11+7 = 18, and

y = sqrt(18^2 - 299) = sqrt(25) = 5, as I only care about the positive solution.

So I have (18+5)(18-5) = (23)(13) = 299, and a factorization with this approach.

The result is significant for two reasons:

x mod p_1*p_2*p_3

and if p_1*p_2*p_3 > x then, of course, you have x exactly.

So the short of it is, if it had been known early on that you could get x mod p then factoring would NOT have been thought to be a hard problem, so it's that significant.

From a socio-political aspect the result is significant because it's easy to derive, so easy to prove and has extraordinary social impact when developed into a fast factoring method so there is no way that a healthy mathematical society would not inform the world about it (and start celebrating, cheering and being generally happy that such a remarkable and beautiful result exists).

That isn't happening yet and my guess is that part of it is that mathematicians hate me and they're political animals so they are playing politics with the result. Ha ha.

I laugh because they can only get away with that for so long and then their funding can be taken away—all of it—in "pure math" areas so these people will be looking for new jobs soon enough. Ha ha.

Oh, so how do you derive the result? Easy. I've given the derivation in other posts with different variables but wanted to use more familiar variables to help some of you understand.

I have other mathematical research having proven Fermat's Last Theorem, found the prime counting function, delivered a prime gap equation, and if you Google "definition of mathematical proof" you can find my definition in the top 10.

Mathematicians hate me because I say many of them routinely lie because they do lie and they do it for money and prestige and because doing real mathematical research is harder than lying about your research and playing pretend. Ha ha.

Part of the purpose of postings like this one is to remove their naive student support, which will hurt their feelings very much because they are actors, playing at being mathematicians so it will bug them for you to look at them like they're crappy human beings, which they are.

And to me that actually is such a fun thing to contemplate that I have a sense of satisfaction already.

After all, Ribet or Andrew Wiles really just want butt-kissers which so many of you have been for so many years so the shock of that tragic look in your eyes will devastate the con artists, which they deserve.

Merry day!

Given

x^2 = y^2 + cN

where N is a target odd composite to factor, not divisible by 3, and c is a control variable that equals 1 if N mod 3 = 2 and 5 if N mod 3 = 1, it can be trivially proven that

x^2 = 8^{-1] (9cN) mod p

when 8^{-1] (9cN) is a quadratic residue for an odd prime p, where p < 2x/3.

For some of you it may be an extremely counter-intuitive result or terribly hard to understand, so I'll give an example and then talk about why it's significant.

Let N = 299 = 13(23), and since 299 mod 3 = 2, c=1. The only primes available (I'll leave the proof to the reader) are 3, 5, 7, 11 and 13 but since I know 13 is a factor I'll try, 11.

With p = 11, I check to see if the quadratic residue exists:

x^2 = 8^{-1} (9(299)) mod 11 = 7(7) mod 11, so that's easy and x = 7 mod 11 or -7 mod 11.

For those who wonder about the modular inverse 8^{-1} mod 11 = 7 because 7(8) = 1 mod 11.

Just knowing that x needs to be greater than p, you could try 11+7 = 18, and

y = sqrt(18^2 - 299) = sqrt(25) = 5, as I only care about the positive solution.

So I have (18+5)(18-5) = (23)(13) = 299, and a factorization with this approach.

The result is significant for two reasons:

- No one knew in mathematical history that given x^2 = y^2 + cT, you could get x mod p, where p is an odd prime less than 2x/3, when x is forced to be divisible by 3, and it is a "pure math" result with amazing significance there because you have these prime numbers coming in out of the blue in this remarkable way.

And prime numbers are cool. - Given x mod p with successive primes, you can get x exactly, which means you can factor T.

x mod p_1*p_2*p_3

and if p_1*p_2*p_3 > x then, of course, you have x exactly.

So the short of it is, if it had been known early on that you could get x mod p then factoring would NOT have been thought to be a hard problem, so it's that significant.

From a socio-political aspect the result is significant because it's easy to derive, so easy to prove and has extraordinary social impact when developed into a fast factoring method so there is no way that a healthy mathematical society would not inform the world about it (and start celebrating, cheering and being generally happy that such a remarkable and beautiful result exists).

That isn't happening yet and my guess is that part of it is that mathematicians hate me and they're political animals so they are playing politics with the result. Ha ha.

I laugh because they can only get away with that for so long and then their funding can be taken away—all of it—in "pure math" areas so these people will be looking for new jobs soon enough. Ha ha.

Oh, so how do you derive the result? Easy. I've given the derivation in other posts with different variables but wanted to use more familiar variables to help some of you understand.

I have other mathematical research having proven Fermat's Last Theorem, found the prime counting function, delivered a prime gap equation, and if you Google "definition of mathematical proof" you can find my definition in the top 10.

Mathematicians hate me because I say many of them routinely lie because they do lie and they do it for money and prestige and because doing real mathematical research is harder than lying about your research and playing pretend. Ha ha.

Part of the purpose of postings like this one is to remove their naive student support, which will hurt their feelings very much because they are actors, playing at being mathematicians so it will bug them for you to look at them like they're crappy human beings, which they are.

And to me that actually is such a fun thing to contemplate that I have a sense of satisfaction already.

After all, Ribet or Andrew Wiles really just want butt-kissers which so many of you have been for so many years so the shock of that tragic look in your eyes will devastate the con artists, which they deserve.

Merry day!