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.
Leave a ReplyCancel reply