Harristotelian Logic

ON August 9th I stepped through integer factorization equations in my post "JSH: On integer factorization" and earlier today I thought some more about when that approach might work to give a non-trivial factorization.

Those equations were

y^2 = x^2 mod T

and

k = 2x mod T

where T is the target composite to be factored. You can easily find by multiplying the second by k, adding to the first and completing the square and then going to an explicit equation that

(x+k)^2 = y^2 + 2k^2 + n*T

where n is some non-zero integer, so that now you may factor T by instead factor 2k^2 + nT, but how do you pick k and n?

I have approached the problem by wondering what would happen if

T = p_1*p_2

where the p's are differing primes, if you picked x.

Well that gives you k, but can any x work? The answer comes from the first congruence as you need to solve for x using two linear equations:

x+y = c_1*p_1

and

x-y = c_2*p_2

where the c's non-zero integers and that is trivial and gives you

2x = c_1*p_1 + c_2*p_2

so a solution can always be found with

c_1 = (2x)*(p_1)^{-1} mod p_2

now assume p_1>p_2, then the maximum size of the modular inverse of p_1 with respect to p_2 is p_2 - 1, so the maximum size for c_1 is

c_1<= (2x)*(p_2-1)

so you have roughly c_1*p_1 < 2x*T.

Now you can also solve for y with those two linear equations to get

y = (c_1*p_1 - c_2*p_2)/2

so then y<x*T, so if that is in the size range of 2k^2 + n*T then you factor non-trivially.

As from before I have that

(x+k)^2 = y^2 + 2k^2 + n*T

so if I have rationals f_1 and f_2 where

4f_1*f_2 = 2k^2 + n*T

then

y = f_1 - f_2,

so the issue is managing the size of 2k^2 + n*T, so first assume that you find the smallest absolute size given by

n = -floor(2k^2/T)

and it may work, but if it does NOT work, then subtract 1 from n and you push up the absolute size, but I'm debating how much that increases the likelihood of a non-trivial factorization.

If p_1 is very much larger than p_2 then it seems reasonable to suppose that y will roughly be the size of p_1, and it doesn't seem likely that it can be much smaller. So 2k^2 + n*T has to be above a minimum absolute size, and above that minimum I'd think factoring should occur with a high probability.

[A reply to someone who asked James if is at the stage where he can write some code that will factor efficiently.]

I like theory. Theoretically the size of 2k2 + nT is the key variable, as if it is too small, making it easier to factor, then y cannot be roughly the same size as the largest prime factor, if you have two prime factors where one is much larger than the other.

Now that is math.

Questioning the math, well that is politics.

It occurs to me that some sci.math'ers must believe that talking down math can be enough to convince people not to use it, or you may think that a viable factoring approach requires that I implement in some stunning algorithm that shuts down all debate.

And you believe that because the world has not noticed that I DID prove Fermat's Last Theorem, it fails to care when I show that Andrew Wiles didn't—even when I show a stupid logical flaw in his work—and can even ignore my prime number research.

And people thought mathematicians were in love with primes!

So people like you hope that you can talk down any mathematics, even if, if you fail, the world pays the price and people who trusted and saved lose those savings, and everything they built for decades because mathematicians learned to lie about math and thought they'd never get caught.

Oh yeah, didn't Jim Ferry claim that he programmed an efficient algorithm into Mathematica?

Was he lying? Hey, Jim! You out there? Were you lying?

If so, then you better say so, as I am increasingly confident in this approach, as I'm finally understanding when and how it should work, assuming I didn't make any major mistakes in my analysis.

But now comes the scary part, what to do? I KNOW mathematicians routinely lie about math, probably because they never took it seriously, and couldn't appreciate the consequences.

They make even stupid mistakes and play pretend smart for their niche audience that loves to believe they're smart no matter what.

They were just cons playing a simple game with stuff most people don't care about, but now there is a world on financial edge and it is deadly serious.

And mathematicians are just cons who played with fire, so why would they have any clue what to do now?

I don't know. For all I know, tomorrow could be a very bad day for the world's financial markets, but who really is to blame?