Integer Factorization: The Adjusted Ceiling Square, and Newly Deriving an Old Characteristic Polynomial

Advertisements

Consider the problem of factorization of m, an odd discrete semiprime (the product of two distinct odd primes).

m can be expressed as the difference between two perfect squares in two different ways, giving the “Fermat factorization” of m corresponding to its expression 1*m and p*q, with p and q being m’s distinct prime factors.

For m to have an expression as s2-t2 for some values s and t, we know that for the trivial factorization m=1*m, s=(m+1)/2 and t=(m-1)/2. Also, if m=pq, s will equal (p+q)/2 and t will equal (|p-q|)/2.

Also we know that, depending on m’s value modulo 4, and due to the fact that perfect squares can only be congruent to 0 or 1 modulo 4, all expressions of m as s2-t2 will have s even and t odd if m is congruent to 3 modulo 4, and s odd and t even if m is congruent to 1 modulo 4.

The m congruent to 3 modulo 4 condition is equivalent to saying (m+1)/2 is even. Correspondingly, (m+1)/2 is odd whenever m is congruent to 1 modulo 4. The values 0 and 2 modulo 4 do not figure into this discussion since m is odd.

Determine the Adjusted Ceiling Square of m to be the least perfect square greater than m that is odd if (m+1)/2 is odd, and even otherwise, and let its integer square root be the Adjusted Ceiling Root of m. This means the Adjusted Ceiling Root is either the integer ceiling of the square root of m [a number the author has called the Ceiling Root in earlier posts and articles] or that number plus 1.

If m is a discrete semiprime, the Adjusted Ceiling Square c2 will not equal m, and c2-m will be a positive integer remainder r. Sometimes r is itself a perfect square, which leads directly to Fermat factorization of m. For the majority of discrete semiprimes, though, this is not the case.

Consider the series of remainders r0, r1, r2 given by the series of differences:

r0=c2-m;

r1=(c+2)2-m;

r2=(c+4)2-m,

and determine the coefficients of the quadratic polynomial f(x) which satisfies f(0)=r0, f(1)=r1, and f(2)=r2.

(Notice that since one is calculating these three remainders, if any one of them is a perfect square, Fermat factorization becomes possible and this process can end with having made that determination and producing the solution.)

The quadratic coefficient of f(x) is 1, the linear coefficient is 2c, and the constant coefficient is r0: i.e., the original remainder r in the earlier paragraph, the difference between the Adjusted Ceiling Square and m.

f(x)=x2+2cx+r is thus a characteristic polynomial for m=c2-r, the function for which the least non-negative integer value of x for which f(x) is a perfect square will lead to an expression of m as s2-t2 and thus factorization.

But do we know enough about the behavior of the values of quadratic polynomials, with leading coefficient 1 and evaluated at integer arguments, to let us predict when f(x) will be such a value?

The author is looking into this with renewed vigor, and hopes to make further discoveries.

Leave a Reply Cancel reply