I found a way to calculate Quadratic min mod $N$, but why does it work?

Question

I am trying to factor $N$ using Dixon's factorization method, so I am looking at the equation:

$$a^2\equiv b(\mod{N})$$

If I am able to find $b$ that is a perfect square, I will be able to factor $N$.

While looking at the values of the following $f(x)$, I noticed something very interesting:

$$f(x)\equiv(\lceil\sqrt{N}\rceil+x)^2(\mod{N})$$

The values of $f(x)$ grow as $x$ grows, but then they fall again and start over, like waves.

Since there is a bigger chance of finding B-smooth values when $f(x)$ is small, it is beneficial to only look at the start of the waves. I noticed that most of the time $f(x)<\sqrt{N}$ in those locations, and by experiment I found a formula to get those values.

$$f_{min}(x)=\lceil\frac{\lceil\sqrt{(a-b+1)^2+4(xN-a)}\rceil+(a-b+1)}{2}\rceil+\lceil\sqrt{N}\rceil$$

• $a = f(0)$
• $b = f(1)$

Edit: tnx to Tob Ernack that notice that $f_{min}(x)$ can be reduced to

$$f_{min}(x)=\lceil\sqrt{Nx}\rceil$$

Note that $\mod{N}$ been removed and it still works

$f(f_{min}(x))$ will be either the start or the end location of the wave (if it is the end, then the next value is the start)

So my question is Why does the formula work?

Edit:

Here is another interesting observation:

$f(a) < f(b)$ iff $\lceil\sqrt{Na}\rceil^2-Na<\lceil\sqrt{Nb}\rceil^2-Nb$

Here are example values:

• $N=296629285609=570043\cdot 520363$

• $\lceil\sqrt{N}\rceil=544637$

• $f(f_{min}(0)) = 176160$

• $f(f_{min}(1)+1) = 303071$
• $f(f_{min}(2)+1) = 612094$
• $f(f_{min}(3)+1) = 704640$
• $f(f_{min}(4)+1) = 15980$

Here is the java code I use to evaluate this:

   private BigInteger nextJump(BigInteger a, BigInteger b, BigInteger index, BigInteger root) {
        BigInteger abDif = a.subtract(b).add(ONE);
        BigInteger difPower = abDif.pow(2);
        return sqrCeil(
                difPower
                        .add(V_4.multiply(N.multiply(index).subtract(a)))
        )
                .add(abDif)
                .divide(TWO).add(root);
    }

    BigInteger lastY = TWO;

    private BigInteger sqrCeil(BigInteger value) {
        BigInteger y = lastY;
        BigInteger result = value.divide(y);
        while (true) {
            BigInteger subtract = y.subtract(result);
            if (subtract.abs().equals(BigInteger.ONE) || subtract.equals(ZERO)) {
                break;
            }
            y = result.add(y).divide(TWO);
            result = value.divide(y);
        }
        lastY = y;
        return y;
    }