Integer Factorization: Pushing Forward


[To the regular reader: I do apologize for a bit of repetition of definitions, but I do this mainly for someone just jumping in to my posts for the first time, so that they’ll get up to speed quickly.]

Let m be a discrete (square-free) semiprime, c its Ceiling Root and r the difference c2-m, so that m=c2-r.

c, as defined in previous blog posts, is the least positive integer that is odd or even, as (m+1)/2 is odd or even, such that c2>m.

Let c0, c1, c2 be the integer sequence starting with c and increasing by two, so that cn=c+2n. Construct an integer sequence of remainders rn by subtracting m from each cn2. For my studies, I only need to increase n until it reaches the value for which cn=(m+1)/2, the greater square corresponding to the “trivial” factorization, 1 times m.

This series of remainders rn are the values of the quadratic polynomial x2+2cx+r evaluated at x=2n. Similar to what I’ve established elsewhere, the least non-negative value of n for which n2+2cn+r is a perfect square gives a remainder that allows for factoriztion of m as (cn-sqrt(rn))(cn+sqrt(rn)).

The real trick, of course, is predicting when this will happen, using the values of c and r which we have. The quest continues!

Leave a ReplyCancel reply