FORTH GO

Every so often I like to waste a lot of time trying to solve some practically impossible math problem, like finding a simple proof to Fermat’s Last Theorem or proving Goldbach’s Conjecture. These days I’m trying to find a quick way to factor numbers by using graphs to gain insights. (Unlike the other problems, solving this one would put me in an interesting dilemma about how to publish the solution.)

Trial division is the most basic technique for factoring numbers. You just go through candidate factors, dividing each one into the number to be factored and getting a yes/no for each candidate. My thought was to look at the result of the division (not just yes/no) and use that to decide how far to skip ahead for selecting the next candidate. The first graph shows trial divisions of the number 3341287, which is the product of two primes, 2087 and 1601. The candidate factors start at the square root of n and increase along the horizontal axis. The remainders are on the vertical axis.

You can definitely see patterns in the remainders, and it turns out the points lie on “concentric” quadratic curves. The equations for the curves are all of the form: x^2 - m*x + n, for some integer m. We can factor the quadratic into (x-a)(x-b) where n=ab and m=a+b, but that doesn’t help since n=ab is what we’re trying to solve in the first place. However, since each curve covers multiple points, we can reduce our work by iterating over m and solving each quadratic instead of iterating over each x. Unfortunately successive curves cover fewer and fewer factors, and soon it doesn’t help at all.

We might also try to solve the general quadratic. Using the quadratic formula we end up with something of the format k^2-n under the radical (where 2k=m), which means all we have to do is find a k that makes the square root an integer, or in other words an integer solution to k^2 - n = p^2, or k^2 - p^2 = n, or (k-p)(k+p) = n, but then we’re back where we started trying to factor n.

The second graph is the same as the first, but with a wider domain of x. Other interesting quadratics start to appear. In all graphs the red line represents y=x.

The technique of using the quadratics to skip candidates is basically the same as Fermat’s factorization method, except with a graphically inspired derivation. Fermat started where I ended, noticing that any odd number could be written as (k-p)(k+p) and then trying to find solutions by starting k at the square root of n and checking if each k^2 - n is a perfect square.

The last graph shows the remainders for the x values corresponding to the Fermat trial divisors. I think each “Fermat point” represents a quadratic curve from above, using the point with the maximum remainder (or 0 remainder). The green line is at y=n/x, and I’m not sure why all the non-trivial Fermat remainders are above it.

So iterating through quadratics is really the same as Fermat’s method, and we haven’t gained anything, but what about the patterns in the Fermat remainders themselves? Looks like there are some quadratics there as well and maybe we can use the same idea to reduce the number of Fermat points we examine. I’ve found that the quadratics are generally of the form x^2 - a/b * x + n/b, where b has been a small integer in my tests. I haven’t gone much further — there needs to be a way of iterating through these quadratics with confidence of convering all the candidate factors. Then again, even if only most of the candidates are covered, there’s some chance of finding a factor quicker.

At best, any attempt to use those quadratics will surely also be duplicating optimizations that have already be made to Fermat’s method. For instance, there is a method of re-centering the search by multiplying n by some number to offset the problem of diminishing returns once you get far from the “center”, and that sounds a lot like using the quadratics that have another center point.

This entry was posted on Wednesday, July 20th, 2005 at 9:43 pm and is filed under Math. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.