My name is J. Calvin Smith. I graduated in 1979 with a Bachelor of Arts in Mathematics from Georgia College in Milledgeville, Georgia. My Federal career (1979-2012) in the US Department of Defense led me to learn, explore, and take courses in cryptologic mathematics and number theory for cryptology, which in turn led me to the problem – which I assume is still difficult – of factoring very large numbers. I came up with a series of quadratic polynomials associated with any number one is trying to factor – an example of the technique follows – and I want to find out if this is a technique with promise, one that would help make factorization be algorithmic and fast, reducing the order of magnitude of the problem.
It is most easily described by way of example. Let p = 1009 and q = 2003.
n = pq = 2021027.
In this situation, we can effortlessly factorize n: we know what p and q are. What I want to do here is take what we know and use it as a means toward a means: a way to find a way, that way being a method of factoring numbers of arbitrary size straightforwardly.
The largest integer less than the square root of n is 1421. Let us set a
new variable m to 1421.
1009 = m – 412.
2003 = m + 582.
n = m^2 + 170*m – 239784.
The determinant in the quadratic formula for this polynomial would be B^2 – 4AC = 28900 + 959136 = 988036, the square of 994. Thus the quadratic formula will give us integer roots. This follows obviously from how we constructed the quadratic: as the product of two known factors.
But since m^2 = 2019241, we also have as a polynomial for n:
n = m^2 + 1786, which cannot be factored using the quadratic formula.
But 1786 = m + 365 = 2m – 1056 = 3m – 2477 and so on. Adding each of these expressions to m^2 produces a series of quadratic polynomials, almost all of which cannot be factored into integer roots.
Let us now look at m^2 + 1786, with or without the next few polynomials in a series thus constructed, and see if we can determine/calculate ahead of time that we would be hitting the jackpot, so to speak, at the polynomial with the 170*m term? (i.e., the 171st quadratic in the series)
B C B^2-4*C
0 1786 -7144 no real square root
1 365 -1459 no real square root
2 -1056 4228 = 65^2 + 3 = 66^2 – 128.
3 -2477 9917 = 99^2 + 116 = 100^2 – 83.
In general here, Determinant is (B + 2842)^2 -8084108. (This is B^2 + 5684B – 7144, after completing the square.) What I have not yet figured out, but I suspect might be easy, is for which values of B the determinant becomes a perfect square, thus causing the quadratic formula to produce integer roots and lead us to the answer we want – the factorization. Further, will this approach scale nicely? I am hoping the discovery of the perfect-square values of the determinant’s quadratic, regardless of n = pq chosen (and in that case p and q still unknown), can be done algorithmically and easily.