Harristotelian Logic

Ok, sorry, as I hate it to some extent when a problem turns out to be harder to solve than I thought when some part of me must kind of know the answer but it takes a while for the rest of me to get it.

Here's the correct answer to the factoring problem where I just kind of diverged a bit before.

I was puzzling about the latest failed factoring idea wondering where I went wrong, as I really felt that there was information wrapped up in the intersection of the residues modulo T of two primes.

So I pondered some more.

Before too long I was writing out things along these lines:

(f_1 + c_1*p_1)(f_2 + c_2*p_1) = T = (r_1 + k_1*p_1)

and

(g_1 + d_1*p_2)(g_2 + d_2*p_2) = T = (r_2 + k_2*p_2)

And I multiplied out and solved for k_1 and k_2 respectively and again pondered what if you GUESSED using f_1*f_2 = T mod p_1 and g_1*g_2 = T mod p_2, so you'd know the f's and the g's, and I realized that then you could just solve for the c's by using

(f_1 + c_1*p_1) = (g_1 + d_1*p_2)

and

(f_2 + c_2*p_1) = (g_2 + d_2*p_2)

and I realized you could solve for everything and reduce to a solution for d_1.

That's from before, but after that point, before, I went in the wrong direction as it is so OBVIOUS what you should do next, which is solve d_1 modulo p_1 (maybe I was sleepy when I first typed that last).

d_1 = (f_1 - g_1)*p_2^{-1} mod p_1

and then you also need d_2, so

d_2 = (f_1 - g_2)*p_2^{-1} mod p_1

and now you can substitute modulo p_1 into, oh, forgot something:

(g_1 + d_1*p_2)(g_2 + d_2*p_2) = T = (r_2 + k_2*p_2)

multiply out, and divide by p_2, using m_2 = (g_1*g_2/p_2), and you can get to

k_2 = d_1*g_2 + d_2*g_1 + d_1*d_2*p_2 + m_2

so now you just substitute modulo p_1 and compare what you get on the right side with k_2 mod p_1 as you know what k_2 is, since

k_2 = floor(T/p_2).

If you guessed correctly then you will match with k_2's residue modulo p_1, but if you didn't, you shouldn't match unless this doesn't work either!!!

So if you don't match you try another possible and try until you match, and do that for a series of primes where the total is less than m, such that T/m! < 1, or you can get an exact number by multiplying primes together—assuming you start with the smallest and go up—until you exceed T, and counting how many you have.

That is the solution to the factoring problem.

It's stupid simple.

I just took a little time to figure out exactly how the damn thing worked.

But that's problem solving for you. Some part of me must have known the answer but the rest of me was stupid, until simple won.

[A reply to someone who asked James why doesn't he just guess p1 such that T/p1 is integer.]

Funny. Ok, yes, I admit it. I went on and on about having solved the factoring problem through an intersection of primes when I hadn't shown it.

So I had a strong feeling that there had to be a way to do it, and then got waylaid in figuring out exactly how, but this latest result is actually consistent with the original idea while what I had before was not.

Here you DO test, and the guess just gets you SOME information, so you need a series of primes.

The approach IS straightforward and it is stupid, simple, so get mad and upset about the problem solving process but that just shows you have no clue how it really works.

Mostly it's about hard work, lots of misses and being willing to keep beating on that hunch until it pays off, and later let the freaking historians re-write history and talk about what a genius you are.

It's a big mess until you're right.

During the process most of the time you feel like a freaking idiot.

[A reply to someone who said that the issue is to find an efficient algorithm.]

If the approach holds i.e. if the values for d_1 mod p_1 and d_2 mod p_1 are provisional values that work only when you guess correctly, then this approach DOES lead to an efficient algorithm.

It turns out that it is well-known that if you have f_1 mod p_1, and f_1 mod p_2, … f_1 mod p_n, where n is a sufficient number of primes then you have f_1 explicitly.

The problem though has been, how do you find f_1 modulo successive primes?

I contemplated this issue and hypothesized that when you have two primes you have some kind of intersection that will give the answer, and I went looking for that intersection.

My first approaches went awry as I tried to actually solve for d_1 exactly, but thinking about why those approaches didn't work, I looked at the equations again and saw:

d_1 = (f_1 - g_1)*p_2^{-1} mod p_1

and I had everything I needed where BOTH primes gave input, so I had my intersection.

So this approach IS a valuable one as long as the hypothesis holds true and the value of d_1 modulo p_1 found above is invalid unless you've guessed f_1 and g_1 correctly, as those are residues, where

f_1*f_2 = T mod p_1 and g_1*g_2 = T mod p_2

and are NOT the full solutions. Maybe I could have picked other variable letters.

In any event, the point is an intersection between two primes with a guess at residues and checking to see if the guess is right.

If you can do that then factoring is trivial as you need less primes than m, where T/m! < 1.

So you have factorial working for you here, and that is a big over-estimate for m.

If this approach holds water then factoring an RSA public key of any size possible on modern desktop computers would be trivially done in minutes if not seconds.

The factoring problem is solved by using the intersection of prime numbers, in an elegant, precise, and remarkably short solution.