Appendix F: Recognizing Primes - Codes: The Guide to Secrecy from Ancient to Modern Times - page 559

F.5 Decision Problem or Primality Test?

On page 551, we discussed Lucas' test as an application of Fermat's compos-
iteness criterion (F.1) (contrapositively speaking). There is, however, a brand
of opinion that Lucas' test is really a decision problem (see page 502). Here is
the reasoning.
Lucas' test tells us to compute 2 n − 1 (mod n ). If

2 n − 1 ≡ 1 (mod n ) ,

then we know that n is not prime and send it off to some factoring routine such
as discussed in Appendix C.
If

2 n − 1

≡ 1 (mod n ) ,

then we send it off for primality testing. Hence, the Lucas test may be viewed
as a decision problem on whether to send n for primality testing or factoring.
Since decision problems are “yes-no” issues, we phrase the question as

Do we send n for primality testing?

If the answer is yes, we do so, and if the answer is no, we send it to a factoring
algorithm.
There is merit to the above argument. Attendant with the above viewpoint is
the opinion that assigning probabilities or improving such estimates has nothing
to do with primality testing. Thus, this school of thought would not consider
the MSR test in Section F.2 to be a test that in any way assists with practical
primality testing. Given that MSR does not satisfy our criterion (2) given on
page 550, this viewpoint also has some merit. That said, this does not prevent
the use of such algorithms in practice.
The aforementioned point of view is presented for mental fodder and general
interest in what is often a contentious topic.