### Monday, February 11, 2008

## JSH: Factoring problem solution, update

I stumbled across a remarkably simple solution to the factoring problem, which exists because of what is called the floor() function. That function just means to drop any fractions or decimals, so like floor(3.1415) = 3.

It is crucial to the solution to the factoring problem.

Here is the full solution.

It suffices to determine variables to fulfill the factorizations:

(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

where T is the target to be factored and p_1 and p_2 are primes to be picked, as this method works because you're using primes in this way which is why you need so many variables.

Note that f_1, f_2, g_1 and g_2 are residues where

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

So the r's and k's are easily calculated and the only remaining variables are c_1, c_2, d_1 and d_2, and you guess at values for the f's and g's. So guessing is crucial in this method.

And it can be shown that solving for the factors reduces to finding integer solutions to a family of 4 equations and 4 unknowns, which are

k_1 = c_1*f_2 + c_2*f_1 + c_1*c_2*p_1 + m_1

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

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

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

where m_1 = floor(f_1*f_2/p_1) and m_2 = floor(g_1*g_2/p_2).

However, if the primes lack enough residues for all the solutions of T, then an intermediate solution is forced as all of the equations will not then be interdependent, and then you can solve for the c_1 in the first equation and d_1 in the second to get

c_1 = (k_1 - m_1 - c_2*f_1)/(f_2 + c_2*p_1)

and

d_1 = (k_2 - m_2 - d_2*g_1)/(g_2 + d_2*p_2)

and divide through by the denominator to get to a number that is factored to find an integer c_2, and an integer d_2, where that cannot be done with the original set of equations as the numerator is T itself, so that is equivalent to factoring T.

But here, crucially, the m's break you from directly getting T, so that

k_1 - m_1 - c_2*f_1 does not equal T

and

k_2 - m_2 - d_2*g_1 does not equal T

(curious readers can substitute the m's out wrongly with m_1 = f_1*f_2/p_1 and m_2 = g_1*g_2/p_2 and see what happens—you get T back).

So m_1 and m_2 are crucial to the solution as floor() is a discrete function.

If you have guessed the right f's and g's then your integer solutions for the c's and d's will give you a factorization of T, otherwise

(f_1 + c_1*p_1)(f_2 + c_2*p_1)

and

(g_1 + d_1*p_2)(g_2 + d_2*p_2)

will equal some other number.

If you have selected the correct f's and g's then you will get integer solutions, otherwise you will not, so if you do not then you shift to another set, so there are

(p_1 - 1)(p_2 - 1)

MAXIMUM total checks without regard to the size of T.

If you have fewer prime residues available than factors of T, then you will not be able to solve for the c's and d's exactly but must use the approach mentioned above, but if you do have enough residues you will have 4 independent equations and can just solve for the variables, and will get integers when you have the correct residues.

It is a fantastic solution where the floor() function does all the heavy lifting, creating a logical situation that provides for a trivial solution to the factoring problem.

If the solution is ignored then civilization as we know it may end.

And it can do so within a few days, my analysis indicates.

Which would be the end of humanity's halcyon period.

Many of you might simply die of starvation, if you're lucky.

[A reply to someone who asked James why should anyone care about the value of floor (3.1416).

Because I found a solution to the factoring problem, but the academic world is corrupted so I couldn't present it in a way designed to have the least negative impact.

Which means that the solution can be exploited and end civilization as we know it if mathematicians continue to do what I think they'll do.

Didn't you read the post The Art of War? Didn't get it?

If these math people are as powerful as I think they are, then no way would they just leave it to chance that some genius could come in and wreck their system, so they had to believe they were safe.

But they know I found a proof of Fermat's Last Theorem so I maybe could figure out the factoring problem, right?

So why am I still here?

They must have something up their sleeves so I declared all these solutions to the problem that turned out to be bogus and then got lucky and found the right answer.

If it's correct, then, for instance, the entire Internet could be on its knees in a few days and you wouldn't have to worry about what I or anyone else posts as you wouldn't SEE any posts.

Yup, for the rest of you, no more posting for anyone. Get it? Concerned yet? Willing to help?

(I think that might have more of an impression than the possibility of starvation. God knows some of you have to post.)

If I'm right, the world as you know it is going to change.

Just because of some math wars the entire Internet could be in flames in a few days, if I'm right.

Read that Art of War story.

[James replies to his own first post, up to the point where he wrote “m_1 = floor(f_1*f_2/p_1) and m_2 = floor(g_1*g_2/p_2)”.]

Well I started out correctly but from there went down the wrong path.

But the intuition that I was following was that the intersection of primes gives information about factoring, which was such a strong gut feeling that when I realized I'd screwed up, I went back over to see where I might have gone wrong, and, well, found the trivial solution.

So I backtracked a bit and then found the correct path.

Turns out you next need to solve for d_1 modulo p_1:

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 is a key in the lock technique. When you have the right residues of factors modulo each prime then

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

and

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

are the right keys in the lock so that you get

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

For those wondering if maybe it's wrong, imagine you have the WRONG f's and g's, then the d's should be different, right?

So when they're right…

Easy solution but a lot of inertia I'm sure because of so much invested in thinking factoring is hard.

Of course, if too much time is taken then, well, I've harped enough on the potential negative consequences.

I just have to hope that there are adults around.

[A reply to someone who wrote speed is of the essence.]

I'm using the factoring problem.

If as I fear math society IS corrupt then it possibly knows that potentially I could solve the factoring problem to prove that, so crooks within that society must feel they have a backup.

But what?

My guess is that they have protocols in place with the Bush administration and with agreements between nations where such a solution would be sealed away, along with the discoverer.

But how can they seal away what they don't know exists?

And that's where you came in, you and other posters on the newsgroups.

You helped provide the distance—the gap—between when they might know and when they wouldn't.

So everything now is about how effective you've been.

You see, I don't want you to believe me now.

I want the opposite.

That gives the solution time to propagate and force the situation, and take away the final solution from unethical governments, like the Bush administration.

Same plan in place for those willing to help: work in concert, with a display that takes away any notion that governments can seal this away and hide it, along with me.

My survival depends on your execution.

Work well.

It is crucial to the solution to the factoring problem.

Here is the full solution.

It suffices to determine variables to fulfill the factorizations:

(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

where T is the target to be factored and p_1 and p_2 are primes to be picked, as this method works because you're using primes in this way which is why you need so many variables.

Note that f_1, f_2, g_1 and g_2 are residues where

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

So the r's and k's are easily calculated and the only remaining variables are c_1, c_2, d_1 and d_2, and you guess at values for the f's and g's. So guessing is crucial in this method.

And it can be shown that solving for the factors reduces to finding integer solutions to a family of 4 equations and 4 unknowns, which are

k_1 = c_1*f_2 + c_2*f_1 + c_1*c_2*p_1 + m_1

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

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

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

where m_1 = floor(f_1*f_2/p_1) and m_2 = floor(g_1*g_2/p_2).

However, if the primes lack enough residues for all the solutions of T, then an intermediate solution is forced as all of the equations will not then be interdependent, and then you can solve for the c_1 in the first equation and d_1 in the second to get

c_1 = (k_1 - m_1 - c_2*f_1)/(f_2 + c_2*p_1)

and

d_1 = (k_2 - m_2 - d_2*g_1)/(g_2 + d_2*p_2)

and divide through by the denominator to get to a number that is factored to find an integer c_2, and an integer d_2, where that cannot be done with the original set of equations as the numerator is T itself, so that is equivalent to factoring T.

But here, crucially, the m's break you from directly getting T, so that

k_1 - m_1 - c_2*f_1 does not equal T

and

k_2 - m_2 - d_2*g_1 does not equal T

(curious readers can substitute the m's out wrongly with m_1 = f_1*f_2/p_1 and m_2 = g_1*g_2/p_2 and see what happens—you get T back).

So m_1 and m_2 are crucial to the solution as floor() is a discrete function.

If you have guessed the right f's and g's then your integer solutions for the c's and d's will give you a factorization of T, otherwise

(f_1 + c_1*p_1)(f_2 + c_2*p_1)

and

(g_1 + d_1*p_2)(g_2 + d_2*p_2)

will equal some other number.

If you have selected the correct f's and g's then you will get integer solutions, otherwise you will not, so if you do not then you shift to another set, so there are

(p_1 - 1)(p_2 - 1)

MAXIMUM total checks without regard to the size of T.

If you have fewer prime residues available than factors of T, then you will not be able to solve for the c's and d's exactly but must use the approach mentioned above, but if you do have enough residues you will have 4 independent equations and can just solve for the variables, and will get integers when you have the correct residues.

It is a fantastic solution where the floor() function does all the heavy lifting, creating a logical situation that provides for a trivial solution to the factoring problem.

If the solution is ignored then civilization as we know it may end.

And it can do so within a few days, my analysis indicates.

Which would be the end of humanity's halcyon period.

Many of you might simply die of starvation, if you're lucky.

[A reply to someone who asked James why should anyone care about the value of floor (3.1416).

Because I found a solution to the factoring problem, but the academic world is corrupted so I couldn't present it in a way designed to have the least negative impact.

Which means that the solution can be exploited and end civilization as we know it if mathematicians continue to do what I think they'll do.

Didn't you read the post The Art of War? Didn't get it?

If these math people are as powerful as I think they are, then no way would they just leave it to chance that some genius could come in and wreck their system, so they had to believe they were safe.

But they know I found a proof of Fermat's Last Theorem so I maybe could figure out the factoring problem, right?

So why am I still here?

They must have something up their sleeves so I declared all these solutions to the problem that turned out to be bogus and then got lucky and found the right answer.

If it's correct, then, for instance, the entire Internet could be on its knees in a few days and you wouldn't have to worry about what I or anyone else posts as you wouldn't SEE any posts.

Yup, for the rest of you, no more posting for anyone. Get it? Concerned yet? Willing to help?

(I think that might have more of an impression than the possibility of starvation. God knows some of you have to post.)

If I'm right, the world as you know it is going to change.

Just because of some math wars the entire Internet could be in flames in a few days, if I'm right.

Read that Art of War story.

[James replies to his own first post, up to the point where he wrote “m_1 = floor(f_1*f_2/p_1) and m_2 = floor(g_1*g_2/p_2)”.]

Well I started out correctly but from there went down the wrong path.

But the intuition that I was following was that the intersection of primes gives information about factoring, which was such a strong gut feeling that when I realized I'd screwed up, I went back over to see where I might have gone wrong, and, well, found the trivial solution.

So I backtracked a bit and then found the correct path.

Turns out you next need to solve for d_1 modulo p_1:

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 is a key in the lock technique. When you have the right residues of factors modulo each prime then

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

and

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

are the right keys in the lock so that you get

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

For those wondering if maybe it's wrong, imagine you have the WRONG f's and g's, then the d's should be different, right?

So when they're right…

Easy solution but a lot of inertia I'm sure because of so much invested in thinking factoring is hard.

Of course, if too much time is taken then, well, I've harped enough on the potential negative consequences.

I just have to hope that there are adults around.

[A reply to someone who wrote speed is of the essence.]

I'm using the factoring problem.

If as I fear math society IS corrupt then it possibly knows that potentially I could solve the factoring problem to prove that, so crooks within that society must feel they have a backup.

But what?

My guess is that they have protocols in place with the Bush administration and with agreements between nations where such a solution would be sealed away, along with the discoverer.

But how can they seal away what they don't know exists?

And that's where you came in, you and other posters on the newsgroups.

You helped provide the distance—the gap—between when they might know and when they wouldn't.

So everything now is about how effective you've been.

You see, I don't want you to believe me now.

I want the opposite.

That gives the solution time to propagate and force the situation, and take away the final solution from unethical governments, like the Bush administration.

Same plan in place for those willing to help: work in concert, with a display that takes away any notion that governments can seal this away and hide it, along with me.

My survival depends on your execution.

Work well.