Polynomial Associates

Given a polynomial P in some ring R, I define an p-associate polynomial Q as one which has the same value when evaluated at p as P does.

The set of all m-associates of a polynomial P I'll refer to as M(P).

It's relatively straightforward to construct an associate. Given the polynomial P and m, all you have to do is add m to P, and subtract it back out to maintain the value.

That is to say, you may substitute m for any of the variables in the polynomial as many times as you need to, provided you add m back in to compensate.

For example:

\[P(x) = x^2 + 3x\]

I seek to find an m-associate where \(m = 10\).

\[P(x) + 10 - 10 = x^2 + 3x + 10 - 10\] \[x = 10 \rightarrow P(x) = x^2 + 4x - 10\]

Hence the polynomial \(Q(x) = x^2 + 4x - 10\) has the same value at \(x=10\) as P.

That is to say, \(P(10) = 130 = Q(10) = 140 - 10\)

The procedure for fetching an associate gives you an awful lot of choice. You have many choices on which power of x to substitute m for, and for each x, you can either replace it with m, or remove it and add a constant in.

This means that you can form a graph where each polynomial P is connected to all of its m-associates.

The resulting graph is absurdly complicated.

Given some integer n, there is always a corresponding polynomial \(P(x)\) that evaluates to n at \(x=10\), that is, the polynomial given by the digits of n evaluated at \(x=10\).

That polynomial often does not factor. However, if you can factor it into two integer-valued polynomials then evaluating one of them will give you a factor of n. This is not useful for integer factorization, however, since it's quite a bit difficult to factor the polynomials, and there's a huge chance that even if you do succeed, you'll just get one polynomial that evaluates to 1, and the other evaluates to n.

Just a helper function so we can test things in the REPL.

(defun polynomial-eval (P x)
        (let ((result 0))
                (loop for i from 0 below (length P) do
                        (incf result (* (aref P i) (expt x i))))
                result))

This one is helpful for debugging, too, it spits out random associates:

(defun polynomial-random-associate-array (n &optional (B 10))
        ;;Given n as a polynomial in base b (list of coefficients)
        ;;Find an associate of it, at random:
        (let* ((L (length n)) (R (random L)) (direction (random 2))) ;; 0 means right, 1 means left.
                ;;Prevent noops:
                (when (and (= R (- L 1)) (= direction 0))
                        (setf direction 1))
                (when (and (= R 0) (= direction 1))
                        (setf direction 0))

                (when (and (= direction 0)  (< R (- L 1)))
                        (let ((RD 1))
                                (decf (aref n R) (* RD B)) ;;Decrement by B*RD
                                (incf (aref n (+ R 1)) RD));;Increment next digit by 1*RD
                        (return-from polynomial-random-associate-array n))
                (when (and (= direction 1) (> R 0))
                        (let ((RD 1))
                                (decf (aref n R) RD) ;;Decrement this digit by 1*RD
                                (incf (aref n (- R 1)) (* B RD)));;Increment by B*RD
                        (return-from polynomial-random-associate-array n)))
        n)

Now what you want to do is just iterate that function repeatedly until one of the cofficients shares a nontrivial divisor with n.

(defun polynomial-next-associate-array (P base)
        ;; Just quickly find a nearby associate, always going the same way:
        ;;Add B*RD to the 0th coefficient.
        (let ((RD 1));;Random digit.
                (incf (aref P 0) (* base RD))
                (decf (aref P 1) RD)
                P))

(defun factor-via-polynomial-tree-walking (n &optional (base 10))
        (loop for P = (polynomial-random-associate-array
                                          (convert-base-b n base))
                then (polynomial-random-associate-array P base) do
;;              (format t ";;P = ~a~%" P)
                (loop for coefficient-i across P do
                        (let ((d (gcd coefficient-i n)))
                                (when (and (> (abs d) 1)
                                                  (not (= n d)))
                                        (return-from factor-via-polynomial-tree-walking d))))))

But this isn't any faster than just randomly generating integers and doing gcd until you hit a divisor by chance.

It would appear that what's really happening under the hood here is that I'm looking at arithmetic progressions \(c + nb^k\) for a fixed \(k\) and base \(b\), where \(c\) is the k'th digit of n.

The arithmetic progression taken mod \(d\) (for the unknown d) must necessarily cycle, and the corresponding cycle must form a subgroup of \(Z_d\). But if \(d\) is prime, then you can only fall into the trivial subgroup, or the whole group, and thus the arithmetic progression mod \(d\) must always (unless you get the trivial subgroup instead) cycle through all possible values.

Eventually, you must hit a divisor of n, but there is no way to guarantee you hit it quickly. The complexity of this algorithm is therefore \(O(d)\), where d is the smallest nontrivial factor of \(n\)

So, useless factoring algorithm but nonetheless a fun mental exercise and something to play around with.