Integer Factorization: Some Newly Observed Relationships

Points in a scatter plot of nontrivial vs. trivial t in m=s2-t2

If odd integer m is a discrete semiprime, then the search for the least positive integer whose square when added to m produces another perfect square is the problem addressed by the admittedly slow process of Fermat’s factorization method.

Despite its lack of advantages over trial division as a factorization method, Fermat’s approach fascinates me and has been central to the past year’s work I have done on finding new and faster factorization methods based on the patterns I have observed.

One such pattern has come to me recently that is striking in its beauty, if not utility: An odd discrete semiprime will have two possible factorizations, which correspond to two distinct expressions of it as the difference between perfect squares. The trivial factorization of discrete semiprime m as being 1 times m corresponds to m’s expression as s2-t2 where s=t+1. All odd integers have such an expression as the difference between consecutive perfect squares: When you look at x2 for x=0,1,2,… you will see each differs from its predecessor by 1, 3, 5, …, which is, by the way, what one would expect from a quadratic polynomial’s values.

But as I was working on compiling a large table of the discrete semiprimes less than or equal to 20000, in numerical order (it’s a bigger bite than I can chew, I am finding), with their non-trivial and trivial expressions as differences of squares, I came upon the above graph, which is the logarithmic-y-axis representation of the non-trivial solution’s value of t plotted versus the trivial solution’s value of t. But beyond that, I found the following relationship, based on the value of the smaller of the two primes in the factorization of m:

Let m=pq with p>q.

Let t1 squared be the nontrivial perfect square added to m to produce a perfect square equal to s1 squared. The difference s1-t1 will be equal to q.

Let t2 squared be the trivial perfect square added to m to produce the perfect square of s2=t2+1. t2 as it turns out always equals (m-1)/2.

I assert (without proof, though such might not be difficult) that:


Again, I don’t know that it gives much new information – I suspect it doesn’t – but it’s a compact formula behind the properties of a pretty graph.

Leave a ReplyCancel reply