Integer Factorization: Behavior with Fixed Remainders


EDITED TO ADD – WARNING! – Do not yet take any of the following formulae or ideas as verified, not just yet. I am having a problem with larger values plugged into the approach. I have to investigate and debug, or at least understand better, what is going on.

EDITED TO ADD, PART TWO: Stand down from Red Alert! The problem I was having had to do with taking numbers for the Ceiling Square and Remainder, when doing larger number experiments, which were outside the range of possibility relative to each other. For reasons I cannot understand yet, but definitely respect, this causes Zone Grid calculation anomalies. In particular, it causes to spit out Characteristic Lines that did not make sense, and did not match what my calculations would predict. But being outside the “legal zone,” so to speak, meant I was looking at nonsensical quantities.

I am lately studying what I believe to be some of the results that relate to modern factorization methods, in particular the quadratic behaviors of squares and remainders that I feel certain helped lead to the Quadratic Sieve and similar approaches which have brought methods to the state of the art.

In particular, I am looking at the family of odd positive integers m=c2-r for fixed r and consecutive values of c odd or even as r is even or odd. When one examines these values, their lines on the zone grid, and their factorizations, one sees behavior that does allow for sieving: when c2-r is a multiple of n, every nth term in the series after that is also divisible by n. Further, the Characteristic Line on the Zone Grid (see here for my construction of this concept) has slope and y-intercept values that change linearly, albeit at different rates, as c increases linearly. These Characteristic Lines will, after all, pass through the single point on the Zone Grid which the construction method chooses for the remainder r.

I have written a handy little Perl script to take values a and b in y=ax-b, and determine when the Characteristic Line with that equation passes through Zone Boundaries at integer values, after I realized that the x value of such points is (n2+b)/(a+1-2n) as n, the Zone Boundary number, ranges from 0 to (a-1)/2. Since a is always odd by this construction, n=(a-1)/2 produces a denominator of 2 which, also according to the construction, corresponds to the point on the Zone Grid that gives the trivial solution m equals 1 times m. In the scatter plots below, for r values of 5, 8, and 12 and 0 < m < 10,000, the topmost and unbroken diagonal line of dots in blue correspond to this trivial case. The Perl script shows these, but also the smaller Zone Boundary numbers for the points in the illustration below. As always, I am searching for patterns, and so far I mainly see the sieving behavior and the periodic patterns of dots as they run parallel in the scatter plots to the blue line of dots.

Again, I am dealing with smaller, easily calculated quantities in order to discover, as I can, patterns that will persist as numbers get (much) larger. This particular avenue of study is encouraging in that it is free of some of the random messiness that recent studies and graphs have left untangled. But as always, it will not take me long to see whether this clearer view is more fruitful, or is just restating the known and obvious.

Leave a ReplyCancel reply