Enhanced MR test understanding the steps in detail

I'm going through the Enhanced MR test cited in FIPS 186-5, I have couple of questions regarding the following steps

4.5 $$z = b^m \pmod w.$$

4.6 $$\textrm{If }((z = 1)\textrm{ or }(z = w – 1)), \textrm{then go to step }4.15.$$

Q.1 Since $$b$$ is coprime with $$w$$, and here if $$z=1$$ in which case if we check $$m=w-1$$ then according to Eulers theorem it guarantees that $$w$$ is prime and we can exit from the MR test rather than continue further with other iterations. But we initially choosing $$m$$ to a lower value than $$w-1$$ on purpose which is $$m= (w-1)/2^a$$. Can you help me in understanding why we choosing $$m$$ such a way.

Q.2 If $$z = w-1$$ what does that actually mean like is there something wrong with the chosen b such that why we going to step 4.15 directly.

Q.3 At step 4.12 $$g = GCD(x – 1, w).$$ if the number is composite $$x$$ is in some form $$b^jmodw$$ where $$1<=j<=a$$, and $$g= GCD(x – 1, w) > 1$$ but how we are getting a factor from $$x$$ for $$w$$ here. Can this be proved?

• "Enhanced MR" is essentially the traditional Miller-Rabin probabilistic primality test, with a few extra checks included to detect when we have a power of a prime ($p^k$ for prime $p$, $k > 1$). You might want to study the traditional Miller-Rabin test first... Commented Jul 24 at 16:30

Euler stated many theorems, so it's hard to tell which one Q.1 considers. But none implies: if $$b$$ is coprime to $$w$$ and $$b^{w-1}\bmod w=1$$ then $$w$$ is prime, and that does not hold. A counterexample is $$w=341$$ (or other in A001567), $$b=2$$. Another is $$w=561$$ (or other in A002997), and any $$b$$ coprime to $$w$$.

I think Q.1 is (incorrectly) using Fermat's little theorem, which can be re-stated as: if $$b$$ is coprime to $$w$$ and $$w$$ is prime then $$b^{w-1}\bmod w=1$$.

If $$z=w−1$$ what does that actually mean?

It means that either $$w$$ is prime, or we happen to have used $$b$$ such that $$w$$ is a strong pseudoprime to base $$b$$.

Using the notation in FIPS 186-5 appendix B.3.1 and B.3.2, the strong pseudoprime test works as follows. We want to test some odd integer $$w>2$$ for primality. We find the uniquely defined $$a$$ and odd $$m$$ with $$w-1=m\cdot2^a$$. Notice that $$a\ge1$$. We select some $$b$$ with $$1. Notice that if $$w$$ is prime then $$b$$ is coprime with $$w$$.

Define $$z_0=b^m\bmod w$$, and for $$j>0$$ define $$z_j={z_{j-1}}^2\bmod n$$. By induction, it holds $$z_j=b^{m\cdot2^j}\bmod w$$. Therefore, by Fermat's little theorem, if $$w$$ is prime then $$z_a=1$$.

Therefore if $$w$$ is prime then $${z_{a-1}}^2\bmod w=1$$, which implies $$(z_{a-1}-1)(z_{a-1}+1)\bmod w=0$$. Therefore if $$w$$ is prime then $$z_{a-1}$$ is one of $$1$$ or $$w-1$$.

If $$w$$ is prime and $$a>1$$ and $$z_{a-1}=1$$, then similarly $$z_{a-2}$$ is one of $$1$$ or $$w-1$$.

By infinite descent, if $$w$$ is prime then either $$z_0=1$$ or there exists some $$j$$ with $$0\le j and $$z_j=w-1$$.

By contraposition, if $$z_0\ne 1$$ and for all $$j$$ from $$0$$ to $$a-1$$ it holds $$z_j\ne w-1$$ then $$w$$ is not prime.

