### Saturday, February 09, 2008

## JSH: Little more explanation

I went looking for an answer to factoring in the intersection of primes thinking you'd need multiple primes, but found an approach that at first blush seems to allow you to just use two primes.

Weird. I may be wrong, so I'm just kind of tossing it out there and going to think about it more tomorrow.

But what happened to explain yet again what I just posted is that I was wondering about solutions expanded out a lot, like

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

where p_1 is the first prime, and you have your first factor, where f_1 is the residue of it modulo p_1, but I'm showing everything so I also include c_1, so that is the entire factor. I do the same for a second factor and isolate on the parts multiplied by primes to pull them out.

Then I notice that you can equate factors between primes and use guesses to solve for all the variables all the way down, and that is what freaked me out.

As it looks then that rather than needing a series of primes to factor any target composite, you'd only need two. And maybe only 2 and 3, which just sounds insane, so I'm thinking I must have missed something.

No way it's that easy. But it's just a bunch of freaking variables. I just took a slightly creative approach of focusing on what is multiplied by the primes versus the residues.

How can that just break the problem open completely to the point of it being trivial?

Just some variables, and some simple equations, and you solve for them, and get an answer. Just a bit of algebra so where did I screw up. Where's the mistake…hope there's a mistake, I guess.

It all just seems so sad. Just so sad.

Weird. I may be wrong, so I'm just kind of tossing it out there and going to think about it more tomorrow.

But what happened to explain yet again what I just posted is that I was wondering about solutions expanded out a lot, like

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

where p_1 is the first prime, and you have your first factor, where f_1 is the residue of it modulo p_1, but I'm showing everything so I also include c_1, so that is the entire factor. I do the same for a second factor and isolate on the parts multiplied by primes to pull them out.

Then I notice that you can equate factors between primes and use guesses to solve for all the variables all the way down, and that is what freaked me out.

As it looks then that rather than needing a series of primes to factor any target composite, you'd only need two. And maybe only 2 and 3, which just sounds insane, so I'm thinking I must have missed something.

No way it's that easy. But it's just a bunch of freaking variables. I just took a slightly creative approach of focusing on what is multiplied by the primes versus the residues.

How can that just break the problem open completely to the point of it being trivial?

Just some variables, and some simple equations, and you solve for them, and get an answer. Just a bit of algebra so where did I screw up. Where's the mistake…hope there's a mistake, I guess.

It all just seems so sad. Just so sad.