This is a continuation of progress reports on a number study of the integer factorization problem I have been conducting this Spring.
Last night, in working through my calculations to see which quantities involved I could express in terms of other quantities, I came upon one that surprised me, and I wonder if the improbable has occurred and I have discovered something that will speed up integer factorization greatly.
Here is the concept: When m is the product of two distinct odd primes p and q, one can choose p to be less than q. Determine a variable s to be the integer ceiling of the square root of m. Let r be the difference between the square of that value and m, so that m = s2 – r.
Consider the primes p and q. Concerning the distinct odd primes p and q, with p * q = m, and p < q, p will be less than s, and q will be greater than s. Let c1 and c2 be the so far unknown difference between s and p, and between q and s, respectively: p = s – c1 and q = s + c2.
I was looking for ways to express a relationship between the two differences, and thus between p and q, that might become apparent without an iteration of equal or greater calculation time than trial division – that might, in fact, depend only on m and the related numbers s and r. I HAVE NOT FULLY FOUND THAT RELATIONSHIP YET (important! and potentially disappointing), but I have discovered something that may be a step toward it: c1 and, through calculation, c2 relate to r and s by divisibility, in that s – c1 divides (c1 * s) – r. Testing shows that starting with c1 at 0 and increasing by 1 will eventually lead to the value of c1 producing the desired divisibility, and thus to the discovery of p by subtracting it from s. The number of iterations is, again, still on the order of what is required for trial division, even with my earlier technique searching a family of polynomials for one with a perfect-square discriminant, but the calculation is simpler in terms of operations and comparisons, and I hope that the simplicity of those operations will lead to further revelations, either for myself or for someone with greater mathematical experience – as well as someone who actually has an arbitrary-precision mathematical package, such as MAGMA, installed where they can explore this with much larger values of m than the 10 to 12 digit values I have been using to test and study it.
Leave a Reply Cancel reply