Probability of Enhanced MR test outcome for NOT A POWER OF PRIME

I come up with an approach to find the probability of the outcome "PROVABLY COMPOSITE AND NOT A POWER OF A PRIME" of enhanced MR test.

In context of this question, the probability/error probability which I'm trying to compute is the probability at which the enhanced MR test returns outcome as PROVABLY COMPOSITE WITH FACTOR or PROBABLY PRIME for a given composite, odd, prime power number.

The error probability of a primality test for the given random number = $$4^{-k}$$

Lets say $$n = p^q$$ and $$1

For any p, the number of possible values of $$b$$ such that $$gcd(b,n) >1 = n/p$$

The probability of choosing $$b$$ one among above out of $$n-2$$ values = $$(n/p) /n$$ = $$1/p$$

Total combined error probability = $$4^{-k} + 1/p$$

Since this probability is very much depends on the prime power number itself, I computed these min, high and average probabilities.

The lowest possible p is in the range $$2^{10}$$ since we checking the smaller primes until 753, and max possible p value is $$n^{1/2}$$ so the error probability lies in b/w $$4^{-k} + 1/2^{-10} < prob < 4^{-k} + 1/2^{n^{1/2}}$$.

Based on which lets say if we want total error probability of $$2^{-100}$$ then we need to run this enhanced MR for atleast $$10$$ iterations as $$(4^{-k} + 1/2^{-10})^{10}$$ < $$2^{-100}$$.

So is the error probability is of $$4^{-k} + 1/p$$ for $$n = p^q$$ is right? Can you please share your thoughts.

Note: As @fgrieu pointed out my intention is to calculate these probabilities or run this algorithm in the presence of adversary. So based on which $$n$$ is any given prime.

• Error means for a given prime power if the enhanced MR test reports either it as prime$(4^{-k})$ or not a prime with factor$(1/p)$. Yes to compute this probability I considered returning "PROVABLY COMPOSITE WITH FACTOR" for a composite not a power of a prime as an error. Commented Jul 25 at 10:02
• sure, added the definition of error probability, Here for a given MR test since $w$ is fixed, i only considered $b$ as variable and computed the probability. I tried to compute probabilities for any $w$ over any $b$ to find the probability for the average case but couldn't come up with a solution. Commented Jul 25 at 10:35
• Actually, given a power of a prime, that is, $p^k$ for prime $p$ and $k > 1$, the enhanced MR test will always find a factor. Hence, the error probability in that specific case is 0. Commented Jul 25 at 13:14
• @fgrieu: If your guess is correct, then the answer (probability that the algorithm returns something other than PROVABLE COMPOSITE AND NOT A POWER OF A PRIME) is 1 - for example, given a Carmichael number, the Enhanced MR test will always return either PROBABLY PRIME or find a factor. Commented Jul 25 at 14:05
• @poncho: regarding your earlier remark, isn't there also the (extremely remote) possibility that enhanced MR returns "PROBABLY PRIME" when passed an odd composite prime power? For a medium example, when testing $1006003^2$ with the single witness $b=3$?
– fgrieu
Commented Jul 25 at 14:05

We assume correct FIPS 186-5 enhanced Miller-Rabin test. We stick to the question's use of $$n$$ and $$k$$ for w and iterations.

When passed a composite odd prime power $$n=p^q$$, the output is either PROVABLY COMPOSITE WITH FACTOR (most often) or PROBABLY PRIME (vanishingly rarely); never PROVABLY COMPOSITE AND NOT A POWER OF A PRIME. Hence the probability in the second paragraph of the question (v5) is $$1$$, regardless of how prime $$p$$ and $$q>1$$ are chosen.

PROBABLY PRIME is returned for a composite odd prime power $$n=p^2$$ if for all the $$k$$ base(s) $$b$$ selected at step 4.1 it holds $$b^{\,p-1}\bmod p^2=1\,$$. That is: $$p$$ is a Wieferich prime to base $$b$$. This is rare, as apparent in Table 1 of Amir Akbary and Sahar Siavashi's The largest known Wieferich numbers (Integers 18, 2018). Their record Wieferich prime is $$p=9809862296159$$. The $$b=22^j$$ for $$1\le j\le19$$ are among suitable bases. The probability of getting PROBABLY PRIME for the corresponding 87-bit composite $$n$$ is thus $$>2^{-82.1\,k}$$. I fail to exhibit a larger composite $$n$$ that's a power of a prime and base $$b$$ with outcome PROBABLY PRIME.

Based on earlier exchanges with the OP, the question's context is implementing a plausibility test of RSA public moduli per NIST's SP 800-89 5.3.3 by the example method given, specifically step e (corrected) which suggests "obtaining an output of COMPOSITE AND NOT A POWER OF A PRIME using the enhanced MR primality test".

The OP wants good assurance that their plausibility test won't reject RSA moduli $$n$$ that match all the stated acceptance criteria, even when such $$n$$ is one they specifically crafted for testing purposes as a composite not a power of a prime with it's smallest prime factor larger than $$\ell=751$$, but still small enough that the enhanced MR test sometime returns PROVABLY COMPOSITE WITH FACTOR (rather than PROVABLY COMPOSITE AND NOT A POWER OF A PRIME as it essentially always does for $$n$$ generated for the purpose of being a safe RSA modulus).

