Integer Factorization: The Continuing Refinement of Square One


At the risk of being repetitive, the “beehive plots” and other recent work bring me back to the basic problem to be solved in order to advance the ability to factor large discrete semiprimes:

Let m be an odd positive composite integer, and let c be the integer ceiling of the square root of m.

m = c2-r for some nonnegative integer r. If r is a perfect square, to include the possibility r=0, m easily factors according to the rule c2-d2=(c+d)(c-d) for any integer d.

Now, instead of simply choosing for the integer ceiling of the square root of m, we choose either c=ceil(sqrt(m)) or that value plus one, so that the resulting c is even or odd as (m+1)/2 is even or odd. This choice arises naturally because any expression m=s2-t2 with integers s and t must have s even or odd, and t odd or even, when (m+1)/2 is even or odd, respectively.

The current and not very rapid factorization routine I use is to take the value of c thus obtained and to increase its value by two until the difference c2-m itself becomes a perfect square.

The task at hand for me in this study is to find out how to tell, initially and formulaically, based on the values of c, r, and m, the least positive value to add to c (it will be an even number) to produce a perfect square value of r.

Again, this is repetitive, but I’ve discovered that the repetition also refines the ideas, and I feel the need to post the fruits of that refinement, however slight, when they occur. The beehive plots are showing me something of the nature of the pattern that is present in all these cases.

Leave a Reply Cancel reply