Finding all proper divisors of $a_3z^3 +a_2z^2 +a_1z+1$ of the form $xz+1$ Let $n=a_3z^3+a_2z^2+a_1z+1$ where $a_1<z, \  a_2<z, \ 1 \le a_3<z, z>1$ are non negative integers. To obtain proper divisors of $n$ of the form $xz+1$, one may perform trial divisions $xz+1 \ | \ n$, for all $xz+1 \le \sqrt n$. Trial division however is inefficient as $z$ becomes large. The method below is much more efficient.
Since $xz+1 \ | \ n$ , we may write $(xz+1)(yz+1)=n$. Assume $y \le x$. We consider two cases;
**Case 1: ** $1 \le x <z$ and $1 \le y<z$
$xyz+x+y=a_3z^2+a_2z+a_1$. Since every positive integer has a unique base $z$ representation we have;
\begin{equation}
x+y=C\cdot z+a_1 , C=0  \ \text{or} \ 1 \  
\end{equation}
\begin{equation}
 xy+C = a_3z+a_2
\end{equation}
Solving the two equations for the cases $C=0$ and $C=1$, $x$ and $y$ can be determined.
**Case 2: ** $z\le x<z^2$ and $1 \le y<z$
Let $x=x_1z+x_0$ and $y = y_0$, $1\le x_1<z, \  0 \le x_0<z$,   $ 1 \le y_0 <z$.
So \begin{equation} 
x_1y_0z^2+(x_0y_0+x_1)z+x_0+y_0=a_3z^2+a_2z+a_1
\end{equation}
Comparing coefficients of powers of $z$;
\begin{equation} 
x_0+y_0=C_1 \cdot z+a_1,  \ C_1 = 0 \  \text{or}  \ 1
\end{equation}
\begin{equation}
x_0y_0+x_1+C_1=C_2 \cdot z+a_2
\end{equation}
\begin{equation}
 x_1y_0+C_2=a_3
\end{equation}
From the last equation, either $y_0 \le \sqrt a_3$ or $x_1 \le \sqrt a_3$. So we do  trial divisions $yz+1 \ | \ n$ for all $y = y_0 \le \sqrt a_3$. Also for each value of $x_1 \le \sqrt a_3 $, we solve the three equations simultaneously to find $x_0, y_0$ and $C_2$ when $C_1=0$ and $C_1 = 1$.
Cases 1 and 2 exhaust all the possible cases.
In this example, we had $n < z^4$. How can this method be modified to efficiently find all proper divisors of the form $xz+1$ of an arbitrary positive integer $n$, $n \equiv  \ 1 ($    mod $ z) $ or at least when $n<z^5 $?
 A: Such an extension is highly unlikely to exist. Already in the simple case of $z=2$, it's equivalent to just factoring a given odd integer $n$, which is a famous hard problem.
A: An extension to the case when $n<z^5$ with some restrictions on $x$ and $y$:
Let $n=a_4z^4+a_3z^3+a_2z^2+a_1z+1$, $a_i < z $, $a_4>0, z>1$. We are looking for positive integes $x$ and $y$ such that $(xz+1)(yz+1)=n$. We add a restriction on $x$ and $y$;  If $x=x_k \cdot z^k + \cdots + x_0$ and $y=y_t \cdot z^t + \cdots + y_0$ are the base $z$ represenations of $x$ and $y$, then $x_i \le x_k$ for all $i<k$ and $y_i \le y_t$ for all $i<t$.
Case 1: $x=x_1\cdot z+x_0$ and $y=y_0$
We get \begin{equation}
x_1y_0z^3+(x_0y_0+x_1)z^2+(x_0+y_0)z+1=a_4z^4+a_3z^3+a_2z^2+a_1z+1
\end{equation}
Comparing coefficients of powers of $z$;
\begin{equation}
x_0+y_0=C_1\cdot z+a_1 , C_1=0 \ \text{or} \ 1
\end{equation}
\begin{equation}
x_0y_0+x_1+C_1=C_2\cdot z+a_2
\end{equation}
\begin{equation}
x_1y_0+C_2=a_4\cdot z+a_3
\end{equation}
From the last equation, $x_1y_0 < (a_4+1) \cdot z$ and since it's assumed that $x_0 \le x_1$, we have $x_0y_0+x_1+C_1<(a_4+2)\cdot z$ , therefore $C_2 \le a_4+1$. By solving the three equations for $C_2=0, 1, \cdots , a_4+1$, all solutions with $x_0 \le x_1$ are found.
Case 2: $x=x_1\cdot z+x_0$ and $y=y_1\cdot z+y_0$
We get $x_1y_1z^4 + (x_0y_1 + x_1y_0)z^3 + (x_0y_0+x_1+y_1)z^2+(x_0+y_0)z+1=a_4z^4+a_3z^3+a_2z^2+a_1z+1$
Comparing coefficients of powers of $z$;
\begin{equation}
x_0+y_0=C_1\cdot z +a_1 \ \ C_1 = 0 \ \text{or} \ 1
\end{equation}
\begin{equation}
x_0y_0+x_1+y_1+C_1=C_2\cdot z +a_2
\end{equation}
\begin{equation}
x_0y_1+x_1y_0+C_2=C_3\cdot z +a_3
\end{equation}
\begin{equation}
x_1y_1+C_3=a_4
\end{equation}
From the last equation, we have $x_1y_1 \le a_4 < z$. Assuming $x_0 \le x_1$ and $y_0 \le y_1$ we have,
\begin{equation}
 x_0y_0+x_1+y_1+C_1 < 3z
\end{equation}
Therefore $C_2 \le 2$. And from the second last equation we have,
\begin{equation}
x_0y_1+x_1y_0+C_2 \le 2z
\end{equation}
Therefore $C_3 \le 2$.
Solving the four equations for all the 18 combinations of $C_1 \le 1$, $C_2 \le 2$, $C_3 \le 2$, all solutions $x_1,x_0,y_1,y_0$ are found.
The last case when $x$ and $y$ have $3$ base $z$ digits and $1$ base $z$ digits respectively can be tackled in the same way.