In my opinion it's best to reject any $$n$$ which is observed making the enhanced MR test return PROVABLY COMPOSITE WITH FACTOR. That can only improve security. That will only perceptibly lower availability of a deployed system when and if it's attempted to load it with $$n$$ grossly insecure as an RSA modulus (indirect proof: if the enhanced MR test, which is well known, had sizable probability to pull out a factor of RSA moduli intended to be secure, that would be a blow to RSA's security and RSA wouldn't be used). And then it's desirable to be unavailable rather than insecure. That won't prevent getting rubber-stamped by actual security authorities.

Further, @poncho remarks [update: with proof] that if $$n$$ is a Carmichael number then the extended MR test never ends in PROVABLY COMPOSITE AND NOT A POWER OF A PRIME. Rather it ends either in PROVABLY COMPOSITE WITH FACTOR (most often) or in PROBABLY PRIME (with a probability somewhat below $$2^{-2\,k}$$).

And it's possible to generate large Carmichael numbers of bit size in the order of a few thousands bits as used for RSA moduli: $$n=(6u+1)(12u+1)(18u+1)$$ having its 3 obvious factors prime is a Carmichael number. Such $$n$$ matches no explicit criteria requiring rejection per SP 800-89 5.3.3. Yet such $$n$$ is trivial to factor using $$u=\lfloor(n/1296)^{1/3}\rfloor$$, which is reason enough to reject it. And we have no other choice if we want the plausibility test to only directly use the outcome of the extended MR test to prove that a candidate $$n$$ is a composite not a power of a prime (the only method suggested in SP 800-89 5.3.3), and terminate for any $$n$$ a tester can feed it.

In conclusion: I recommend to perform test e of SP 800-89 5.3.3 as a single extended MR test, and reject $$n$$ if the outcome is other than PROVABLY COMPOSITE AND NOT A POWER OF A PRIME. We can use $$k=5$$ for any $$n$$ at least 1024-bit. This simplifies, and allows to perform the tests in the order stated. It rejects some $$n$$ that it's not mandated to reject, but that's justified.

• I'm assuming this [that Carmichael numbers will never return PROVABLY COMPOSITE AND NOT A POWER OF A PRIME] - (I welcome a proof) - the proof is simple. That will be the result only if $g$ is relatively prime to $n$ and $g^{n-1} \ne 1 \pmod n$. For Carmichael numbers, $g^{n-1} = 1 \pmod n$ (except in that case that $g$ is not relatively prime to $n$) Commented Jul 25 at 21:58
• Thank you for the answer. One small doubt is after iteration one, if the enhanced MR test didn't return, then there exists a witness $b$ for which $1=b^{w-1}modw$, so in this case this given number $w$ can be either prime or carmichael number and in either case it was not PROVABLY COMPOSITE AND NOT A POWER OF A PRIME. So can I simply run MR test with just one(k=1) iteration? Can you please help me in understanding what we achieving with k=5 or with higher iterations? Commented Jul 26 at 4:41
• is it like even for composite and non-carmichael numbers also there exists some bases $b$ such that this holds true $1=b^{w−1}\bmod w$? Commented Jul 26 at 5:15
• @sg777: Yes. That's the vast majority of integers. Even if we fix $b$, these $w$ are the (Fermat) pseudoprimes to base $b$ that are not Carmichael numbers, and are aplenty. For $b=2$, that's A001567$\,\setminus\,$A002997.
– fgrieu
Commented Jul 26 at 5:52

I'm not sure what the $$k$$ stands for in the $$4^{-k}$$ term, but in general the 1/4 upper bound for passing a single strong primality test only applies to numbers with two or three distinct prime factors and represents the probability that the Legendre symbol of the witness with respect to the two prime factors are unequal.

In the case of a prime power, say $$n=p^q$$ the strong primality test with witness $$b$$ will pass if and only if $$b$$ is $$p^{q-1}$$th power mod $$n$$. To see this, note that the order of the (cyclic) multiplicative group is $$\phi(n)=p^{q-1}(p-1)$$ and that $$p^{q-1}$$ is coprime to $$n-1$$ whereas $$p-1$$ divides $$n-1$$.

The chance of finding a single random $$b$$ which acts as a witness for $$m$$ is therefore $$(p-1)/(n-1)$$.

• $k$ is number of iterations in MR enhanced test, I messed up the context and also my calculations for this question. @fgrieu added the context in the answer. Commented Jul 26 at 4:55
• I don't get the meaning of the proposition "the 1/4 lower bound for passing a single strong primality test only applies to numbers with two distinct prime factors". Isn't the proportion of misleading witnessses for the strong pseudoprime test less than 1/4 for all integers? I don't see a clear relation between proportion of misleading witnesses for the strong pseudoprime test and number of distinct prime factors, beyond this proportion being vanishingly low for a single prime factor.
– fgrieu
Commented Jul 26 at 9:15
• @fgrieu "lower" should read "upper" now amended. The proportion of false witnesses for an Euler test on a number that passes the weak test, is the proportion of residues where the Lagrange symbol for all prime factors matches. This probability is $2\times 2^{-\omega(n)}$, so a 1/4 for three prime factors, 1/8 for 4 prime factors and so on. I was mistaken on the 3 prime factor case, for the two prime factor case see Schoof mat.uniroma2.it/~schoof/millerrabinpom.pdf Commented Jul 26 at 14:49