### Saturday, February 09, 2008

## JSH: Factoring trivially solved

Pondering the factoring problem I noticed that you can work things out explicitly relative to two primes:

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

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

Those are explicit equations for the same factorization of T, but doing it using two different prime numbers p_1 and p_2.

Notice that then

f_1*f_2 = T mod p_1

and

g_1*g_2 = T mod p_2

So the f's and g's there are RESIDUES.

Then you can guess at the f's and guess at the g's, and use

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

and

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

to solve for one of the c's or one of the d's which is just some relatively simple algebra.

So you have 4 equations and 4 unknowns.

Easy.

And a simple, trivial solution to the factoring problem.

Count the variables and equations, and then get over the shock.

[A reply to someone who told James that he should subtract 1 from 4 since his equations are not independent.]

The unknown variables are c_1, c_2, d_1 and d_2.

The four equations are:

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

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

and

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

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

which are only true if you guess at f_1, f_2 and g_1 and g_2

correctly, where those are residues and

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

Algebra just laid out so there is no doubt.

If you guess the f's and g's correctly then you can solve for an

integer value for one of the c's or one of the d's.

Trivial algebra.

So what are you claiming against the result?

The four equations are:

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

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

and

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

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

which are only true if you guess at f_1, f_2 and g_1 and g_2 correctly, where those are residues and

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

And yes it does matter to me when people come back to say I'm wrong and just keep arguing and arguing and arguing.

That is about as direct as you can get with algebra.

If you people can't be convinced with 4 equations and 4 unknowns in an algebraic system then there is truly no hope left all.

And the human race should just do the universe a favor and just die right now, as it has totally lost all connection with the truth.

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

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

Those are explicit equations for the same factorization of T, but doing it using two different prime numbers p_1 and p_2.

Notice that then

f_1*f_2 = T mod p_1

and

g_1*g_2 = T mod p_2

So the f's and g's there are RESIDUES.

Then you can guess at the f's and guess at the g's, and use

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

and

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

to solve for one of the c's or one of the d's which is just some relatively simple algebra.

So you have 4 equations and 4 unknowns.

Easy.

And a simple, trivial solution to the factoring problem.

Count the variables and equations, and then get over the shock.

[A reply to someone who told James that he should subtract 1 from 4 since his equations are not independent.]

The unknown variables are c_1, c_2, d_1 and d_2.

The four equations are:

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

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

and

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

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

which are only true if you guess at f_1, f_2 and g_1 and g_2

correctly, where those are residues and

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

Algebra just laid out so there is no doubt.

If you guess the f's and g's correctly then you can solve for an

integer value for one of the c's or one of the d's.

Trivial algebra.

So what are you claiming against the result?

The four equations are:

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

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

and

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

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

which are only true if you guess at f_1, f_2 and g_1 and g_2 correctly, where those are residues and

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

And yes it does matter to me when people come back to say I'm wrong and just keep arguing and arguing and arguing.

That is about as direct as you can get with algebra.

If you people can't be convinced with 4 equations and 4 unknowns in an algebraic system then there is truly no hope left all.

And the human race should just do the universe a favor and just die right now, as it has totally lost all connection with the truth.