My Integer Factorization Study: Inching Toward Realizations


This last tack I’ve developed to look at Ceiling Squares, differences between perfect squares, and their relationships with factoring m=pq where p and q are odd prime numbers is getting exciting, but the excitement and inspiration seems a bit more mundane this time, more rooted in day-to-day thought processes and not those early morning imaginings that popped me out of bed in past months – though possibly just as promising. There is also the possibility of letdown, a possibility that I’ve already realized with any number of exciting new findings I’ve made along the way.

Not only does an odd discrete semiprime (the product of two distinct odd primes), let’s call it m, sit on the number line between two consecutive perfect squares (the greater one being c2 where c=ceil(sqrt(m)) in programming notation), but when we write m=c2-r, we deal with that remainder r which is either a perfect square itself – in which case factoring m is easy – or is between its own pair of consecutive perfect squares. And there is the insight that has led me to do some thought and development.

What I have started to see, shining in front of me faintly, is a possibility to deal algorithmically with some of the jumpiness that I have observed and that I believe makes factorization so difficult: remainders seem to jump around in a random-looking fashion, just as the discrete semiprimes themselves and their “ascents” (the differences between (p+q)/2 and c) show random characteristics, or at least the same jumpiness. Now, looking at the differences between two squares immediately or close around the value of m, there may be a way – and I hope I am on the way to finding it – to tease out the process of finding an ascent given a Ceiling Square and its remainder.

Working out this, and even the promise of this, is computationally intensive. And I’m having a ball with it so far.

I’m including, for information’s sake, today’s scratch pad as I’ve worked a simple, small example. This is computation intensive, and, as you will easily be able to tell, not all the dots, either of finding an algorithmic method or ofdetermining no such method can be teased out, have yet come to me.

I will continue working. And I shall keep you informed.

M = 1501 = 39^2 - 20, remainder between 4^2 and 5^2,
  giving Ceiling Root C0=39 and putting M between
  A0 = 1496 = 39^2 - 5^2 and
  B0 = 1505 = 39^2 - 4^2.
  M = A0 + 5 = B0 - 4.
  B0 - A0 = 9.
  Now calculate 2 or 3 "higher remainders" as follows: 
  (C0+1)^2-M = 1600-1501 = 99, between 9^2 and 10^2.
  A1 = 1500 = 40^2 - 10^2.
  B1 = 1519 = 40^2 - 9^2.
  M = A1 + 1 = B1 - 18.
  B1 - A1 = 19.
  (C0+2)^2-M = 1681-1501 = 181, between 13^2 and 14^2.
  If we choose these two perfect squares, A2 = 1485 = 41^2 - 14^2.
  However, we can choose instead A2 = 1456 for uniformity with A0 and A1.
  A2 = 1456 = 41^2 - 15^2.
  B2 = 1485 = 41^2 - 14^2.
  (Currently doubting how much the B values matter aside from B-A span.)
  M = A2 + 45 = B2 + 16.
  B2 - A2 = 29. 
  (C0+3)^2-M = 1764-1501 = 263, between 16^2 and 17^2.
  But if we follow the linearly-increasing pattern already established,
  A3 = 1364 = 42^2 - 20^2.
  B3 = 1403 = 42^2 - 21^2.
  M = A3 + 137 = B3 + 98.
  B3 - A3 = 39.
  Verified that the differences between A's and M constitute an integer
  sequence corresponding to the values of quadratic polynomial:
  F(X) = 24X^2-28X+5, where X is the integer added to C0.

  Knowing the factorization of M (because we are CHEATERS!!), we know
  that C0+10 is where the remainder is exactly a perfect square.
  B10 - A10 = 109.

Leave a Reply Cancel reply