### Saturday, March 28, 2009

## JSH: Probing composites with quadratic residues idea

I've been thinking still about factoring as my other "pure math" research is as useless as ever in breaking the impasse—mathematicians can choose to ignore any "pure math" result—so I'm thinking more about quadratic residues and how primes will "bump" each other.

Given T a target composite that is the product of two odd primes p_1 and p_2, so T=p_1*p_2, I'm considering

m^2 - T = r

where m^2>T, with m near sqrt(T), but I'm interested in the smaller prime, as there is only roughly a 50% chance that r will be a non-square quadratic residue for BOTH primes, so the math has an out to which I will return.

So consider about 1000 checks, so I'll let m be a function:

m(n)^2 - T = r(n)

where I want it linear, so you'd say, take floor(sqrt(T)) + 1, for m(0), and m(1) would be m(0) + 1, and m(2) = m(1) + 1 and so forth.

For approximately 50% of the cases, p_1 and p_2 will have r itself as a quadratic residue.

In EACH of those cases r < p_1 and r < p_2.

For approximately the other half of cases p_1 will have r itself as a quadratic residue, but for p_2, r mod p_2 will be a perfect square, as the math takes the out.

And in EACH of those cases r < p_1 and r > p_2.

So with your 1000 checks roughly 1/2 of your values for r(n) should be above p_2 and roughly 1/2 should be below.

So you find p_2 in the middle. That is, p_2 is given approximately by the mean, that is r(n)/1000.

With 10000 checks you should get a sharper view of p_2, in what is kind of like a pixelated approach to factoring.

Just an idea as I grasp for straws here. I'm beginning to hate "pure math" as it's so much easier for me to do, while for a practical result, the only thing big enough is factoring. And I'm looking for my third solution to the factoring problem as the other two are just too hard for people to grasp for some reason.

But this one should be easy.

Given T a target composite that is the product of two odd primes p_1 and p_2, so T=p_1*p_2, I'm considering

m^2 - T = r

where m^2>T, with m near sqrt(T), but I'm interested in the smaller prime, as there is only roughly a 50% chance that r will be a non-square quadratic residue for BOTH primes, so the math has an out to which I will return.

So consider about 1000 checks, so I'll let m be a function:

m(n)^2 - T = r(n)

where I want it linear, so you'd say, take floor(sqrt(T)) + 1, for m(0), and m(1) would be m(0) + 1, and m(2) = m(1) + 1 and so forth.

For approximately 50% of the cases, p_1 and p_2 will have r itself as a quadratic residue.

In EACH of those cases r < p_1 and r < p_2.

For approximately the other half of cases p_1 will have r itself as a quadratic residue, but for p_2, r mod p_2 will be a perfect square, as the math takes the out.

And in EACH of those cases r < p_1 and r > p_2.

So with your 1000 checks roughly 1/2 of your values for r(n) should be above p_2 and roughly 1/2 should be below.

So you find p_2 in the middle. That is, p_2 is given approximately by the mean, that is r(n)/1000.

With 10000 checks you should get a sharper view of p_2, in what is kind of like a pixelated approach to factoring.

Just an idea as I grasp for straws here. I'm beginning to hate "pure math" as it's so much easier for me to do, while for a practical result, the only thing big enough is factoring. And I'm looking for my third solution to the factoring problem as the other two are just too hard for people to grasp for some reason.

But this one should be easy.