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 $?

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.
