Integer Factorization: The (Currently) Incalculable Property of the Remainder-Remainder Grid


The Usual Definitions, Restated for Current Explorations: Let m be an arbitrary odd positive integer whose factorization into powers of primes is not something we necessarily know. Determine whether (m+1)/2 is odd or even, or, equivalently, whether m is congruent modulo 4 to 1 or 3, respectively. Consider the possible expressions of m as differences of perfect squares: m=s2-t2. I have shown elsewhere that s must be even or odd the same as (m+1)/2 in any such expression. Additionally, the number of ways to express m as the difference of two perfect squares equals the number of distinct ways to express m as the product of two positive integers, which is the number of divisors of m over 2. For each possible expression m=ab, with a, b positive integers and a less than or equal to b, s appears as (a+b)/2 and t appears as (b-a)/2: m = [(a+b)/2]2-[(b-a)/2]2. Now let us determine the smallest perfect square c2 greater than m that is even or odd the same as all such s for a given m. c will be either ceil(sqrt(m)) or that quantity plus 1, and I have named this the Ceiling Root of m, and c2 the Ceiling Square of m.

As I hastily and probably inadequately explained in a blog post last night, I have been assembling what I call Remainder-Remainder Grids for, so far, a couple of selected values of m: one integer, 101010101, which I selected for its prettiness, and a “nearby” squarefree semiprime: the product of two prime numbers. Both of these have an Ascent (another term I invented) of 50, meaning that 50 is the smallest positive integer that one must add to m’s Ceiling Root and then square it to find a value of s squared that yields a perfect-square value of t squared.

The Remainder-Remainder grid is made by taking several values of a Remainder Series that emerges from Ceiling-Square-related calculations on m as follows:

Construct a series of remainders produced by subtracting m from the Ceiling Square c2 and then the series of integers (c+2)2, (c+4)2, and so on. This series of remainders will increase monotonically, quadratically in fact, and will eventually produce at least one perfect square. These are in fact the values of the polynomial x^2+2cx+r evaluated at x=0, 1, 2, and so on.

I have taken the series of remainders and used the first few of them for the row numbers of a grid. The columns of the grid I have chosen to be the Ceiling Roots of the remainders themelves. I then calculate the difference between the squares of the Ceiling Roots along the top and the Remainder Series down the side. I fill in a Remainder-Remainder Grid in this way. The main diagonal of the grid has the numbers that are smallest in absolute value, and if one were to take the Remainder Series to the first perfect square that occurs, the cell on that main diagonal would be 0.

The columns of these charts have numbers that follow a quadratic progression. However, because of the nature of Ceiling Roots and Remainders, the same cannot be said for the rows’ numerical progressions. Furthermore, I have not yet figured out formulaically a method to think about their progression predictively. I suspect when and if I do so, it will give great insight into the process of integer factorization itself. I hope that happens, and will work toward it … while, at the same time, NOT holding my breath.

And now, a Star Trek break: While I’ve been doing this lately, I’ve also been streaming episodes of Star Trek: Discovery, which is rapidly becoming one of my very favorite additions to the Star Trek franchise. And as I’ve played in the past couple of days with the underlying sense but also the utter unpredictability and un-understandability (so far) of the Remainder-Remainder grids, one metaphor that jumps to my mind is, of course, the Mycelial Network. It’s actually gratifying to be dealing with an arrangement of numbers that seems to me as mysterious and as full of possibility as that fictional network of spores and organisms seemed to that story’s characters, at least for the first couple of seasons (so far as I know – I’m not far into Season 2), to be.

Leave a ReplyCancel reply