# Purpose of the b1, b2, b3.... terms in Rabin-Miller Primality Test

In Rabin-Miller primality test, let N be the number you're checking for primality. Here N = 78007. Let m be the number you get after dividing (N - 1) by 2 several times until you can no longer do so. In this case, m = 39003.

The next step is to pick an A, here we pick A = 3. Now we calculate b0 = Am mod N. Now, if that A's b0 turned out to be (N-1) or 1, then the algorithm says "N is probably prime". In any other case, it says "N is composite".

At this point, we have two choises: Pick another A and compute its b0 OR keep that A and start computing bi terms for it, where bi = (bi-1)2 mod N. If a particular bi = (N-1), the algorithm says "N is probably prime", if it's anything else, it says "N is composite".

MY QUESTION IS: What exactly is the purpose of those bi terms? How do I know when to stop computing a particular A's bi terms and go to a new A? Do I just see how many bi terms it will take before the algorithm says "probably prime" and then go to a different A? Or do I just compute every A's b0 only, record what the algorithm says and go to a new A value right away and completely ignore every A's bi terms?

Any explanation I'd highly appreciate. Even more so one that doesn't use heavy terminology from number theory so I can actually understand it. :P

• It was (N-1) divided by 2, not N. My bad, I corrected it. Jul 9, 2023 at 8:20

What exactly is the purpose of those $$b_i$$ terms?

$$b_i = A^{2^i m} \bmod N$$

If $$\lambda$$ is the number of times you divided by 2 in the first step, then $$2^\lambda m = N-1$$.

Hence, by Fermat's little theorem, if $$b_\lambda \ne 1$$, then we know $$N$$ is not prime (because $$A^{N-1} = 1 \pmod N$$ for any prime $$N$$, as long as $$A$$ is a not multiple of $$N$$). Hence, if you go $$\lambda$$ steps, and don't hit one, we know we have a composite.

At this point, we have two choises

Actually, you don't; you always perform $$\lambda$$ squarings unless you hit $$N-1$$ (actually, it turns out $$\lambda-1$$ is sufficient). That is, unless you hit 1 initially, or $$N-1$$ on any later step, we know $$N$$ is composite (either by Fermat's Last Theorem, or because nontrivial factors are deducible). We have to do that for the Miller-Rabin proof to hold (and anyways, that's a lot cheaper than picking another $$A$$ and computing $$A^m$$ all over again).

This is because if we have a value $$B \ne 1, N-1$$, and $$B^2 = 1 \pmod N$$, then $$N$$ is composite (and $$\gcd(B-1, N), \gcd(B+1, N)$$ are nontrivial factors). This (along with Fermat's little theorem) are why when MR says composite, it has proven it.

• And if you go up to λ steps in the Bi terms and you DO hit 1 somewhere along the way, then (and only then) the algorithm says "probably prime"? And doing this for a number of A's is how you become more and more certain that the number is prime, right? Jul 9, 2023 at 14:34
• Im still confused about when to look for (N-1) as a result and when to look for 1 and when to stop computing Bi terms. Jul 9, 2023 at 15:43
• @KevinStefanov: at the very first step (immediately after computing $A^m \bmod N$), you look for 1 or $N-1$ - if you see either, it's "probably prime". After that, $N-1$ means "probably prime", a 1 means "composite" (assuming you would have stopped for a previous $N-1$ term). And, if you don't see an $N-1$ after $\lambda$ steps, that's "composite" Jul 9, 2023 at 15:54
• Okay, so to summarize: For any value of A and let K be the number of times we managed to divide by 2: if b0 = 1 OR b0 = (N-1) => probably prime. Else if b0 is neither of those, begin computing Bi terms until you hit one of 3 cases: EITHER you see (N-1), in which case you stop and say "probably prime" and go test other A's, OR you see 1 in which case you stop and conclude "N is composite, no need to test other A's", OR you have reached the B(k-1)th term and so far have not seen (N-1) even once, in which case you conclude "N is composite, no need to test other A's". Jul 9, 2023 at 16:05
• Did I finally get the hang of it? Jul 9, 2023 at 16:05