[Math] Factorization using Miller-Rabin Primality Test

Question

Given an $n$ to factor, define $b_0 \equiv a^m\pmod{n}$ with $1 < a < n-1$ and $m \equiv \frac{n-1}{2^k}$ for $k$ as the maximum power of $\it 2$ in $n{-}1$. If $b_0 = \pm 1\pmod{n}$, then n is probably prime, otherwise, define $b_1 \equiv b_0^2\pmod{n}$ if $b_1 \equiv -1$ then $n$ is probably prime, if $b_1 \equiv 1$ then $n$ is composite. Keep going and define $b_i\equiv b_{i-1}^2\pmod{n}$ until $i = k-1$. At any time, if $b_i \equiv \pm 1$ then stop and we have a result as for $b_1$. At the end, if $b_{k-1} \not\equiv -1$, then n is composite.

Furthermore, this gives a way of factoring $n$. if $b_i \equiv 1$ and $i \neq 0$, then $gcd(b_{i-1} – 1, n)$ gives a factor of n.

My question is, if $b_i \equiv 1$, then $b_{i+1} \equiv 1$ as well. Does this also imply I can factor $n$ using $gcd(b_i – 1, n)$ as well?

Answer 1

The answer to your question is "no", since obviously we don't get anything from $\gcd(b_{(i+1)-1}-1, n)$ $= \gcd(b_{i}-1, n)$ $ = \gcd(1-1, n)$ $= \gcd(0, n)$ $ =n$.

---

You have a small omission and an error in your description of the Miller-Rabin test:

• $k$ is the maximum value consistent with integer $m$, i.e. $k$ is the multiplicity of $2$ in $n{-}1$.
• Note that if we find $b_i\equiv 1$ or $-1$, the process stops with a result (composite or probably prime respectively).
• "At the end", if $b_{k-1}\not\equiv -1 \bmod n$, then $n$ is composite.