Harristotelian Logic

With z^2 = y^2 + mT, where T is the target composite to be factored, m is a non-zero integer of your choice, and N is an odd prime or composite of your choice, with a probability calculation shown below you may find the following to be true:

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

where 'a' is coprime to N, and

k^2 = (a^2+1)^{-1}(mT) mod N

(notice that you calculate k, by finding 'a' such that it exists and then you can get z)

and y can be calculated then from y^2 = z^2 - mT modulo N, and resolving the quadratic residue.

But as a special case if N = p^c, where c is a natural number, then y can be solved for directly: y = (2a)^{-1}k mod p

and the factors modulo N can be found directly, where with f_1*f_2=mT:

f_1 = ak mod N

and

f_2 = a^{-1}(a^2 + 1)k mod N

Otherwise your factors f_1 and f_2 where f_1*f_2 = mT, can be found from

f_1 = z-y mod N, and f_2 = z+y mod N.

Notice that allowing composites with N versus primes with p, changes things slightly.

If the total count of quadratic residues of N is c, then the probability is (1-(1-c/(N-1))^2)*(100%).

And there is no general congruence solution of y, unless N has only one prime factor.

Example:

Let m=1, T=119, N=15. I find that no 'a' will work, so that N gives no solutions.

Ok, so I'll try N=9, then a = 1 will work.

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

so k=1 mod 9 is an answer.

z = (2a)^{-1}(1 + 2a^2)k mod N = (2)^{-1}(3)(1) mod 9 = 6 mod 9.

Then y^2 = 36 - 119 mod 9 = 7, and y = 5 mod 9 is a solution.

Then f_1 = z - y mod N = 1 mod 9

and

f_2 = z + y mod N = 2 mod 9.

But I have something interesting here as I need to subtract 9, to get

f_1 = -8 mod 9 and f_2 = -7 mod 9

showing how negative solutions are a solution.

Notice you can also directly solve for f_1 mod 9 and f_2 mod 9, since the only prime factor is 3:

f_1 = ak mod N = 1 mod 9

and

f_2 = a^{-1}(1 + a^2)k mod N = (2)(1) mod 9

and subtracting 9 from each gives f_1 = -8 mod 9, and f_2=-7 mod 9, as before.

And notice that 7 is given directly as a factor, which had to happen
as I picked an N greater than the smallest prime factor of 119.

To derive the factoring congruences for yourself, just use two congruences where mathematicians traditionally (and wrongly) use only one:

x^2 = y^2 mod N

and

z^2 = y^2 mod T.

Then introduce k and 'a' with 2ax = k mod N, and note that you can then multiply through by k itself to get 2axk = k^2 mod N, and add that now to the first congruence to get

x^2 + 2axk = y^2 + k^2 mod N

and now, of course, you simply add a^2 k^2 to both sides and complete the square and simplify slightly to get

(x+ak)^2 = y^2 + (a^2 + 1)k^2 mod N

and set mT = (a^2 + 1)k^2 mod N, and let z = x+ak.

I'll leave it as an exercise to prove the existence of solutions to get the probability for finding instances where 'a' and k exist such that the congruences hold.

Oh yeah, the research is cutting edge, or as I like to say, bleeding edge, as there is nothing else out there in number theory that even comes close to allowing you to get f_1 mod N and f_2 mod N in general in a straightforward way—except of course factoring the target T first.

Nothing in the literature, at all.

The advancement to human knowledge is fairly huge.

Enjoy!!!