A bridge from modular quadratic congruences $x^2 \equiv 1^2 \pmod n$ to generalized Pell equations $X^2 - nY^2 = 1 - n$

I have been analyzing the problem of integer factorization by looking at non-trivial square roots of unity modulo $n$.

Starting directly from the quadratic congruence $x^2 \equiv 1^2 \pmod n$, I derived a specific parameterization that maps the problem onto a generalized Pell equation of the form $X^2 - nY^2 = 1 - n$. I would like to share this derivation and ask about efficient ways to approach this formulation.

1. Algebraic Derivation

Step 1: From Modular Congruence to Integer Difference

We start with the quadratic congruence:

$$x^2 \equiv 1^2 \pmod n$$

By definition of modular congruence, this implies that $x^2 - 1^2$ is an integer multiple of $n$:

$$x^2 - 1^2 = nk$$

Step 2: Factoring into Consecutive Integers ($a$ and $a+2$)

Using the difference of two squares and substituting $a = x - 1$ (so that $x = a + 1$):

$$(x - 1)(x + 1) = nk \implies a(a + 2) = nk$$

Step 3: Imposing Symmetric Quadratic Growth on $k$

To study the intersections dynamically, we parameterize $k$ so that it shares the same quadratic growth pattern as the left-hand side. We set $k = b(b + 2)$ for some integer $b$:

$$a(a + 2) = n \cdot b(b + 2)$$

Step 4: Completing the Square and Transformation

Rewriting both sides as completed squares:

$$(a + 1)^2 - 1 = n \left[ (b + 1)^2 - 1 \right]$$

Applying the change of variables $X = a + 1 = x$ and $Y = b + 1$:

$$X^2 - 1 = n(Y^2 - 1)$$

$$X^2 - 1 = nY^2 - n$$

$$X^2 - nY^2 = 1 - n$$

2. Worked Example ($n = 21$)

For $n = 21$, the equation becomes $X^2 - 21Y^2 = -20$, or equivalently $X^2 = 21Y^2 - 20$.

Testing small integer values for $Y$:

Notice how $X = 8$ and $X = 13$ correspond directly to the non-trivial roots of $x^2 \equiv 1 \pmod{21}$.

Questions

1. Efficient Solvers: Is there a known, computationally efficient method (e.g., using continued fractions, class groups, or lattice reduction) specifically designed to find integer points $(X, Y)$ on $X^2 - nY^2 = 1 - n$ when $n$ is a large composite integer?
2. Computational Complexity: Does forcing $k = Y^2 - 1$ reduce the search space in a meaningful way compared to general quadratic sieve approaches, or is finding integer solutions to $X^2 - nY^2 = 1 - n$ computationally equivalent in hardness to general integer factorization?

Any insights, literature references, or historical context regarding this specific parameterization would be greatly appreciated!