# How exactly does finding a square root of $1$ modulo $N$ enable us to factor $N$?

The aim of the algorithm is to find a square root $$b$$ that is different from $$1$$ and $$-1$$; such a $$b$$ will lead to the factorization of $$N$$, as in other factoring algorithms like the quadratic sieve.

I'm not quite sure how finding such a $$b$$ will lead to the factorization of $$N$$. Nevertheless, I will write down what I understood so far.

Say we find a $$b$$ (apart from $$1$$ and $$-1$$) such that

$$b^2 \equiv 1 \pmod N$$

$$\implies b^2-1^2 \equiv 0\pmod N$$

$$\implies (b-1)(b+1) \equiv 0 \pmod N.$$

Then computing the GCD of $$b-1$$ or $$b+1$$ with $$N$$ will produce a factor of $$N$$, although it might be a trivial factor ($$1$$ or $$N$$). If it's a trivial factor we should try with a different $$b$$, as there are at least two possible values of $$b$$, apart from $$1$$ and $$-1$$, as a consequence of the Chinese Remainder Theorem.

Is this the correct way to find a factor of $$N$$ (as stated on the Wiki article) or am I missing something?

Note: $$N$$ is an odd composite number.

• If $b\ne \pm 1\mod N$, you actually get a non-trivial factor this way. Commented Feb 16, 2019 at 13:59
• @Peter Interesting! If possible, could you elaborate on "why" in an answer below?
– user568976
Commented Feb 16, 2019 at 14:00
• $\gcd(b\pm 1,N)$ cannot be $N$ because that would imply $N\mid b\pm1$, i.e., $b\equiv \mp 1\pmod N$. And $\gcd(b\pm1,N)$ cannot be $1$ because that would imply $N\mid b\mp1$, so $b\equiv\pm1\pmod N$. Commented Feb 16, 2019 at 14:02

Well, in general for factor basis algorithms for factorization, if you finally obtain $$b^2\equiv c^2\mod n$$ and $$b\not\equiv \pm c\mod n$$, then compute $$\gcd(b+c,n)$$, which will be a nontrivial factor of $$n$$.
• Thanks. But why is the $b\not\equiv \pm c\pmod n$ condition necessary here?