JCSBimp's Hexagonal Orthogonal

Let m = p * q denote the positive integer that is the product of prime numbers p and q.

Determine s as the integer ceiling of the square root of m.

If s is a perfect square, then p = q = s.

Otherwise, perform the following steps:

Determine r = s^2 – m.

Consider the infinite set of polynomials of the form

fsub n = x^2 + n * x – (n * s + r)

which evaluate to the value of m when x = s.

The Quadratic Formula gives roots of each of these polynomials corresponding to their Discriminants, all of which will be of the form:

D = n^2 + 4sn + 4*r.

An integer value of n which produces a value of D that is a perfect square will lead to a polynomial with integer roots that corressponds to a factorization of m.

This process is often no faster than trial division to find p and q dividing m.

Let us consider non-integer values of n, and their corresponding fsub n = m quadratic polynomials, which produce perfect square values of the Discriminant. These values of n will still be algebraic integers; they will, in fact, be roots of quadratic polynomials with integer coefficients.

Choosing such an algebraic integer will produce algebraic integer factorizations of m. These may lead to a useful integer factorization of m.