Efficicient algorithm to check if $az+1=(xz+1)(yz+1)$ Given two positive integers $a$ and $z$ with $z$ prime, consider the problem of determining whether the integer $az+1$ can be factored as $az+1=(xz+1)(yz+1)$, where $x, y$ are positive integers and $xz+1$ is prime. This problem can be solved by checking if $yz+1 \ | \ az+1$ for some integer $y$, $yz+1 \le \sqrt{az+1}$.
Trial division however is too slow when $a/z$ is large. Is there an efficient algorithm for solving this problem or a particular case. (Note that we are not interested in finding factors of $az+1$, only to determine if it can be factored this way).
A related but different question is here Prove that the diophantine equation $(xz+1)(yz+1)=az^{3} +1$ has no solutions in positive integers $x, y, z$ with $z>a^{2} +2a$.
 A: I'll give a heuristic argument for the following claim: any algorithm that solves this problem cannot be faster than factoring $az+1$.
From there it is well known what the asymptotic complexity is, plus what algorithms are actually faster when implemented in a programming language and so on.
Consider the first few cases with small $z$:
$z=2$
The algorithm returns true if and only if $az+1$ is composite. I proved this a couple days ago here.
$z=3$
Let the factorization of $az+1$ be the following:
$$az+1=\prod_i p_i^{a_i}\prod_i q_i^{b_i}$$
Where $p_i\equiv 1 \mod 3$ and $q_i\equiv 2 \mod 3$. We have that $\sum b_i \equiv 0 \mod 2$ since $az+1\equiv 1 \mod 3$. The factorization is impossible again if $az+1$ is prime but also in the case where $\sum b_i = 2$ and there are no $a_i$ i.e. when it is the product of two primes $\equiv 2 \mod 3$. It's easy to see that all other cases allow you to group the primes into two factors that are $\equiv 1 \mod 3$, all of which get you a valid factorization.
The case $z=4$ is very similar to the previous one. But when $\varphi(z)$ starts getting larger it gets more complicated. The case $z=5$ is as follows:
Let
$$az+1=\prod_i p_i^{a_i}\prod_i q_i^{b_i}\prod_i r_i^{c_i}\prod_i s_i^{d_i}$$
Where the classes of prime numbers are those congruent to $1,2,3,4$ mod 5 respectively. Let also $A=\sum_i a_i$ and the same for the other three residue classes. Then $az+1$ is of the form $(5x+1)(5y+1)$ when all of the following are false:

*

*It is prime;


*$A=C=D=0$ and $B=4$;


*$A=D=0$ and $B=C=1$;


*$A=C=0$ and $B=2$ and $D=1$;
As you can see, these are increasingly complicated statements about the prime factorizations of $az+1$. So I don't think your question can be answered faster than actually factoring it.
A: As GerryMyerson writes, "$az+1=(xz+1)(yz+1)=xyz^2+xz+yz+1,\ a=xyz+x+y,$ so a restatement of the question is whether, given $a,z,$ there is an efficient way to decide whether there exist $x,y$ such that $a=xyz+x+y.$"
Then, a restatement of this is whether, given $a,z$ and $a=qz+r,$ there exist $x,y$ such that $xy=q$ and $x+y=r.$ But this corresponds to solving $x(r-x)=q$ which has solutions
$$
2x = r \pm \sqrt{r^2-4q}.
$$
Thus, we need to decide whether $r^2-4q$ is a square number, say $s^2.$
Now, $r^2-4q=s^2$ is equivalent to $(r+s)(r-s)=4q$ which means that we need to find all factorizations of $4q.$
A: Taking in account GerryMyerson comment, easily to get the system in the form of
\begin{cases}
az+1=(xz+1)(yz+1) = 1+ z(x+y) + z^2xy\\
a=xyz+x+y=(xz+1)y+x=(yz+1)x+y\\
x\le y\\
a,x,y,z\in\mathbb N,\tag1
\end{cases}
where $\;x,y\;$ are unknowns and $\;a,z\;$ are parameters.
Denote $\;s=x+y,\;$ then
$$4(az+1) = 4+4zs+z^2s^2-z^2s^2+4z^2x(s-x) =(zs+2)^2-z^2(s-2x)^2,$$
$$4(a-s) = z(s^2-(s-2x)^2),$$
$$a = zx(s-x)+s,$$
\begin{cases}
y=s-x\\[4pt]
s\in\left\{z\left\lfloor\dfrac{2\sqrt{1+az}-2}{z^2}\right\rfloor+(k-1)z+(a \mod z),\; k\in\mathbb N\right\}\cap\{1,2\dots a\}\\[4pt]
2x=s-\sqrt{s^2-\dfrac{4a-4s}z}.\tag2
\end{cases}
Therefore, the integer variable $\;s\;$ should change the values with the step $\;z.\;$
If $\;z\;$ is too small, then can be used analysis on the unused simple residue classes.
For example, the parity anlysis of $(1)$ gives the next additional constraints.

*

*If $\;\mathbf{(2\!\not|\;z)\wedge(2\!\not|\;a)},\;$ then $\;(2\,|\;az+1),\;(2\!\not|\;x)\vee(2\!\not|\;y).\;$

*If $\;\mathbf{(2\!\not|\;z)\wedge(2\,|\;a)},\;$ then $\;(2\!\not|\;az+1),\;(2\,|\;x)\wedge(2\,|\;y).\;$

*If $\;\mathbf{(2\,|\;z)\wedge(2\!\not|\;a)},\;$ then $\;(2\!\not|\;az+1),\;(2\,|\;x+y).\;$

*If $\;\mathbf{(2\,|\;z)\wedge(2\,|\;a)},\;$ then $\;(2\!\not|\;az+1),\;(2\!\,\not|\;x+y).\;$
Similar schemes allow to improve the computational complexity of the algorithm.
However, there are not a good simple algorithm for big numbers.
