My Integer Factorization Study: An Important Quadratic Polynomial

Advertisements

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 = c2-r1 for some positive integer r1. (The value of r1 will not be zero because m is a discrete semiprime: the product of two distinct odd prime numbers.)

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

If r1 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 r2.

Consider the quadratic polynomial of the form x2+ax+b that evaluates to r1 at x=0, and to r2 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 x2+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 Reply Cancel reply