Harristotelian Logic

Intriguingly it's easy to prove certain things about the relations I call factoring congruences and in doing so prove mathematically that they solve the factoring problem, without actually demonstrating with a factorization.

The Diophantine system of equations that I use is

x^2 = y^2 + pr_1

and

z^2 = y^2 + nT

where T is the target to be factored. 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).

First off, 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.

Notice 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, as long as nT = (1 + a^2) k^2 + p(r_1 + kr_2), and in the derivation (which I posted a while back) I cover how you know that you can do that, though 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.

So I've covered how I further connect the system of two Diophantine equations, covered why a solution must always exist and shown why you have 'a' and 'k'. All that effort is about finding rules governing the system, which I call the factoring congruences.

In the previously posted derivation I show how you get the factoring congruences so I'll just give them here versus deriving them in detail again:

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

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

and

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

So remarkably there are these rules governing the system, which were previously unknown, and they cover things that can happen versus those that cannot.

For instance, I have been using p=11 in my examples in past posts demonstrating the factoring congruences with T=119 and n=1, but let n=1 again, and let T=21, so I can connect with what I have above and look again at the list of some possible values for pr_1:

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

In that list you can just see when 11 is the prime as that last case given where pr_1 = 77. And notice that 7 is there when it's a factor of 21, which can help you see how all those limitations I had in place, like I thought nT had to be coprime to pr_1, were just wrong, and of course nT can have 3 as a factor as 21 does.

Now since I found the factoring congruence relations by derivation, solving out with z^2 = y^2 + nT, but the equations end up just using nT mod p, you get the odd result that the answers given will apply to every nT that has the same residue modulo p. Which is just so weird that it bugged me for a while, but the math says it must be true.

But then, you can always factor T, if it is the product of two primes, by just using z-y mod p and z+y mod p, if p is chosen such that p>sqrt(T), and you get the non-trivial factorization.

So, if you find all a's that will work such that k exists, and remember

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

then you WILL non-trivially factor T, as the answers you get for z and y mod p will simply bounce between giving you the residues of T mod p and 1, or giving you the residues of the prime factors modulo p, and one of them must be less than p, unless T=p^2, so it must have itself as its residue.

The factor will just pop out directly as an answer, which you know by mathematical proof.

Now, based on classical thinking in this area, it seems likely that k will exist about 50% of the time, but the mathematics is kind of weird here, so it may make it harder to find k than that if you loop through values for 'a' that you check to see if they work. I know, for instance, with p=11, and nT mod 11 = 9, there are only four possible values for the a's: 2, -2, 5 and -5. That's it, over infinity, so you have this odd thing that with 9 + 11c, where c is an integer, you can work out ALL the residues modulo 11 that can occur as residues of the factors modulo 11.

So I'm not sure that you can rely on just letting n=1 and finding an 'a' that will work. But you CAN set 'a' and definitely find an 'n' that will work, and then you use p>sqrt(nT), if you can though you might have to do some juggling to get a p that is large enough while setting 'n', but I'm not sure, but now you will have a chance of factoring nT, and might get a prime of your target in that way, again from z-y mod p and z+y mod p, but now rather than just seeing the prime itself, you'd pull it out with a gcd with nT.

And that is a solution to the factoring problem, which represents the approach I think would make the best for algorithms, as you don't search for 'a', and you don't have to resolve a quadratic residue modulo p.

Now I had given most of the algorithm before in a prior post replying to a poster who claimed to be working on an implementation, but I had all kinds of extra rules which I now know are unnecessary, so nT does not have to be coprime to 3, and small prime factors are not an issue for 'n'.

But even with those extras, a real implementation should have worked remarkably well, so I know that the poster who claimed to have implemented, could not have, and since he gave supposed results showing failure, I know those had to be fabrications.

Mathematical proof makes it easy and the proof behind these remarkable congruences is so easy as the hardest thing is completing the square!

A very trivial proof in terms of mathematical difficulty with a very easy explanation means it's trivial to know when people are wrong about this result.

It solves the factoring problem as easily shown by mathematical proof and the denial about that by the mathematical community up to this point is just unfathomable.

[A reply to someone who asked James how rapidly does the number of a's or n's to be checked increase for large values of T and whether or not did he have a way of keeping that number down to a reasonable size even when T becomes very large.]

The conclusion I have is that you will get an answer for a factorization, no matter what. That is, every 'a' that works to give you a k, will give you a z mod p and a y mod p such that z-y mod p or z +y mod p will give you the residues modulo p for SOME factorization of nT.

Now that is the weird result that bothers me so much as it seems so strange, and there is a reflex kind of thinking where I figure that maybe some z mod p and y mod p just are junk and don't connect to anything, but that's not what the math says.

There is no way trivial factorizations can be preferred as the trivial factorization just gives you two cases for the factors: T mod p and 1, or -T mod p and 1

So they can only account for TWO CASES though I think that multiple a's may give you those cases, but they have to also evenly cover all the others.

So the short answer is that without regard to the size of nT, these methods should factor nT very quickly with a limited search, unless there is something else I missed.

It is a weird result given everything we used to know about factoring. But all that went out the window with the two equation system.

Mathematicians were studying one equation when two were controlling.

With only half the decision equations in hand, factoring is a hard problem. With both, it's not.