Harristotelian Logic

You people need to wake up. I'm telling you the underlying math is EASY. It's a technique to solve quadratic residues modulo N.

If you think it's not possible then use all of your mathematical training to explain the second example:

So now let's do, k=9. So q = 11 mod 35, and T = 22 mod 35, so I can try T = 57.

The trivial factorization didn't work here, so I'll just jump to, f_1 = 19, and f_2 = 3, so:

k = 3^{-1}(19 + 3) mod 35 = 12(22) mod 35 = 264 mod 35 = 19 mod 35.

19^2 = 11 mod 35

so it worked! (It's so weird though watching it. Even though I know the underlying mathematics it seems like magic.)

And that is a factoring example, as I know k=9 is a solution, so I have

19^2 = 9^2 mod 35

so (19-9)(19+9) = 0 mod 35, so (10)(28) = 0 mod 35, and you pull 5 and 7 as factors with a gcd.

THAT is how you use a method for solving quadratic residues modulo N: you find one quadratic residue and then go looking for another.

Factoring problem solved.

Happy one year birthday to the solution as it's a year old about now.