The strong pseudoprime test applies the above theorem. The simplest implementation computes all the $$z_j$$ for $$j$$ from $$0$$ to $$a-1$$ per the definition given above, and tests if it holds $$z_0\ne 1$$ and $$z_j\ne w-1$$ for all these $$j$$. In the affirmative, it's concluded that $$w$$ is not prime. Otherwise that strong pseudo prime test to base $$b$$ is inconclusive: $$w$$ could be prime, or not. In the later case, $$w$$ is said to be a strong pseudoprime to base $$b$$. An example is $$w=2047$$ (or other in A001262), $$b=2$$.

In FIPS 186-5 B.3.1 and B.3.2, and commonly, it is used three independent "early abort" optimizations of that simplest algorithm for the strong pseudoprime test, none of which changing that test's outcome. Computation can be aborted as soon as it's found any one of:

• $$z_0=1$$, with the strong pseudoprime test inconclusive.
• $$z_j=w-1$$, with the strong pseudoprime test inconclusive.
• $$z_j=1$$ for $$j\ne 0$$ and $$z_{j-1}=w-1$$, with the strong pseudoprime test concluding that $$w$$ is not prime.

A Miller-Rabin test performs a number of strong pseudoprime tests for random choice of base $$b$$, stopping when a strong pseudoprime test concludes that $$w$$ is composite (which also is the conclusion of the Miller-Rabin test). Otherwise the Miller-Rabin test concludes that $$w$$ is probably prime.

The enhanced Miller-Rabin test of B.3.2 performs the same, excepts that

• for each $$b$$ chosen it's computed $$g=\gcd(w,b)$$ and if $$g\ne1$$ the enhanced Miller-Rabin test terminates concluding that $$w$$ is a composite with non-trivial factor $$g$$.
• when the strong pseudoprime test with (at least) the last of the above three optimizations finds a $$z_j$$ allowing to conclude that $$w$$ is not prime, that is when for $$j>0$$ it holds $$z_j\ne w-1$$ and $$z_{j+1}=1$$ (as detected by said third optimization), or when it's reached $$j=a-1$$ with $$z_j\ne w-1$$, then it's computed $$g=\gcd(w,z_j)$$, and:
• if $$g\ne1$$, the enhanced Miller-Rabin test terminates concluding that $$w$$ is a composite with non-trivial factor $$g$$.
• if $$g=1$$, the enhanced Miller-Rabin test terminates concluding that $$w$$ is a composite not a prime power. I refer to @poncho's proof of that later property.
• Understood, it does answers my other questions. One small doubt is, for false positive cases in MR test, is it the case that in all those iterations of MR $w$ is strong pseudoprime to all those randomly chosen bases? I mean can i interpret the error probability of $2^{-100}$ for RSA 1024 for number of iterations as 4, is the probability of choosing 4 random bases that makes a given composite number passes the MR test? Commented Jul 24 at 7:02
• @sg777: Yes in case of false positive in MR test, the tested integer is a strong pseudoprime to all chosen bases. There is probability $<2^{-100}$ that A RANDOM 1024-bit composite is a false positive to MR test for 4 random bases. However, that's not true for ANY GIVEN 1024-bit composite (which is how the second part of the above comment could be read) because the given composite could be chosen as a Carmichael number. In which case the probability is much higher (I only know an upper bound of $2^{-8}$ for the probability).
– fgrieu
Commented Jul 24 at 7:48
• One confusing thing is this step 4.7.4 If $(z = 1)$, then go to step 4.12. If $z_a = 1$ then $z_{a−1}$ is one of $1$ or $w−1$ but if $z_{a-1}$ is one then MR declaring the number as one of composite with factor or no prime power. [Update] I got it now, it is like since $z_j≠w−1$ and $z_{j+1}=1$ then $z_j$ is either $1$ or $w-1$ since it contradicts with $z_j≠w−1$ and $z_j≠1$ so it indicates that $w$ has root other than 1 and that makes it composite. Commented Jul 24 at 11:42