Well, I’m right back in the mess!

Today’s epiphany of an interesting avenue to take took place, not in early hours of wakefulness, but as I was on my way to Wendy’s (the fast food place, not my wife’s place, which is currently a cabin by the beach – I’m envious).

Let m be an odd discrete semiprime. Let c be the Ceiling Root of m; i.e., the integer ceiling of the square root of m, so that m = c^{2}-r_{1} for some positive integer r_{1}. (The value of r_{1} will not be zero because m is a discrete semiprime: the product of two distinct odd prime numbers.)

If r_{1} is a perfect square, one can quickly factor m as [c+sqrt(r_{1})]*[c-sqrt(r_{1})]. This is a quick enough discovery that one’s algorithm should test for r_{1} being a perfect square first.

If r_{1} is not a perfect square, compute a second remainder (don’t panic! my idea only has us doing this again just this once; we only have to compute two remainders) by subtracting m from (c+1)^{2}. Call this remainder r_{2}.

Consider the quadratic polynomial of the form x^{2}+ax+b that evaluates to r_{1} at x=0, and to r_{2} at x=1. a and b will be positive integer coefficients. More importantly, this will be the quadratic polynomial for which we want to find the least positive integer value of x that makes the polynomial yield a perfect square value. This will tell us the value of x we need to add to c so that m-(c+x)^{2} will be the perfect square we want, giving us factorization.

Right off hand, I do not know how easy it is to determine a formula for finding the least value of x that makes x^{2}+ax+b a perfect square given positive integers a and b; I will of course investigate this for potential in speeding up factorization. It is the new tree up which I am barking, to employ my old reliable metaphor.

## Leave a ReplyCancel reply