How to choose $n$ such that $N = am - bn^2$ has smooth factors $d_i \le \beta$

Question

Let $N = am - bn^2$ where $a, m, b$ are given and all are positive integers. We need to choose $n$ such that $N$ has smooth factors $d_i$ (where $d_i \le \beta$).

How can we accomplish that?

Right now, I am just brute-forcing it. Is there a better way?

Answer 1

Your problem is equivalent to the sieve step of the quadratic sieve method for factoring large numbers. Here is the relevant section from Wikipedia:

In practice, a process called sieving is typically used. If $f(x)$ is the polynomial $f(x)=x^2-n$ we have \begin{align} f(x)&=x^2-n \\ f(x+kp) &= (x+kp)^2-n \\ &= x^2+2xkp+(kp)^2-n \\ &= f(x)+2xkp+(kp)^2\equiv f(x)\pmod{p} \end{align} Thus solving $f(x) \equiv 0 \pmod{p}$ for $x$ generates a whole sequence of numbers $y$ for which $y=f(x)$, all of which are divisible by $p$. This is finding a square root modulo a prime, for which there exist efficient algorithms, such as the Shanks–Tonelli algorithm. (This is where the quadratic sieve gets its name: $y$ is a quadratic polynomial in $x$, and the sieving process works like the Sieve of Eratosthenes.)

The sieve starts by setting every entry in a large array $A$[] of bytes to zero. For each $p$, solve the quadratic equation mod $p$ to get two roots $\alpha$ and $\beta$, and then add an approximation to $\log(p)$ to every entry for which $y(x) \equiv 0 \pmod{p}$... that is, $A$[$kp+\alpha$] and $A$[$kp+\beta]$. It is also necessary to solve the quadratic equation modulo small powers of $p$ in order to recognise numbers divisible by small powers of a factor-base prime.

At the end of the factor base, any $A$[] containing a value above a threshold of roughly $\log(x^2-n)$ will correspond to a value of $y(x)$ which splits over the factor base. The information about exactly which primes divide $y(x)$ has been lost, but it has only small factors, and there are many good algorithms for factoring a number known to have only small factors, such as trial division by small primes, SQUFOF, Pollard rho, and ECM, which are usually used in some combination.

In your case, $f(x) = am-bx^2$. This is not exactly in the form $f(x)=x^2-n$ used in the article, but the method is the same. Also, it is not explicitly mentioned in the article, but for higher powers of each prime $p\le\beta$ you can use Hensel lifting (e.g. see this question) to solve the quadratic congruence mod $p^k$, and you would need to add a total of $k\log(p)$ to each entry of $A$[] that solves the congruence mod $p^k$.