Monday, January 26, 2009
Figurate Numbers and factoring, pt. 2
Since my last post I've been playing a bit more specifically with square and triangle figurate numbers. And, there is an interesting modification you can do to turn an equation like this:
i.) c^2 == d^2 mod (n)
into this:
ii.) x^2 + ax == y^2 mod (b)
For example, let n = 51. We want to find:
iii.) c^2 == d^2 mod 51
So that we can factor 51. This can be modified so that we solve:
iv.) x^2 + 16x == y^2 mod 13
instead of the original congruence. Why would we want to do this? That is still, for me, an open question. In the book "Number Theory" by George E. Andrews there's a similar problem posed in section 9-4 (pg 127 in the Dover paperback edition):
"4. Does x^2 + 5x == 12 (mod 31) have a solution?"
The answer, in my view, hinges on several key issues. First, does knowing the factors of 16 and 13 make equation iv easier to solve or, more specifically, quicker to compute? Second, do all of the values of x and y which satisfy the congruence give us "useful" numbers for factoring n?
If the answer to the first two questions is yes, then we wind up with an interesting recursion -- let us assume for a moment that a and b (16 and 13 in equation iv, respectively) were very large numbers that were difficult to factor. If equation ii really is faster than i to solve, then it could be used to find the factors of a and b, which could in turn be used to factor n. Thus one could continue downward, if necessary, to factor large numbers by factoring smaller numbers first.
When I have a better grasp of what's going on, perhaps I can approach that recursion issue and see if it leads to a contradiction via infinite descent.
i.) c^2 == d^2 mod (n)
into this:
ii.) x^2 + ax == y^2 mod (b)
For example, let n = 51. We want to find:
iii.) c^2 == d^2 mod 51
So that we can factor 51. This can be modified so that we solve:
iv.) x^2 + 16x == y^2 mod 13
instead of the original congruence. Why would we want to do this? That is still, for me, an open question. In the book "Number Theory" by George E. Andrews there's a similar problem posed in section 9-4 (pg 127 in the Dover paperback edition):
"4. Does x^2 + 5x == 12 (mod 31) have a solution?"
The answer, in my view, hinges on several key issues. First, does knowing the factors of 16 and 13 make equation iv easier to solve or, more specifically, quicker to compute? Second, do all of the values of x and y which satisfy the congruence give us "useful" numbers for factoring n?
If the answer to the first two questions is yes, then we wind up with an interesting recursion -- let us assume for a moment that a and b (16 and 13 in equation iv, respectively) were very large numbers that were difficult to factor. If equation ii really is faster than i to solve, then it could be used to find the factors of a and b, which could in turn be used to factor n. Thus one could continue downward, if necessary, to factor large numbers by factoring smaller numbers first.
When I have a better grasp of what's going on, perhaps I can approach that recursion issue and see if it leads to a contradiction via infinite descent.
