3
$\begingroup$

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

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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
15
  • $\begingroup$ 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? $\endgroup$ Jul 9, 2023 at 14:34
  • $\begingroup$ 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. $\endgroup$ Jul 9, 2023 at 15:43
  • $\begingroup$ @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" $\endgroup$
    – poncho
    Jul 9, 2023 at 15:54
  • $\begingroup$ 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". $\endgroup$ Jul 9, 2023 at 16:05
  • $\begingroup$ Did I finally get the hang of it? $\endgroup$ Jul 9, 2023 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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