7
$\begingroup$

Let's assume $n$ doesn't pass the Miller-Rabin test and $b$ is a witness. Meaning, $b^{\frac{n-1}{2^r}} \equiv 1 \pmod{n}$ where $\frac{n-1}{2^r}$ is even, but $c = b^{\frac{n-1}{2^{r+1}}} \not\equiv \pm1 \pmod{n}$. Show that $\gcd(c+1,n),\gcd(c-1, n)$ are non-trivial divisors of $n$.

So first of all, for my convenience:

  • Denote $n-1 = 2^ls$, $s$ is odd.
  • Denote $k=l-r$.
    • $c = b^{2^{k-1}s}$
    • $c^2 = b^{2^{k}s}$
    • $2^ks$ is even

It is given that $c^2 \equiv 1 \pmod{n} \implies (c-1)(c+1) \equiv 0 \pmod {n} \implies n\mid (c-1)(c+1)$

Now, I think we can assume that $n$ passed Fermat's theorem test (that's part of the initial tests of the Miller-Rabin algorithm).

Hence,

$$c^{r+1} = b^{2^l s} = b^{n-1} \equiv 1 \pmod {n}$$

but that isn't revealing anything new other than $r$ is odd (since $2$ must divide $r+1$).

What am I missing?

$\endgroup$
  • $\begingroup$ An unusual definition of a witness. How did you arrive at $c^{r+1}$ ? We have $2^{r+1}$ in the denominator of the exponent defining $c$. $\endgroup$ – Peter Dec 7 '17 at 16:31
  • $\begingroup$ @Peter, oh your're right. It suppose to be $c^{2^{r+1}}$ $\endgroup$ – Elimination Dec 8 '17 at 19:05
3
+500
$\begingroup$

The general statement is that whenever we have a nontrivial square root of $1$ modulo $n$, a value $c$ such that $$ c^2 \equiv 1 \pmod{n}, \qquad c \not\equiv \pm1 \pmod{n}, $$ then we obtain a factorization of $n$.

If $c^2 \equiv 1 \pmod n$, then $(c+1)(c-1) \equiv 0 \pmod n$.

If $c+1$ were relatively prime to $n$, then it would have an inverse modulo $n$, and we could multiply by $(c+1)^{-1}$ to conclude that $c-1 \equiv 0 \pmod n$. But this is ruled out by our assumption that $c \not\equiv 1 \pmod n$.

If $c+1$ were divisible by $n$, then we would have $c+1 \equiv 0 \pmod n$. But this is ruled out by our assumption that $c \not\equiv -1 \pmod n$.

So the only remaining possibility is that $c+1$ shares some, but not all, prime factors with $n$: that $\gcd(c+1,n)$ is a nontrivial factor of $n$.

The same goes for the other factor $c-1$.


More generally, whenever we find $a$ and $b$ such that $a^2 \equiv b^2 \pmod n$ but $a \not\equiv \pm b \pmod n$, the same argument shows that $\gcd(a+b,n)$ and $\gcd(a-b,n)$ are nontrivial factors of $n$. This is the basis for many integer factorization algorithms starting from Fermat's factorization method and ending with the quadratic sieve.

$\endgroup$
3
$\begingroup$

From $b^{\frac{n-1}{2^r}}\equiv 1\pmod n$, we see that there exists an integer $m$ such that $$b^{\frac{n-1}{2^r}}=mn+1\tag1$$ From $b^{\frac{n-1}{2^{r+1}}}\not\equiv \pm 1\pmod n$, we see that there exist integers $k,r$ such that $$b^{\frac{n-1}{2^{r+1}}}=kn+r+1\tag2$$ where $$\text{$1\le r\le n-1\quad$ with $\quad r\not=n-2$}\tag3$$

Since $\frac{n-1}{2^r}$ is even, we get, from $(1)(2)$, $$mn+1=b^{\frac{n-1}{2^r}}=b^{\frac{n-1}{2^{r+1}}\times 2}=\left(b^{\frac{n-1}{2^{r+1}}}\right)^2=(kn+r+1)^2=(k^2n+2kr+2k)n+(r+1)^2$$ implying $$1\equiv (r+1)^2\equiv r^2+2r+1\pmod n$$ which implies $$r(r+2)\equiv 0\pmod n\tag4$$

Here, supposing that $r+2=n+1$ implies $r\equiv 0\pmod n$ which is impossible.

So, from $(3)$, we have $1\lt r\lt n$ and $1\lt r+2\lt n$.

It follows from these and $(4)$ that both $r$ and $r+2$ are non-trivial divisors of $n$.

We have $b^{\frac{n-1}{2^{r+1}}}+1=kn+r+2$. Since $r+2$ is a non-trivial divisor of $n$, we see that $\gcd\left(b^{\frac{n-1}{2^{r+1}}} +1,n\right)$ is a non-trivial divisor of $n$.

We have $b^{\frac{n-1}{2^{r+1}}}-1=kn+r$. Since $r$ is a non-trivial divisor of $n$, we see that $\gcd\left(b^{\frac{n-1}{2^{r+1}}} -1,n\right)$ is a non-trivial divisor of $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.