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.

Answer 2

Yes you can but the reason that its regarded as primality test and not as factoring algorithm is because the number of numbers that do reveal there factorization using this method are very scarce and are called pseudoprime to base $a$ and they must not be Carmichael number. the first number that have this property is $341$, and because $2^{340} = 1 \mod 341$ and $2^{\frac{340}{4}} = 32 \mod 341$ so the factorization of $341$ is $GCD(341,32+1)=11$ and $GCD(341,32-1)=31$.

for more about these numbers and there proprieties i suggest you read about Carmichael numbers and pseudoprime numbers and strong pseudoprime for primality test like Miller-Rabin.

on the other hand (to show you why it won't work as factorization method) take $n=3337$ and some base that its not the one of the factors of $n=3337$, for the sake of the argument lets just take $a=2$ so $2^{3336} =1835 \not= 1 \mod 3337$ and because its not equal to $1$ in most of cases it won't work in General.

hope you find what you are looking for