Friday, June 06, 2008
JSH: Iterative process, factoring
To me it's just such a remarkable journey to do basic mathematical research where you start with a concept and look to figure out the mathematics that says the concept is viable or it's not. And today we have advantages that just were not on this planet before. Modern problem solving techniques are just so much more powerful than what was known in the past when researchers were often more like hobbyists like Fermat or introducing new systems like Newton, whereas today, the science and art of problem solving is fully matured.
It only makes sense that people using the best techniques of our modern era can figure out extraordinary things.
I've been trained to use iterative processes and brainstorming so the oddity of the posting style that I use is easily explained as throwing ideas out there as part of brainstorming, and there is usually a progression through a fairly structured process to each iteration.
With factoring after considering what was previously known I asked myself, can you maybe factor one number by using the factorization of some other number?
And that was just a question, which became a concept I called surrogate factoring and that start was over 4 years ago.
I've talked to people who are amazed that you can work on a math problem for years, but for readers on these forums it should not, of course, sound all that remarkable. What is I think remarkable though is the simple answer that years of iterations, with lots of brainstorming, so many posts, so many false starts and so much analysis has brought:
To solve for positive integer x, when x^2 = y^2 mod N, where N is an odd target composite to be factored you can use helper primes to solve the explicit equation:
x^2 = y^2 + cN
where c is an integer chosen to force cN mod 3 = 2, where for each prime that works you will have
x^2 = 8^{-1}(9cN) mod p
where p is an odd prime that is less than 2x/3 for which the quadratic residue exists, but further it must be true that the residue given by a prime in that range for which a quadratic residue exists must give an x near a value I call x_0 where x_0 is the largest positive integer divisible by 3 such that
abs(cN - 8x_0^2/9)
is a minimum, and x must be within x_0/(3p) positive steps from x_0.
That the question of whether or not one factorization can lead to another then has a surprising answer which represents the outcome of over four years of basic research.
Weird thing is that the derivation of
x^2 = 8^{-1}(9cN) mod p
is easy to the point of trivial so I've presented it a lot (see other threads), while the other rules are harder to explain so you'd have to dig a bit to understand where they come from, where that last part about x_0 is rather remarkable in terms of the why of the constraint.
I will say a few words about how I do problem solving which typically does include some insults in a post, often lambasting the mathematical community, which has a lot to do with motivating replies to my posts so that I can get other people looking over mathematical ideas. Years of experience on newsgroups has taught me that conflict draws readers and without it, you don't get readers at the same level.
Maybe unfortunate but it is the reality that I've found to be true in my experiments with what works and what does not as that has been an iterative process and a lot about problem solving as well.
If some other technique worked better, I'd use it.
[A reply to someone who suggested that James should write some code.]
I've written code before that factors numbers though not very large as I think it was usually right in the 40 bit range. For people who wonder what 40 bits is, it's numbers larger than 2^40 or 1099511627776. Those are considered small for factoring.
My experience is that posters deny any and all evidence or just keep raising the bar until the request is to demonstrate factoring better than anything else previously known.
The behavior as I've noted before is like saying that unless Albert Einstein built a working atomic bomb, and exploded it, his research was garbage.
The theory guy doesn't have to be the implementing guy or team.
Sometimes you just need to open the door and reasonable people can see value in your research effort, as we live in a very connected world. If there is anything to this research I'm sure there will be people building on it, which frees me up to consider theoretical issues.
[A reply to someone who told James that Einstein never claimed that he could build an atomic bomb.]
Scaling a solution can present challenges that have nothing to do with whether or not the theoretical solution is correct.
Mathematical theory says I've solved the factoring problem, like an interpretation of Einstein's research (along with that of others) indicated there were nuclear applications available.
But producing the practical product from theory can be a different enterprise.
The mathematical theory is about mathematical proof, which says the problem is solved.
Disbelief in mathematical proof can lead to a request for demonstration as if only seeing is believing.
Real mathematicians, however, know that mathematical proof means that the thing can be done.
You people could do something more useful and attack the claim of proof versus asking for a demonstration as if only an example can prove a proof, which displays a basic ignorance of mathematics, as examples can be nice but proof is proof.
[A reply to someone who explained James that no barrier prevents him from implementing of a solution to the factoring problem.]
I don't have to factor anything.
Of one thing there is little doubt in my mind it's if I'm right then someone will do the grunt work.
Now if you deny that then you're insane.
Why argue?
If I have solved the factoring problem and I say theory proves it, and I'm not implementing then if I am correct someone in the world will do the rest, so why bother arguing?
It's just stupid.
[A reply to someone who asked James how long will it be with nobody implementing his solution before he realises that he is wrong again.]
I'm not wrong. The derivation is trivial. All your arguing is equivalent to claiming that given
z^2 = y^2 + nT
x^2 = y^2 mod p
2x = k and z = x + k
that it's meaningless that
z^2 = 8^{-1} (9nT) mod p
which is a DERIVED result. If the derivation is useless then the algebra that gives it is nonsensical and lost, like a human being.
Issues around finding p as an odd prime are separate from the mathematical reality that those 4 equations give that result, which is about loving mathematics for what it tells us, not denying it for human reasons.
[A reply to someone who asked James how often does he reconsider his assertions that
Daily. Or better yet, several times a day.
People, including myself, are notable for easily being complete fools, idiots and total morons for things they want to believe. And are quite capable of doing so to unseemly limits, like blowing themselves up.
We as a species are remarkably bonkers in general.
I fully believe that I am quite capable of being totally and completely wrong, and believing I'm right indefinitely, and have reached a point where I find I trust little if anything, especially myself.
Sometimes I believe that our planet is best simply described as world of fools and I may be one of the greatest of all time.
It only makes sense that people using the best techniques of our modern era can figure out extraordinary things.
I've been trained to use iterative processes and brainstorming so the oddity of the posting style that I use is easily explained as throwing ideas out there as part of brainstorming, and there is usually a progression through a fairly structured process to each iteration.
With factoring after considering what was previously known I asked myself, can you maybe factor one number by using the factorization of some other number?
And that was just a question, which became a concept I called surrogate factoring and that start was over 4 years ago.
I've talked to people who are amazed that you can work on a math problem for years, but for readers on these forums it should not, of course, sound all that remarkable. What is I think remarkable though is the simple answer that years of iterations, with lots of brainstorming, so many posts, so many false starts and so much analysis has brought:
To solve for positive integer x, when x^2 = y^2 mod N, where N is an odd target composite to be factored you can use helper primes to solve the explicit equation:
x^2 = y^2 + cN
where c is an integer chosen to force cN mod 3 = 2, where for each prime that works you will have
x^2 = 8^{-1}(9cN) mod p
where p is an odd prime that is less than 2x/3 for which the quadratic residue exists, but further it must be true that the residue given by a prime in that range for which a quadratic residue exists must give an x near a value I call x_0 where x_0 is the largest positive integer divisible by 3 such that
abs(cN - 8x_0^2/9)
is a minimum, and x must be within x_0/(3p) positive steps from x_0.
That the question of whether or not one factorization can lead to another then has a surprising answer which represents the outcome of over four years of basic research.
Weird thing is that the derivation of
x^2 = 8^{-1}(9cN) mod p
is easy to the point of trivial so I've presented it a lot (see other threads), while the other rules are harder to explain so you'd have to dig a bit to understand where they come from, where that last part about x_0 is rather remarkable in terms of the why of the constraint.
I will say a few words about how I do problem solving which typically does include some insults in a post, often lambasting the mathematical community, which has a lot to do with motivating replies to my posts so that I can get other people looking over mathematical ideas. Years of experience on newsgroups has taught me that conflict draws readers and without it, you don't get readers at the same level.
Maybe unfortunate but it is the reality that I've found to be true in my experiments with what works and what does not as that has been an iterative process and a lot about problem solving as well.
If some other technique worked better, I'd use it.
[A reply to someone who suggested that James should write some code.]
I've written code before that factors numbers though not very large as I think it was usually right in the 40 bit range. For people who wonder what 40 bits is, it's numbers larger than 2^40 or 1099511627776. Those are considered small for factoring.
My experience is that posters deny any and all evidence or just keep raising the bar until the request is to demonstrate factoring better than anything else previously known.
The behavior as I've noted before is like saying that unless Albert Einstein built a working atomic bomb, and exploded it, his research was garbage.
The theory guy doesn't have to be the implementing guy or team.
Sometimes you just need to open the door and reasonable people can see value in your research effort, as we live in a very connected world. If there is anything to this research I'm sure there will be people building on it, which frees me up to consider theoretical issues.
[A reply to someone who told James that Einstein never claimed that he could build an atomic bomb.]
Scaling a solution can present challenges that have nothing to do with whether or not the theoretical solution is correct.
Mathematical theory says I've solved the factoring problem, like an interpretation of Einstein's research (along with that of others) indicated there were nuclear applications available.
But producing the practical product from theory can be a different enterprise.
The mathematical theory is about mathematical proof, which says the problem is solved.
Disbelief in mathematical proof can lead to a request for demonstration as if only seeing is believing.
Real mathematicians, however, know that mathematical proof means that the thing can be done.
You people could do something more useful and attack the claim of proof versus asking for a demonstration as if only an example can prove a proof, which displays a basic ignorance of mathematics, as examples can be nice but proof is proof.
[A reply to someone who explained James that no barrier prevents him from implementing of a solution to the factoring problem.]
I don't have to factor anything.
Of one thing there is little doubt in my mind it's if I'm right then someone will do the grunt work.
Now if you deny that then you're insane.
Why argue?
If I have solved the factoring problem and I say theory proves it, and I'm not implementing then if I am correct someone in the world will do the rest, so why bother arguing?
It's just stupid.
[A reply to someone who asked James how long will it be with nobody implementing his solution before he realises that he is wrong again.]
I'm not wrong. The derivation is trivial. All your arguing is equivalent to claiming that given
z^2 = y^2 + nT
x^2 = y^2 mod p
2x = k and z = x + k
that it's meaningless that
z^2 = 8^{-1} (9nT) mod p
which is a DERIVED result. If the derivation is useless then the algebra that gives it is nonsensical and lost, like a human being.
Issues around finding p as an odd prime are separate from the mathematical reality that those 4 equations give that result, which is about loving mathematics for what it tells us, not denying it for human reasons.
[A reply to someone who asked James how often does he reconsider his assertions that
- If he is right, then someone will factor big numbers using his method.
- He is right.]
Daily. Or better yet, several times a day.
People, including myself, are notable for easily being complete fools, idiots and total morons for things they want to believe. And are quite capable of doing so to unseemly limits, like blowing themselves up.
We as a species are remarkably bonkers in general.
I fully believe that I am quite capable of being totally and completely wrong, and believing I'm right indefinitely, and have reached a point where I find I trust little if anything, especially myself.
Sometimes I believe that our planet is best simply described as world of fools and I may be one of the greatest of all time.
# posted by James Harris @ 23:10 
