View source for Talk:Miller–Rabin primality test

{{WikiProject banner shell|class=C|
{{WikiProject Computer science|importance=high}}
}}
{{Broken anchors|links=
* <nowiki>[[Modular arithmetic#Properties|compatible with exponentiation]]</nowiki>  The anchor (#Properties) has been [[Special:Diff/1134946352|deleted by other users]] before. <!-- {"title":"Properties","appear":{"revid":776267624,"parentid":773590112,"timestamp":"2017-04-19T23:25:28Z","removed_section_titles":[],"added_section_titles":["Properties"]},"disappear":{"revid":1134946352,"parentid":1134929827,"timestamp":"2023-01-21T17:20:07Z","removed_section_titles":["Properties"],"added_section_titles":["Basic properties","Advanced properties"]}} -->
}}

== Misc ==
To 203.217.64.49:
* Please direct questions and other discussion on the talk page, not in the article text.
* Any nonzero integer is uniquely expressible as an odd multiple of a power of 2. This defines ''k'' and ''m'' from ''n''. In other words, ''k'' is the largest integer such that 2<sup>''k''</sup> divides ''n''&minus;1.
-- [[User:EJ|EJ]] 11:49, 21 Sep 2004 (UTC)

Don't you get some really large numbers when doing this? I'm trying to write a C++ implementation using 1009, which is prime, as a test  number,  and I just realized that in larger bases you get very big numbers in the second test. For example, <math>1009 = 2^4 \times 63</math>, so for the second test you might have <math>2^{2^363} = 2^{504}</math>

:I haven't stepped through it, but as with all crypto stuff involving modular exponentiation, you can keep reducing it at every step.  See [[modular exponentiation]]. [[User:CryptoDerk|CryptoDerk]] July 8, 2005 21:25 (UTC)

::You do indeed get really big numbers. To quote a step-by-step implementation (see given link<ref>H. Glarner, ''Miller-Rabin Primality Test, Step by Step'', http://www.gandraxa.com/miller_rabin_primality_test.xml, retrieved 2011-08-02</ref>):<br>"[...] probing 24155007172823 for primality requires the evaluation of 17<sup>12077503586411</sup> mod 24155007172823." [[User:Gulliveig|Gulliveig]] ([[User talk:Gulliveig|talk]]) 04:14, 20 June 2009 (UTC)

::: But you won't ever work with a number larger than 24155007172823^2 using modular exponentiation. [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 07:13, 20 June 2009 (UTC)

Not sure if this is appropriate here or not, but I just wanted to thank everyone who works on Wikipedia compsci, math, and crypto pages, especially this one. I have learned so much, just wanted to give a hearty thank you for being clear, including psudocode and step by step instructions. [[User:Can2016|Can2016]] ([[User talk:Can2016|talk]]) 14:23, 1 July 2019 (UTC)

== Ruby Code ==

Wouldn't it be much (well, at least a little, compared to the overall complexity) more efficient to store the value of s instead of shifting until we reach n-1 in the example Ruby code? I do not know Ruby, but it is safe to say that shifting the same values repeatedly is less efficient than storing the value of s in the calculation. <b>[[User: Coolv|Coolv]]</b><small>([[User talk:Coolv|Talk]] • [[Special:Contributions/Coolv|Contribs]])</small> 19:11, 15 June 2007 (UTC)
: I'd expect that your proposal would have a very small impact on the runtime, because shift operations are cheap compared to modular multiplication. But your proposal would possibly make the code easier to understand. E.g., it seems that even the author of the code was a little confused. The while loop computes all powers <math>a^{2^r d}</math> for all <math>r\leq s</math> while the Miller-Rabin test only calls for the cases with <math>r\leq s-1</math>. I'd further propose the following modifications: (1) the functions should not be called prime, since it is only a pseudoprimality test; (2) negative integers should not be declarde prime. [[User:85.2.99.96|85.2.99.96]] 16:16, 4 July 2007 (UTC)

== Smallest number for which MR test is uncertain? ==

Hello. It seems one could establish by brute force that the MR test gives exactly the right answer for all numbers up to some limit (determined by how long you run the MR test on successive integers). Has anyone done a brute force search like that? Or maybe someone has proved that MR test is correct (i.e., reports N is prime iff N is actually prime) for all numbers up to some bound? -- I'm assuming here that the test is computationally deterministic, i.e., if I run the test twice on the same input, I'll always get the same report. Maybe my understanding of the test is flawed. It seems like the "probabilistic" aspect of the test could be explained at greater length. Many thanks to the authors for their work on this article. [[User:207.174.201.18|207.174.201.18]] 18:47, 1 February 2006 (UTC)

: You apparently misunderstood something. Probabilistic tests are explained at greater length in [[Primality test]] and [[Randomized algorithm]], which are both prominently linked from the first paragraph of the article.

:: It would help this article to briefly state what is the import of the fact that Rabin's version is probabilistic. Given the subtlety of the concept, it's not enough to give a link and assume the readers can go figure it out for themselves. [[User:207.174.201.18|207.174.201.18]] 00:43, 2 February 2006 (UTC)

::: Well, people certainly ''can'' go follow the link, and at some point it becomes necessary to assume they ''do'', because it is impossible to repeat everything everywhere. But I'll try to put some summary here, you're right that the concept is confusing. -- [[User:EJ|EJ]] 20:16, 3 February 2006 (UTC)

: The ''probabilistic'' (Rabin's) version of the algorithm, which is discussed in the article, is ''provably'' correct for all composites. It is ''not'' deterministic, which is (1) the whole point of the definition of a probabilistic test, and (2) obvious from the description of the algorithm: "pick ''a'' randomly in the range [1, ''n'' − 1]". I have removed the irrelevant, and wrong as stated, sentence from the "Additional information" section, which might have confused you.

:: What can be said about Rabin's test if it is implemented on a computer which has deterministic hardware? (I.e., assuming random numbers come from a pseudorandom number generator and not from atomic decay or some other "really random" source.) [[User:207.174.201.18|207.174.201.18]] 00:43, 2 February 2006 (UTC)

::: That's a very good question, but I'm afraid that nobody knows a satisfactory answer. Derandomization and pseudorandom generators are a big topic in theoretical computer science. However, these constructions of PRG tend to be inefficient (and thus rarely used in practice), and they depend on unproven assumptions about computational hardness of certain functions. PRG used in practice are based on heuristic without any serious analysis. -- [[User:EJ|EJ]] 20:16, 3 February 2006 (UTC)

: The ''deterministic'' (Miller's) version of the algorithm, which is only briefly mentioned in the introduction, is only ''conjectured'' to be correct for all composites. As for brute force verification, it is known e.g. that all numbers ''n'' < 341,550,071,728,321 which pass the test for bases ''a'' = 2, 3, 5, 7, 11, 13, and 17, are prime [http://primes.utm.edu/prove/prove2_3.html]. As 17 is well below 2(ln ''n'')<sup>2</sup>, Miller's test is also correct for these ''n''. The [[Riemann hypothesis]] was also verified by brute force for a lot of numbers, but I don't know whether anybody tried similarly to verify the [[Generalized Riemann Hypothesis]] for quadratic Dirichlet characters, which is what the Miller test depends on. -- [[User:EJ|EJ]] 20:22, 1 February 2006 (UTC)

:: OK, thanks a lot for these facts. If I understand correctly, the outcome of the MR test is uncertain only if ''n'' >= 341,550,071,728,321 (because for numbers less than that, the test reports a number may be prime iff it is indeed prime). I think this aspect should be mentioned in the article itself. [[User:207.174.201.18|207.174.201.18]] 00:43, 2 February 2006 (UTC)

::: Bear in mind that these results only concern the deterministic version of the algorithm, they are irrelevant for the randomized version. Also, do not take the bound too seriously, that fact that I could quickly find it does not mean that no better bounds are available.

::: The current (almost nonexistent) coverage of the deterministic algorithm in the article should be expanded, thanks for the tip. -- [[User:EJ|EJ]] 20:16, 3 February 2006 (UTC)

:::: The ANTS'94 paper by Alford, Granville and Pomerance contains some conjectures about the necessary number of tests needed for a deterministic version. I.e., the expect that <math>(1+o(1))(\log(n)\log\log(n))</math> tests is sufficient, whereas <math>o(\log (n))</math> is not sufficient. [[User:24.228.93.22|24.228.93.22]] 05:07, 5 February 2006 (UTC)

::::: Thanks for the pointer. -- [[User:EJ|EJ]] 17:30, 11 February 2006 (UTC)

:::Bleichenbacher [http://www.bell-labs.com/user/bleichen/diss/thesis.html] showed that Miller's test holds for ''n'' < 1{{e|16}}. That's the best result I've seen; I'd love to know of a better result.  Sloane's OEIS doesn't have much information about SPSPs above 1{{e|13}} and nothing above 1{{e|16}} as I recall. [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|talk]] • [[Special:Contributions/CRGreathouse|contribs]])</small> 02:38, 6 August 2006 (UTC)

:::: Unfortunately I can not open the PS files mentioned in your source with any of my software. I tried to e-mail him, but he does not seem to work there anymore. In the meantime, if someone could answer, if Bleichenbacher did work with "Jaeschke's" witnesses a={2,3,...,17} or if he had to include more, it would really be appreciated. - I also tried to contact Jaeschke (via a 3rd party) about progresses (i.e. better results). If I succeed with these attempts, I will update the article accordingly. [[User:Gulliveig|Gulliveig]] ([[User talk:Gulliveig|talk]]) 12:57, 20 June 2009 (UTC)

:::: Meanwhile I did some additional research. Apparently Pomerance, Selfridge, and Wagstaff [PSW 1980] calculated the first 4 values of this sequence, Jaeschke [Jaeschke 1993] calculated the next four, and Zhang and Tang [ZT 2003] provided for more values, not listed yet in the sequence. I added them, incl. reference. With those, we are at 318,665,857,834,031,151,167,461 now. [[User:Gulliveig|Gulliveig]] ([[User talk:Gulliveig|talk]]) 13:44, 20 June 2009 (UTC)

::::::There are several freely available [[PostScript]] previewers, for example [[Ghostscript]] front-ends such as Ghostview or GSview (see [http://pages.cs.wisc.edu/~ghost/]). —&nbsp;[[User:EmilJ|Emil]]&nbsp;[[User talk:EmilJ|J.]] 13:18, 22 June 2009 (UTC)

::::: You misunderstand Zhang & Tang.  They give upper bounds, not values.  They did not prove that there are no failures below those numbers, only that they fail at those numbers. [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 20:17, 20 June 2009 (UTC)

:::::: Thank you, CR. Now, [http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html] says, that although it is known that MR holds for ''n'' < 10<sup>16</sup>, for larger number "[...] no counterexamples are known and if any exist, they are expected to occur with extremely small probability (i.e., much less than the probability of a hardware error on a computer performing the test)." -- Do you know, if the source of this claim is known and if it stand on solid grounds? -- Shouldn't at least Bleichenbacher's result and possibly also that claim (if it does stand on solid grounds) be included in the article? [[User:Gulliveig|Gulliveig]] ([[User talk:Gulliveig|talk]]) 07:22, 21 June 2009 (UTC)

::::::: The MathWorld comment is solid but not relevant here -- it's talking about the BPSW test, not just a Rabin-Miller. Bleichenbacher's results could be included, perhaps along with Feitsma's -- but it may be better to wait for better sourcing, I'm not sure.  [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 00:33, 22 June 2009 (UTC)

== Some imprecise (wrong) formulations ? ==
After reading the article I have the suspicion that some of the formulations are very
imprecise (or plain wrong :-)):

"Strong Witness": If I understand this correctly, it means that we found a number <math> x </math>
for which the following equations hold:
:<math>
x \equiv a^{2^r\cdot d} \pmod{n}</math> for some <math>0 \le r \le s-1
</math>
:<math>
x \not\equiv -1\pmod{n}
</math>
:<math>
x \not\equiv  1\pmod{n}
</math>
:<math>
x^2 \equiv 1 \pmod{n}
</math>

To sum up: <math> x </math> is a non-trivial square-root of <math> 1 \pmod{n} </math>

Are there any non-trivial square roots of 1, if <math> n </math> is a prime ?
If there are not, then I assume that "Strong Witness" would be better called "Sure Witness" for the
compositeness of <math> n </math>. Fruther then at the beginning
"Let n be an odd prime, ...  Then, one of the following must be true for some a" it should be
"...  Then, one of the following must be true for EVERY a ..."

Is the above correct ?

[[User:213.70.137.66|213.70.137.66]] 17:49, 14 February 2006 (UTC)
:You're right that there aren't non-trivial square roots of 1 mod prime ''p''. If x<sup>2</sup> = 1 (mod ''p''), then (x-1)(x+1) = 0 (mod ''p''). If x is neither 1 nor -1 mod p, neither x-1 or x+1 is zero mod p, which means we have a nontrivial factorization of ''p'', which is of course impossible. This is how we can claim that taking square roots repeatedly will either always yield 1 or eventually yield -1. In fact, as the pseudocode shows, any failure of the conditions proves compositeness. I've modified the article to read ''witness'' of compositeness rather than ''strong witness''. You're also correct that it should say "for all a"; it is for composite numbers that it is only true for some a. [[User:Deco|Deco]] 18:24, 14 February 2006 (UTC)
::I've added the lemma about non-trivial square roots of 1 to the page. It's fairly obvious, but it doesn't hurt to spell out everything. [[User:Deco|Deco]] 18:53, 14 February 2006 (UTC)

The phrase "Except for powers of 3 (see page 1393 of [3]), every odd composite n has at least one witness a." it is confuse and it has to be rephrased. Powers of 3 have nothing to do here. This in fact is trivially true: all odd composites have witnesses, at least two (not only one!), including the Carmichael numbers, and *especially* the powers of 3: they ONLY have witnesses (no liars!). One third of the numbers lower then a power of 3 give a zero (the one being 0 mod 3) and the other two thirds are witnesses, ex: n=9, b=3,6: b^8=0 (mod 9);  b=2,7: b^8=4 (mod 9);  b=4,5: b^8=7 (mod 9); for n=27, b^26 (mod 27) is zero for 3,6,9,12,15,18,21,24, it is 13 for 2 and 25, it is 7 for 4 and 23, etc. Powers of 3 have no LIARS. All the other odd composites have at least two liars (if L is a liar, then -L is one, too).  <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:LaurV|LaurV]] ([[User talk:LaurV|talk]] • [[Special:Contributions/LaurV|contribs]]) 03:22, 30 May 2013 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

== Deterministic variants of the test ==

82.6.98.77, the result has been published in a respectable peer-reviewed journal, and as it is referenced by several other sources, it seems to be accepted by the community. If you disagree with the result, you cannot just slap a "this is wrong" notice, you have to bring forth convincing evidence. -- [[User:EJ|EJ]] 20:18, 27 April 2006 (UTC)

Counter example:
Take n=7. So n-1 = 6 and s=1,d=3 since 2^1.3 = 6. The article claims it's enough to check a=2,7 and 61. Try a=7. The test described in "deterministic variants" section then says n is composite. -- XYZ, June 8 2006

Could it be that only a in the range 1...(n-1) should be tested? If so, it's not clear from the page. -- XYZ, June 8 20006.

Yes, only a in the interval [1,n-1] should be checked. -- [[User:EJ|EJ]] 19:17, 8 June 2006 (UTC)
:Yeah, sorry for my stupid comment. EJ is correct, ''a'' must always be smaller than ''n''. In fact, we specify that <math>a\in \left(\mathbb{Z}/n\mathbb{Z}\right)^*</math>, which excludes the possibility that <math>a = 0 (mod n)</math>. I assume the result of Jaeschke takes this into account - not to say this doesn't deserve clarification. [[User:Deco|Deco]] 19:28, 8 June 2006 (UTC)

Following the deterministic algorithm i found some exception: 49=2^4*3+1 s=4, d=3; if a=18, (18^3) mod 49 = 1 -> 49 prime. Like 49 there is also 121, 289. [[User:Kaluppollo|Kaluppollo]] ([[User talk:Kaluppollo|talk]]) 21:15, 6 July 2009 (UTC)

:: Im not so sure. As I understand it 'a' CAN be larger than 'n'. A result of True indicating primeness is still valid, albeit probabilistic. But a False result no longer indicates compositeness. Rather, it indicates the possibility of either compositeness OR non-coprimality. If you're going to choose an 'a' larger than 'n' (and there's no practical reason why you would) then you must first check that 'a' is coprime to 'n'.  If 'a' is not coprime to 'n' but smaller than 'n' youre still going to get a false result, but because a<n in this case you know n cannot be prime. You dont have that assurance if n<a. Can someone verify this logic? [[Special:Contributions/134.204.1.226|134.204.1.226]] ([[User talk:134.204.1.226|talk]]) 19:43, 27 February 2025 (UTC)

:Why on earth do you test it only for ''a'' = 18? There are several deterministic variants of the test mentioned in the article, and none of the involves 18. The algorithm described by the pseudocode requires you to test all values of ''a'' from 2 to 2(ln 49)<sup>2</sup> ≈ 30, the Pomerance, Selfridge and Wagstaff result tells you to test ''a'' = 2 and ''a'' = 3. Either way, 49 is declared composite, because it fails the test already for ''a'' = 2. —&nbsp;[[User:EmilJ|Emil]]&nbsp;[[User talk:EmilJ|J.]] 10:31, 7 July 2009 (UTC)

::I test it for all ''a'' from 2 to 30. With ''a''=2, a^3=8 which is not congruent 1 nor -1 mod 49, 2^(2^1*3) mod 49 ≠ -1, 2^(2^2*3) mod 49 ≠ -1, 2^(2^3*3) mod 49 ≠ -1, so it not fail the test and it is a possible composite. If i continue testing with bigger ''a'', when i reach ''a''=18, the if statement is False, so the algorithm won't return composite. Thanks for the attention [[User:Kaluppollo|Kaluppollo]] ([[User talk:Kaluppollo|talk]]) 14:10, 7 July 2009 (UTC)

:::You misunderstand the algorithm. Since 2<sup>2<sup>3</sup>·3</sup> mod 49 ≠ ±1, the algorithm returns "composite" and stops, you do not continue with any further testing. —&nbsp;[[User:EmilJ|Emil]]&nbsp;[[User talk:EmilJ|J.]] 14:22, 7 July 2009 (UTC)

::::sorry, you are right, i misanderstood it. thanks for the help [[User:Kaluppollo|Kaluppollo]] ([[User talk:Kaluppollo|talk]]) 21:47, 7 July 2009 (UTC)

:I see, that this is resolved. However, for future reference: some of the provided links tell you step-by-step what has to be calculated (and why) for any given number, e.g.: [http://herbert.gandraxa.com/herbert/mrp.asp]. [[User:Gulliveig|Gulliveig]] ([[User talk:Gulliveig|talk]]) 04:27, 11 September 2009 (UTC)

Actually, I'm having some trouble with the pseudocode myself.  - bogus walkthrough subsequently deleted -  
It seems to correctly classify all odd 1<n<41 (or at least a software implementation according to my understanding of the pseudocode does).   What am I misunderstanding to make me think the pseudocode yields composite for 41 ?  --[[Special:Contributions/83.104.46.24|83.104.46.24]] ([[User talk:83.104.46.24|talk]]) 14:15, 3 February 2010 (UTC)

:What you apparently misread is the condition for returning composite, which involves <math>a^{2^r \cdot d} \,{\color{red}\not\equiv}\,{-}1 \pmod{n}</math>. Is it true that <math>a^{2^r \cdot d} \not\equiv-1 \pmod{n}</math> for every <math>r\in[0,2]</math>? No, it is not, specifically it is false for ''r'' = 1, because its negation, <math>a^{2^r \cdot d} \,{\color{Red}\equiv}\,{-}1 \pmod{n}</math>, is true for this ''r''. —&nbsp;[[User:EmilJ|Emil]]&nbsp;[[User talk:EmilJ|J.]] 14:47, 3 February 2010 (UTC)

::Thanks Emil.  Yes my walkthrough was completely and utterly bogus.  Funnily enough it turns out I'd managed to implement it right in software, but the real reason it was failing on n=41 was because of arithmetic overflow:  once it gets up to testing a=11, r=2, <math>a^{2^r \cdot d} \pmod{n}</math> is 38 if naively calculated using 64-bit finite precision arithmetic.  Using arbitrary precision arithmetic or a "modpow" to keep the range under control fixes the issue and correctly computes 40, avoiding a "composite" result.  I hadn't appreciated just how quickly that double exponentiation blows up!  --[[Special:Contributions/83.104.46.24|83.104.46.24]] ([[User talk:83.104.46.24|talk]]) 00:25, 4 February 2010 (UTC)

Consider the following base sets. <br>

If the number is less than 109838431 it is sufficient to use {73, 1354284263} <br>
If the number is less than 25987132627 it is sufficient to use {2, 5, 11917567} <br>
If the number is less than 1726021172851 it is sufficient to use {2, 2161, 6719, 9001} <br>
If the number is less than 200412882870661 it is sufficient to use {2, 2161, 2333, 4643, 6491} <br>

It is not too difficult to verify the above results. I just don't know if you guys would consider these to be significantly better than the sets that are listed in the main article.   <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/67.198.189.174|67.198.189.174]] ([[User talk:67.198.189.174#top|talk]]) 13:29, 18 June 2017 (UTC)</small> <!--Autosigned by SineBot-->

: The sets at http://miller-rabin.appspot.com/ are even better, and there is a rather obscure reference to that site in the text.  The base sets highlighted in the article are of historical interest and have been published in journals.  It is a little unfortunate that the more practically useful sets are not clearly pointed out. [[User:DAJ NT|DAJ NT]] ([[User talk:DAJ NT|talk]]) 06:33, 19 June 2017 (UTC)

: The sets you mention use large composite numbers as a base set.  I decided to do an exhaustive search restricting the values of the base set to prime numbers. I don't know for sure that restricting them to prime numbers is important.  Heuristically speaking, adding two additional values to the base set seems to increase the smallest pseudoprime of the set by x100.  (200412882870661 is about 100 times greater than 1726021172851).  Given this, there might exist a set of 7 prime numbers that are sufficient to test all numbers less than 2^64. <br> Also, except for the first few, the base sets I list use small numbers (i.e. numbers less than 10000).  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/59.120.231.199|59.120.231.199]] ([[User talk:59.120.231.199#top|talk]]) 08:44, 19 June 2017 (UTC)</small> <!--Autosigned by SineBot-->

: I recently found a way to test any 32 bit integer (more specifically, an integer less than 4957839253) which certainly includes any 32 bit integer) using only two witnesses in the test.   Specifically <br><br>
if (num % 16 == 1) and num < 9758525617 use {5, 1013} <br> 
if (num % 16 == 3) and num < 46493311411 use {2, 29} <br>
if (num % 16 == 5) and num < 4957839253 use {149, 443} <br>
if (num % 16 == 7) and num < 14856014167 use {2, 163} <br>
if (num % 16 == 9) and num < 5671240489 use {5, 647} <br>
if (num % 16 == 11) and num < 8749965451 use {2, 37} <br>
if (num % 16 == 13) and num < 9174782189 use {19, 149} <br>
if (num % 16 == 15) and num < 20574244687 use {2, 53} <br>
Fortunately, (num % 16) can easily be computed using a bit shift operation.<br>
This also beats the two witness base sets mentioned at http://miller-rabin.appspot.com/  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/59.120.231.199|59.120.231.199]] ([[User talk:59.120.231.199#top|talk]]) 09:38, 22 June 2017 (UTC)</small> <!--Autosigned by SineBot-->

:: I do not think that is correct. For instance, <math>1181 \times 3541 = 4181921 \equiv 1 \pmod{16}</math>; however, that number is a strong pseudoprime for both 5 and 1013 bases. [[User:Anton Lapounov|Anton Lapounov]] ([[User talk:Anton Lapounov|talk]]) 00:25, 15 February 2022 (UTC)
:As for coding, I think you will find that num & 0b1111 == b is a more efficient operation than num % 16 == b. [[Special:Contributions/134.204.1.226|134.204.1.226]] ([[User talk:134.204.1.226|talk]]) 19:59, 27 February 2025 (UTC)

==Strength==
I added the word in bold: "The Miller-Rabin test is strictly stronger than the Solovay-Strassen primality test in the sense the set of strong liars of the Miller-Rabin test is a '''proper''' subset of the set of the Solovay-Strassen primality test."

It was removed, which is fine with me.  (It was actually changed to "(often proper)", which seems overly pedantic to me, but that's beside the point.)  Thinking of the set of all {M-R, S-S} liars grouped by base the inclusion is proper; thinking of a particular base the result isn't proper (but is still inclusion).

However, it we're not going to call the subset proper, we shouldn't use the term "strictly stronger"; it should be stronger.  I propose one of the two wordings below (differences bolded):

:"The Miller-Rabin test is '''strictly stronger''' than the Solovay-Strassen primality test in the sense the set of strong liars of the Miller-Rabin test is a '''proper subset''' of the set of the Solovay-Strassen primality test."
:"The Miller-Rabin test is '''stronger''' than the Solovay-Strassen primality test in the sense the set of strong liars of the Miller-Rabin test is a '''subset''' of the set of the Solovay-Strassen primality test."

If there's no feedback, I'm going to make one of these changes in a few days. [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|talk]] • [[Special:Contributions/CRGreathouse|contribs]])</small> 17:01, 5 August 2006 (UTC)

:The M-R test is an algorithm, which gets an integer ''n'' and a randomly chosen integer ''a'', and tries to use the latter to determine the compositeness of the former. It is strictly stronger than S-S because it is correct whenever S-S is correct, and moreover, there are ''n'' and ''a'' for which S-S is incorrect, but M-R is correct.

:The "set of strong liars", on the other hand, has no absolute meaning. It only makes sense if we fix ''n'', albeit implicitly (as in the offending sentence, in the current version and all versions you proposed). For some ''n'' it is a proper subset of Euler liars, for some ''n'' it equals the set of Euler liars. We cannot call it proper without further qualification, because that would read as "for every ''n'', the set of strong liars is a proper subset of Euler liars", which is false.

:IMO both the original wording and the current wording are OK, in the sense that they are not incorrect, and anyone who understands the concepts will figure out what it exactly means. I disagree with your suggestions, because the first one is incorrect, and the second one fails to mention that M-R is strictly stronger than S-S, which is the whole point of the sentence. If you insist on changing the formulation, the proper way would be

::"The Miller-Rabin test is strictly stronger than the Solovay-Strassen primality test in the sense that for every composite ''n'', the set of strong liars for ''n'' is a subset of the set of Euler liars for ''n'', and for many ''n'', the subset is proper."

: but I think that this is too verbose. -- [[User:EJ|EJ]] 18:48, 5 August 2006 (UTC)
::I think that's fine actually and not too verbose. [[User:Deco|Deco]] 01:43, 6 August 2006 (UTC)

:::OK. CRGreathouse apparently does not object, so I'll put that in. -- [[User:EJ|EJ]] 19:42, 13 August 2006 (UTC)

==Broken Algorithm?==
We know 5 is a prime. So s=2, d=1 and n=5. Let's suppose a=4 (it's in the range 1-4) and r=1, since the case r=0 supports the primality. Then we have (1) 4^1 mod 5 = 4, so it is != 1

(2) 4^(2^1 *1) mod 5 = 1, so it is != -1 or 4.
Therefore, 5 isn't a prime? <small>—The preceding [[Wikipedia:Signatures|unsigned]] comment was added by [[User:84.159.42.147|84.159.42.147]] ([[User talk:84.159.42.147|talk]] • [[Special:Contributions/84.159.42.147|contribs]]) 23:34, 14 July 2007 (UTC{{{3|}}})</small>

:[[For all]] ''r'' means for ''both'' ''r'' = 0 ''and'' ''r'' = 1. As you say, taking ''r'' = 0 already "supports the primality", hence whatever happens with ''r'' = 1 is irrelevant. -- [[User:EJ|EJ]] 08:40, 15 July 2007 (UTC)

Fixed the algorithm.  Check Stinson's "Cryptography Theory and Practice" [http://books.google.com/books?id=Yz55lPEuzckC&pg=PA186&lpg=PA186&dq=miller+rabin+stinson&source=bl&ots=qr150e1W6b&sig=A27ZdYE_kdw9BWp-91AXohjTpbY&hl=en&ei=QfoESr_7F9jJtgehw_34Bg&sa=X&oi=book_result&ct=result&resnum=1]  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/72.226.196.71|72.226.196.71]] ([[User talk:72.226.196.71|talk]]) 03:37, 9 May 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

This algorithm is referenced a lot by rosettacode.org but using many of the examples it says that 31 is a composite number. [[Special:Contributions/203.18.108.226|203.18.108.226]] ([[User talk:203.18.108.226|talk]]) 06:09, 11 March 2016 (UTC)

: The code example on RosettaCode did not properly implement the pseudocode.  The current pseudocode is similar to Cohen Algorithm 8.2.2.  It is similar to Crandall and Pomerance Algorithm 3.5.2 with a difference being the base from 2 to n-2 and the input > 3.  [[User:DAJ NT|DAJ NT]] ([[User talk:DAJ NT|talk]]) 17:36, 11 March 2016 (UTC)

== Generating coprime a ==

In an edit summary, [[User:EJ]] said: "The algorithm takes a in full Z/nZ (save the obvious exception a=0), because there is no simple way of generating a's coprime to n."

He's correct that the algorithm as it's normally formulated does not restrict ''a'' to a value coprime to ''n'', but I think there is a simple way of generating such ''a'': generate a random ''a'', test GCD with ''n'', and if it exceeds 1 return COMPOSITE, else continue. This isn't needed for correctness though, and provided the value ''n'' has (as is typical) been prescreened for small divisors, the chance of hitting a value sharing factors with ''n'' is so small as to make this not a useful optimization. [[User:Dcoetzee|Dcoetzee]] 19:57, 5 November 2007 (UTC)

:You're right that my edit summary was misleading. The actual reason why the algorithm does not restrict ''a'' to values coprime to ''n'' is that it is a pointless complication: the other ''a'' are all compositeness witnesses anyway (they do not need to be explicitly tested for, as the condition <math>a^{n-1}=1\pmod n</math> implies that ''a'' is coprime to ''n''), and in fact, provide a factorization of ''n''. And, as you say, they are too rare to make worrying about them worthwhile (which is, after all, one of the reasons why factoring is conjectured to be hard). -- [[User:EJ|EJ]] 10:44, 6 November 2007 (UTC)

::To make the last sentence less confusing: what I was trying to point out was that taking gcd with random numbers is a rather inefficient way of finding factors, it is better to try small divisors in order (if there is a realistic chance that ''n'' might have small factors at all). Anyway, forget about factoring, it's irrelevant to Rabin-Miller. -- [[User:EJ|EJ]] 11:32, 7 November 2007 (UTC)

:::Yup. [[User:Dcoetzee|Dcoetzee]] 11:36, 7 November 2007 (UTC)

:Correct me if Im wrong, but like the Fermat test, a non-coprime 'a' will fail the test anyway, so there is no point in checking for coprimality. As long as 'a' is less than 'n' then any 'a' indicating compositeness is truthfully doing so, regardless if it is coprime or not.  Im not entirely sure what the purpose of such a check would be. Even if it could be done with minimal effort, its hardly an optimization at all. Is this not so or am I missing something? [[Special:Contributions/134.204.1.226|134.204.1.226]] ([[User talk:134.204.1.226|talk]]) 19:19, 22 April 2024 (UTC)
::You are right, this is what both [[User:Dcoetzee]] and [[User:EJ]] said in that (old) discussion. [[User:Maëlan|Maëlan]] 13:47, 27 April 2024 (UTC)

== Haskell code ==

Why Haskell implementation of the algorithm was removed? It's not true that given pseudocode is sufficient to directly write efficient code on a computer language. And removed Haskell code was not straightforward translation of the pseudocode either. So, I think, we must return Haskell sample or write another pseudocode, better suited for an implementation.  <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/87.255.1.40|87.255.1.40]] ([[User talk:87.255.1.40|talk]]) 17:06, 10 April 2008 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

:[[WP:NOT#REPOSITORY|Wikipedia is not a source code repository]]. The article is supposed to ''describe'' the algorithm so that the reader can understand why it works, it is ''not'' supposed to give optimized implementations ready for copy&amp;paste. Furthermore, what is or is not efficient heavily depends on the language used, as well as other circumstances (typical size and structure of input data, hardware parameters, etc.) Thus anybody wishing to write an efficient implementation would still have to do it on his/her own, not by copying a random Haskell implementation, especially since he/she is likely to use a completely different language. Finally, the Wikipedia [[WP:V|verifiability]] policy applies to this situation as usual: unless you can supply a reference to published [[WP:RS|reliable source]], your Haskell implementation counts as [[WP:OR|original research]], which is not permitted on WP. You know, why should we take your word on the correctness or efficiency of your code?

:If you are just looking for a public place where to post your code, I'm sure you'll be able to find a plenty of internet sites suitable for that purpose. Wikipedia is not one of them. — [[User:EJ|EJ]] ([[User talk:EJ|talk]]) 14:48, 14 April 2008 (UTC)

== Thank you ==

Excellent article, really. Thank you.

[[User:Antonind|Antonind]] ([[User talk:Antonind|talk]]) 16:50, 6 November 2008 (UTC)


==Notes==
{{reflist|1}}

== Random range in algorithm ==

The pseudocode in [[Miller–Rabin primality test#Algorithm and running time]] says:
 '''Input''': ''n'' > 2, an odd integer to be tested for primality; ''k'', a parameter that determines the accuracy of the test
 ...
    pick ''a'' randomly in the range [2, ''n'' − 2]
But if ''n'' = 3, then the range is [2, 3-2] = [2, 1] = ∅, and so no such ''a'' can be chosen. Is the range incorrect, or is the initial restriction actually ''n'' > 3, or have I missed something else? --[[Special:Contributions/67.249.56.101|67.249.56.101]] ([[User talk:67.249.56.101|talk]]) 01:38, 31 July 2009 (UTC)

:It's really a very bad idea to use a complicated randomized algorithm for testing small integers like 3, any realistic implementation will first use trial division to rule out small prime factors, thus the problem does not occur. As for the theory, the natural analysis of the algorithm works for ''a'' randomly uniformly chosen in <math>(\mathbb Z/n\mathbb Z)^*</math>. Since there is no good way of doing this directly, the next approximation is to choose it uniformly in [1, ''n'' − 1]; since all numbers in this interval which are not coprime to ''n'' will happen to be witnesses of compositeness anyway, this can only improve the success probability. Now, the version [2, ''n'' − 2] which was used in the article is just a trivial optimization, since 1 and −1 (i.e., ''n'' − 1) are never compositeness witnesses, hence it is pointless to test them. Thus, the impossibility of choosing ''a'' in [2, ''n'' − 2] for ''n'' = 3 should be understood as that there are no compositeness witnesses, hence 3 is prime. I'll change it to [2, ''n'' − 1] so that people do not wonder. —&nbsp;[[User:EmilJ|Emil]]&nbsp;[[User talk:EmilJ|J.]] 10:47, 6 August 2009 (UTC)

:: I think a better change would be to make it "input: n > 3". [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 17:08, 6 August 2009 (UTC)

== Algorithm complexity ==

There is written: 

Using [[modular exponentiation]] by repeated squaring, the running time of
this algorithm is [[Big O notation|O]](''k'' &times; log<sup>3</sup>&nbsp;''n'').


Shouldn't it be
[[Big O notation|O]](''k'' &times; ''s'' &times; log<sup>3</sup>&nbsp;''n'') ? [[User:Julekmen|julekmen]] ([[User talk:Julekmen|talk]]) 11:16, 1 October 2009 (UTC)

:No, ''s'' is accounted for by one of those log ''n'' factors. —&nbsp;[[User:EmilJ|Emil]]&nbsp;[[User talk:EmilJ|J.]] 11:54, 1 October 2009 (UTC)

It should be O(k log<sup>2</sup>) not O(k log<sup>3</sup>). a<sup>d</sup> can be calculated in O(log<sup>2</sup> d) by modular exponentiation.  Since n-1 = 2<sup>s</sup>d, s = O(log n). The line <code>x = x<sup>2</sup> mod p</code> only involves 2 multiplications and 1 mod. So the total is O(k (log<sup>2</sup> d + 3s)) = O(k log<sup>2</sup> n). [[User:Angry bee|Angry bee]] ([[User talk:Angry bee|talk]]) 15:29, 26 March 2012 (UTC)
: Please enlighten us how modular exponentiation of log(n)-bit numbers can be done in O(log^2 n) time. I thought O(log^2 n) is the time needed to perform a single multiplication (using the trivial algorithm, nothing fancy like FFT), and then there's another O(log n) factor for repeated squaring. -- [[User:X7q|X7q]] ([[User talk:X7q|talk]]) 02:22, 30 March 2012 (UTC)

Now that integer multiplication in `O(nlog(n))` time has been proven (https://hal.archives-ouvertes.fr/hal-02070778/document), do these runtimes change?  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/130.44.167.24|130.44.167.24]] ([[User talk:130.44.167.24#top|talk]]) 04:50, 22 December 2021 (UTC)</small> <!--Autosigned by SineBot-->

== New bounds for the deterministic variant? ==

"For example, Pomerance, Selfridge and Wagstaff and Jaeschke have verified that [...] if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17." - Did someone since extend this range with more potential witnesses (19, ...)? [[User:Gulliveig|Gulliveig]] ([[User talk:Gulliveig|talk]]) 05:01, 2 August 2011 (UTC)

: Yes, there have been several extensions -- including one I did several years ago.  But I don't know of any that have been published in peer-reviewed sources. [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 13:28, 2 August 2011 (UTC)

== misleading ==

"However, as a caution, note that Arnault  <ref name="Arnault397Digit">{{cite journal|title=Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases |journal=Journal of Symbolic Computation|year=1995|month=August|volume=20|issue=2|pages=151–161 |author=F. Arnault |url=http://www.sciencedirect.com/science/article/pii/S0747717185710425}}</ref> gives a 397-digit composite number that would pass a Miller–Rabin test for every base ''a'' less than 307. One way to reduce the chance that such a number will be declared probably prime is to combine a Miller–Rabin test with another type of test; this is what the [[Baillie–PSW primality test]] does."

I believe this promotes a misunderstanding of the type of probabilistic algorithm the MR test is.  For ANY number, the probability of it incorrectly stating that a number is prime decays exponentially with the number of trials.  As long as one is comfortable with probabilities on the order of 1/10^100 of an error (or even smaller, if you want to run it for longer), the test is completely fine.  For all practical purposes, it will never incorrectly determine the primality of a number, when run with hundreds of iterations.

The result of Arnault was a number for which no small bases worked to disprove primality.  But it is still true for this number (like all composite numbers) that most randomly chosen bases would work to disprove primality.  Their number failed the Maple primality test because of a weakness with the Maple implementation: it checked just the bases 2,3,5,7,11 instead of choosing random bases to test.

I have reworked this paragraph as a result.[[User:Wpegden|Wpegden]] ([[User talk:Wpegden|talk]]) 14:56, 10 October 2013 (UTC)

: I like the change.  I think this concept is important to keep on the page, because there is still a lot of software being written today (2013) that uses the first N bases instead of random bases, and most people seem to not see the difference.  The usual "solution" I've seen is people just raise the number of tests to silly numbers to weasel out of counterexamples, rather than using a BPSW test. [[Special:Contributions/76.115.142.133|76.115.142.133]] ([[User talk:76.115.142.133|talk]]) 04:07, 14 October 2013 (UTC)

* From this perspective, the result of Arnault is similar to the those of Pomerance—Selfridge—Wagstaff and Jaeschke, mentioned in section ''Deterministic variants of the test''. In particular, they give the number 2,152,302,898,747 as one that passes Miller–Rabin primality test for bases 2, 3, 5, 7, and 11 and thus should also pass Maple primality test. I therefore think that Arnault, Pomerance—Selfridge—Wagstaff, and Jaeschke results should be mentioned in the same place/context — I would suggest moving mention of Arnault to ''Deterministic variants of the test'' section. [[User:Maxal|Maxal]] ([[User talk:Maxal|talk]]) 14:09, 14 October 2013 (UTC)

{{reflist-talk}}

== Incorrect logic under Concepts ==

{{quotation|Now, let n be prime with n > 2. It follows that n − 1 is even and we can write it as 2<sup>s</sup>·d, where s and d are positive integers (d is odd).}}

Isn't this true for ''all odd'' n > 2? If n is odd then n - 1 is even. As n - 1 is even, it is divisible by some power of two, the greatest one determines both s and d. [[User:NickGarvey|Nick Garvey]] ([[User talk:NickGarvey|talk]]) 22:33, 7 December 2013 (UTC)

:Yes, that part is true for all odd n > 2. Why do you call that incorrect logic? [[User:PrimeHunter|PrimeHunter]] ([[User talk:PrimeHunter|talk]]) 22:58, 7 December 2013 (UTC)

::Ah I misread the part that came after. Sorry, my mistake. [[User:NickGarvey|Nick Garvey]] ([[User talk:NickGarvey|talk]]) 23:07, 7 December 2013 (UTC)

== Pseudocode underspecified ==

The pseudocode includes the line:

    repeat s − 1 times:

However, s may be zero, in which case that line reads "repeat -1 times". It is reasonable to interpret that as "repeat zero times", but the ambiguity may be confusing.

Indeed, I discovered this problem by translating the pseudocode into a formal specification, then trying to prove an implementation of that spec correct. The spec demanded at least 's' witness squares, but when s==0, there is still one witness to either primality or non-primality. I understand that the pseudocode's job is not to be a formal reference, but my experience indicates that the ambiguity indeed has the potential to confuse readers. Even one reader with an advanced degree in computer science. :)

The line might be rewritten as one of:

    repeat at least s-1 times:
    repeat max(0,s-1) times:
    repeat s-1 times (or none if s==0):

The first variant is least disruptive to the pseudocode, but doesn't do much to hint at why the qualifier is present. The last variant's parenthetical comment clearly explains its own presence, but is unpleasantly distracting. I don't have a strong preference, but I'm enthusiastic about correcting the problem of -1 loops.
[[Special:Contributions/76.104.130.32|76.104.130.32]] ([[User talk:76.104.130.32|talk]]) 06:05, 14 March 2014 (UTC)jonh

:But n is odd so n-1=2<sup>s</sup>·d is even with d odd. Hence s is at least 1.  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/193.144.198.250|193.144.198.250]] ([[User talk:193.144.198.250|talk]]) 12:30, 17 March 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

Oh. So it is. That's awkward. :v) Please disregard this comment.  [[Special:Contributions/131.107.174.36|131.107.174.36]] ([[User talk:131.107.174.36|talk]]) 21:14, 17 March 2014 (UTC)jonh

== Use of Logarithm in in the Miller Algorithm ==

I assume that the "deterministic variant" is the Miller test. The pseudocode uses ln, as in "natural logarithm" to set a bound. In computer science matters, I usually assume log<sub>2</sub>. Shouldn't it be log<sub>2</sub> instead? Is this a convention thing or a genuine difference?<br>
Note that "log" appearing within Big-O-Notation doesn't care about the base of the logarithm, because converting to another base is just multiplying by a constant.  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/176.199.27.52|176.199.27.52]] ([[User talk:176.199.27.52|talk]]) 14:41, 22 June 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

== About the test "if x = 1 then return composite" in the algorithm ==

Hi all,
I'm surprised to see that test in the loop. Where does it come from ? That test does not seem to be stated in the text written above.
[[User:RBossut|RBossut]] ([[User talk:RBossut|talk]]) 13:01, 24 April 2015 (UTC)
: It is not in Crandall and Pomerance Alg 3.5.2.  It is in Cohen (Course in CANT) Algorithm 8.2.2.  In Riesel 1994, it is not part of the definition 4.3, but is included in his program.  It isn't necessary, just practical as repeated squaring of 1 will not change the result, so can be considered an early exit condition.  Cohen structures his loop so this is clearer (repeat r-1 times while x != ± 1). [[User:DAJ NT|DAJ NT]] ([[User talk:DAJ NT|talk]]) 18:15, 12 November 2016 (UTC)

== Least strong pseudoprime to base n table ==

I think the page would be improved if this were either removed or pushed to the end.  It is quite large and breaks up the flow from example to algorithm.  My personal feeling is that it adds no value, and at best we should just point to MathWorld's Strong Pseudoprime page and give a quick list of the first few.  Lastly, base 1 doesn't make sense (or if you think it does, why 9 and not 1 or 4 as pseudoprimes?).  [[User:DAJ NT|DAJ NT]] ([[User talk:DAJ NT|talk]]) 07:09, 23 May 2015 (UTC)

== Is 341 prime? ==

Suppose n  - 1 = 4k where k is odd and for some t, t ^ k = 32 mod n. Can we infer that n is composite? Not, surely, until we have checked that 1024 (i.e. 32 X 32) is not congruent to -1 mod n.

[[User:Bukovets|Bukovets]] ([[User talk:Bukovets|talk]]) 10:00, 11 June 2017 (UTC)

: {{ping|Bukovets}} Yeah, I asked myself the same question. It turns out this example was taken directly from the given source<ref name="baillie">{{cite journal|title=Lucas Pseudoprimes|journal=Mathematics of Computation|date=October 1980|volume=35|issue=152|pages=1391–1417|url=http://mpqs.free.fr/LucasPseudoprimes.pdf|author=Robert Baillie|author2=[[Samuel S. Wagstaff, Jr.]]| mr=583518| doi=10.1090/S0025-5718-1980-0583518-6 }}</ref>{{rp|1402}} with some context stripped. In that paper, the GCD of 32−1 and 341 is computed unconditionally, so we know that we get a non‐trivial factor of 341 because we observe this GCD to be neither 1 nor 341. That was not clear in the present article because the algorithm used was not made explicit. I rewrote that part recently, and added the missing step to the example (check that 32<sup>2</sup> mod 341 = 1). — [[User:Maëlan|Maëlan]] 17:08, 19 February 2019 (UTC)
{{reflist-talk}}

== Pseudocode unnecessary check ==

In the pseudocode we have:
 WitnessLoop: repeat k times:
    ...
    repeat r − 1 times:
       ...
       if x = 1 then
          return composite
       ...

But x could never become 1 and so the check is unnecessary and misleading. If x is 1 than either its initial value was 1 or its previous value was -1 (n-1). In either case the algorithm would have terminated.  <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Perchema|Perchema]] ([[User talk:Perchema#top|talk]] • [[Special:Contributions/Perchema|contribs]]) 10:30, 3 May 2018 (UTC)</small> <!--Autosigned by SineBot-->

: {{ping|Perchema}} Beware that you are assuming 1 and −1 to be the only square roots modulo ''n'' of 1. This is true when ''n'' is prime, but may be false when ''n'' is composite (for example 4<sup>2</sup> mod 15 = 1).
: That said, you are right in saying that this test is unnecessary, as if ''x'' becomes 1 at some point, then it will remain 1 until the end of the inner loop, hence will never be −1, and the algorithm will return “''composite''” nonetheless. So, as is, this test is only a way of short‐circuiting the inner loop, which is not necessary to get the right complexity, and probably does not save anything in practice (as ''r'', the number of iterations of the inner loop, should be very small most of the time).
: However, that additional test becomes helpful for finding factors of ''n''. See the section “Variants for finding factors” which I rewrote recently.
: — [[User:Maëlan|Maëlan]] 16:57, 19 February 2019 (UTC)

== Numbers for which the Miller-Rabin test fails ==

The factor database website <ref>{{Cite web |url=http://factordb.com/prooffailed.php |title=These numbers passed Miller-Rabin's probabilistic test (order 10 at least), but turned out to be composite |last=Tervooren |first=Markus |website=Factor Database |access-date=September 8, 2020 }}</ref> lists 728,134 composite numbers for which at least ten applications of the Miller-Rabin test failed to detect compositeness. The bases used in the tests were chosen by the '''mpz_probab_prime_p( )''' function in the [[GNU Multiple Precision Arithmetic Library]].

The list of numbers can be viewed and downloaded from <ref>{{Cite web |url=http://factordb.com/downloads/prooffailed.txt |title=prooffailed.txt |last=Tervooren |first=Markus |website=Factor Database |access-date=September 8, 2020 }}</ref>.

A short calculation shows that none of these 728,134 numbers is a [[Lucas pseudoprime]] when Selfridge's "Method A" is used to choose Lucas parameters <math>D</math>, <math>P</math>, and <math>Q</math>. Therefore, the [[Baillie-PSW primality test]] would correctly declare that all of these numbers are composite. [[User:MathPerson|MathPerson]] ([[User talk:MathPerson|talk]]) 22:43, 8 September 2020 (UTC)

:Software implementation is not sufficient proof of an algorithm failing, as anyone can write erroneous mathematical code and indeed most do. In the case of mpz_probab_prime_p the selection process is not the same as described by the probabilistic Miller-Rabin  variant, therefore the results are irrelevant, and reading the source code would have told Tervooren that. [[User:JSory|JSory]] ([[User talk:JSory|talk]]) 22:39, 16 November 2022 (UTC)
{{reflist-talk}}

== Reducing values of 'a' to primes ==
Can 'a' be restricted to only the primes?  All of the deterministic "below a certain threshold" variants involve checks against only primes.  If 'a' needs to be coprime to the test number then why not just use prime 'a'?  Every explanation of the Miller-Rabin test I see online tells me to pull an 'a' from a range [2, n-1] and Im wondering if I just pull primes, am I setting myself up for failure?  Can a composite smaller than 'n' catch something that a prime smaller than 'n' cant?  I realize Im putting the cart before the horse here because you need to know primes already in order to test for them, so maybe thats why its worded the way it is, but assuming you already know the primes up to a certain point, why not check them only? That is what the deterministic variants are doing, after all.  If you were pulling randomly generated 'a' from a very large range [2,n-2], and perform the test 'k' times, then I could understand why you wouldnt do only primes. But barring the pragmatic side of the algorithm, what is the mathematical basis for using composites? Is there one or should we ideally be using only primes?  Nothing explicit is said about this. [[Special:Contributions/134.204.1.226|134.204.1.226]] ([[User talk:134.204.1.226|talk]]) 16:35, 13 December 2021 (UTC)

: The base ''a'' does not need to be coprime to the test number ''n''. In fact, if ''a'' happens to have a common divisor with ''n'', it will be a witness for the compositeness of ''n'', because <math>a^{n-1} \equiv 1 \pmod{n}</math> cannot be true. That means you will not need to test any further bases. Moreover, composite bases work a little better in practice. If you look at [https://miller-rabin.appspot.com/ the best known SPRP bases sets], all bases there are composite, except for 2. And the base 2 is used only because we have calculated a huge table of strong pseudoprimes for that base, which allows us to limit testing other bases to that precalculated list only. [[User:Anton Lapounov|Anton Lapounov]] ([[User talk:Anton Lapounov|talk]]) 23:52, 14 February 2022 (UTC)
::"Weak" pseudoprimes rather, however Feitsma & Galway's list can be trivially reduced to strong 2-pseudoprimes. [[User:JSory|JSory]] ([[User talk:JSory|talk]]) 22:41, 16 November 2022 (UTC)

== Pseudocode incorrect? ==

In both the deterministic and non-deterministic pseudocode, there is a check of ''if y ≠ 1 then return “composite”'' after the loop over values of ''s''.  However, this doesn't make sense, as y may never be defined (take the case n=4; you will never enter the s-loop).  I believe the check might be intended to be ''if x != 1'' instead?  <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Apnorton|Apnorton]] ([[User talk:Apnorton#top|talk]] • [[Special:Contributions/Apnorton|contribs]]) 19:49, 29 May 2023 (UTC)</small> <!--Autosigned by SineBot-->

: ''n'' is odd, so ''s'' must be > 0. But the code doesn't seem to implement the test as described above. It may be equivalent, but then it is at least a very inefficient variant if you don't use it to squeeze a factor out of it. --[[Special:Contributions/109.43.50.204|109.43.50.204]] ([[User talk:109.43.50.204|talk]]) 00:52, 18 December 2023 (UTC)
: But does it even make sense to search for a factor in an already known strong probable prime? It may have one if it's not an actual prime, but the article raises more questions than it gives answers. --[[Special:Contributions/109.43.50.204|109.43.50.204]] ([[User talk:109.43.50.204|talk]]) 01:44, 18 December 2023 (UTC)

:: If it is known to be a probable prime, then I don't think it makes sense to search for a factor.  However, if you don't know that, I think it is best to check for some small factors first.  [[User:Bubba73|Bubba73]] <sup>[[User talk:Bubba73|You talkin' to me?]]</sup> 02:08, 18 December 2023 (UTC)

::: The article says that you know it if ''x'' == 1. The pseudocode tests for this condition, but continues the loop. <strike>And if ''x'' == 1 then ''y'' will also be 1 and the pseudocode returns the wrong result anyways.</strike> --[[Special:Contributions/109.43.51.138|109.43.51.138]] ([[User talk:109.43.51.138|talk]]) 12:57, 18 December 2023 (UTC)
::::At this point in the pseudocode, ''x'' is equal to ''y'', because ''x'' is given the value of ''y'' at the end of each iteration of the inner loop, and there is always at least one iteration because ''s'' > 0 (''n'' is odd). So testing x ≠ 1 is the same as testing y ≠ 1.
::::FYI the pseudocodes have been substantially rewritten one year ago. Here is [https://en.wikipedia.org/w/index.php?title=Miller%E2%80%93Rabin_primality_test&oldid=1119698523 the old version] (mine) and here is [https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test the new version] ({{ping|Maggyero}}). I don’t have brain time to check thoroughly for the correctness of the new code, but it is clearly ''not'' equivalent to the old. The old version is a direct translation of the mathematical definition of “strong probable prime” given in the article, and it aborts the inner loop (repeated squaring) as soon as ''x'' becomes −1. The new version continues the loop in that situation, uselessly, and does redundant tests. IMHO the old version is preferable for both these reasons: clarity ''and'' efficiency (it has a bit of ugly unstructured programming, but that can be remedied). [[User:Maëlan|Maëlan]] 14:45, 18 December 2023 (UTC)

::::: Yes, I'd suggest to restore the old version. --[[Special:Contributions/109.43.51.138|109.43.51.138]] ([[User talk:109.43.51.138|talk]]) 15:52, 18 December 2023 (UTC)
:::::: "continue WitnessLoop" goes back to the top of that loop, right?  [[User:Bubba73|Bubba73]] <sup>[[User talk:Bubba73|You talkin' to me?]]</sup> 16:33, 18 December 2023 (UTC)
:::::::Yes, for the next iteration (draw another random ''a''). We can try to avoid it by turning '''repeat s−1 times''' into something along the lines of '''repeat s−1 times while x ≠ n−1''', and putting the '''return “composite”''' under a conditional test. [[User:Maëlan|Maëlan]] 16:40, 18 December 2023 (UTC)

To clarify what I mean: here is my old code (with style slightly updated):

 '''Input #1''': ''n'' > 3, an odd integer to be tested for primality
 '''Input #2''': ''k'', the number of rounds of testing to perform
 '''Output''': “''composite''” if ''n'' is found to be composite, “''probably prime''” otherwise
 
 '''let''' ''s'' > 0 and ''d'' odd > 0 such that ''n'' − 1 = 2<sup>''s''</sup>·''d''  <u># by factoring out powers of 2 from ''n'' − 1</u>
 WitnessLoop:
 '''repeat''' ''k'' '''times''':
     ''a'' ← random integer in the range [2, ''n'' − 2]
     ''x'' ← ''a<sup>d</sup>'' mod ''n''
     '''if''' ''x'' = 1 or ''x'' = ''n'' − 1 '''then'''
         '''continue''' WitnessLoop
     '''repeat''' ''s'' − 1 '''times''':
         ''x'' ← ''x''<sup>2</sup> mod ''n''
         '''if''' ''x'' = ''n'' − 1 '''then'''
             '''continue''' WitnessLoop
     '''return''' “''composite''”
 '''return''' “''probably prime''”

Here is the proposed rewriting that avoids this ugly <code>continue WitnessLoop</code>:

 '''let''' ''s'' > 0 and ''d'' odd > 0 such that ''n'' − 1 = 2<sup>''s''</sup>·''d''  <u># by factoring out powers of 2 from ''n'' − 1</u>
 '''repeat''' ''k'' '''times''':
     ''a'' ← random integer in the range [2, ''n'' − 2]
     ''x'' ← ''a<sup>d</sup>'' mod ''n''
     '''if''' ''x'' ≠ 1 and ''x'' ≠ ''n'' − 1 '''then'''  <u># the second conjunct can be removed (redundant with the tests below it)</u>
         ''i'' ← 0
         '''while''' ''i'' < ''s'' − 1 and ''x'' ≠ ''n'' − 1:  <u># repeat squaring ''n''−1 times, or until ''x'' becomes −1</u>
             ''x'' ← ''x''<sup>2</sup> mod ''n''
             ''i'' ← ''i'' + 1
         '''if''' ''x'' ≠ ''n'' − 1:
             '''return''' “''composite''”
 '''return''' “''probably prime''”

I realize I’ve spoken a bit too quickly: my code short-circuits the inner loop if ''x'' becomes −1, but it continues it if ''x'' becomes +1. Maggyero’s code does the opposite optimization. If deemed useful, it is possible to integrate both shortcuts in my code, by adding a test for <code>''x'' ≠ 1</code> inside the while loop. In other words:

 '''let''' ''s'' > 0 and ''d'' odd > 0 such that ''n'' − 1 = 2<sup>''s''</sup>·''d''  <u># by factoring out powers of 2 from ''n'' − 1</u>
 '''repeat''' ''k'' '''times''':
     ''a'' ← random integer in the range [2, ''n'' − 2]
     ''x'' ← ''a<sup>d</sup>'' mod ''n''
     '''if''' ''x'' ≠ 1 and ''x'' ≠ ''n'' − 1 '''then'''  <u># the second conjunct can be removed (redundant with the tests below it)</u>
         ''i'' ← 0
         '''while''' ''i'' < ''s'' − 1 and ''x'' ≠ ''n'' − 1:  <u># repeat squaring ''n''−1 times, or until ''x'' becomes −1</u>
             ''x'' ← ''x''<sup>2</sup> mod ''n''
             ''i'' ← ''i'' + 1
             '''if''' x = 1:  <u># correct but unnecessary shortcut</u>
                 '''return''' “''composite''”
         '''if''' ''x'' ≠ ''n'' − 1:
             '''return''' “''composite''”
 '''return''' “''probably prime''”

This shortcut is done in the variant of the pseudo-code that tries to find factors (because it’s in this situation that we are able to compute a factor), but I’m not sure whether it brings much to the general case (the shortcut does not trigger often, I think). [[User:Maëlan|Maëlan]] 17:24, 18 December 2023 (UTC)

: To me, pseudocode is clearer if it says "if these conditions are met, do the following" than "if these conditions are not met, continue the loop".   [[User:Bubba73|Bubba73]] <sup>[[User talk:Bubba73|You talkin' to me?]]</sup> 20:02, 18 December 2023 (UTC)

: The first version is much clearer. If the ''continue'' is really too ugly, a function would be better than these complex conditions. --[[Special:Contributions/109.43.51.138|109.43.51.138]] ([[User talk:109.43.51.138|talk]]) 00:03, 19 December 2023 (UTC)

:: My preference is to not use "continue", but do what you think is best.  I avoid using "continue" in programming.  If the rest of the loop is relatively short, I use a conditional on it.  However, if I'm skipping over a large amount of the loop (say the last 30 lines), then I will use "continue".  [[User:Bubba73|Bubba73]] <sup>[[User talk:Bubba73|You talkin' to me?]]</sup> 01:28, 19 December 2023 (UTC)
::: In actual code I would use a function indeed, and it does make a lot of sense to isolate the MR-test-with-fixed-''a'' into its own function. IMHO it’s the clearest option. We just have to settle on a pseudo-syntax for it, and accept the extra verbosity. For instance :

 '''function''' ''is_strong_probable_prime'':
 
     '''Input #1''': ''s'' > 0 and ''d'' odd > 0 (describing the odd integer ''n'' = 2<sup>''s''</sup>·''d'' + 1)
     '''Input #2''': ''a'', the base
     '''Output''': True if ''n'' is a strong probable prime to base ''a'', False otherwise
 
     ''x'' ← ''a<sup>d</sup>'' mod ''n''
     '''if''' ''x'' = 1 or ''x'' = ''n'' − 1 '''then'''
         '''return''' True
     '''repeat''' ''s'' − 1 '''times''':
         ''x'' ← ''x''<sup>2</sup> mod ''n''
         '''if''' ''x'' = ''n'' − 1 '''then'''
             '''return''' True
         '''if''' x = 1:  <u># correct but unnecessary shortcut</u>
             '''return''' False
     '''return''' False

 '''function''' ''miller_rabin_test'':
 
     '''Input #1''': ''n'' > 3, an odd integer to be tested for primality
     '''Input #2''': ''k'', the number of rounds of testing to perform
     '''Output''': “''composite''” if ''n'' is found to be composite, “''probably prime''” otherwise
 
     '''let''' ''s'' > 0 and ''d'' odd > 0 such that ''n'' − 1 = 2<sup>''s''</sup>·''d''  <u># by factoring out powers of 2 from ''n'' − 1</u>
     '''repeat''' ''k'' '''times''':
         ''a'' ← random integer in the range [2, ''n'' − 2]
         '''if''' not(''is_strong_probable_prime''(''s'', ''d'', ''a'')):
             '''return''' “''composite''”
     '''return''' “''probably prime''”

What do you think? [[User:Maëlan|Maëlan]] 01:07, 21 December 2023 (UTC)

:One downside is that, in the variant that finds factors, we’d have to thread the richer return type down to the auxiliary function, but well. [[User:Maëlan|Maëlan]] 01:12, 21 December 2023 (UTC)

== Prime base 'a' ==
Point of inquiry.  I have always thought, beginning with Fermat primality test, that arbitrary base 'a' was an inefficiency.  Can someone correct me? Is it sufficient to test only bases that are prime?  In the section of this article for testing against small subsets, for test numbers 'n' beneath a certain limit, the base 'a' sets always comprise prime numbers.  If a base of 2 and a base of 3 are both inconclusive, does a base of 6 provide any more meaningful information? Or would testing it be redundant? If 6 is indeed redundant to testing both 2 and 3 separately, why not just test against some large primorial number? 

[[Special:Contributions/134.204.1.226|134.204.1.226]] ([[User talk:134.204.1.226|talk]])  <!--Template:Undated--><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|undated]] comment added 19:24, 22 April 2024 (UTC)</small> <!--Autosigned by SineBot-->

: it doesn't work; a number can be a strong pseudoprime to base b but not to base kb. For example, 703 is a strong pseudoprime to base 3 but not to base 15. - [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 13:22, 26 April 2024 (UTC)
::Agreed. But why not just test prime bases then? Why is it listed that the bases to test below n=2^64 should contain composites? Much less composites that share the same prime factors? Can a composite provide more information than its prime factors?  You made my point, I think, CRGreathouse. If base of 3 indicates primality but 15 is a witness to compositeness, then why not just test the larger composite 15=3*5? Why not even larger primorials?  Im looking for a more efficient way of choosing bases and Im asking myself why these particular bases are indicated, whether or not the prime factors of the bases generate redundant information? Perhaps a base of 15=3*5 and a base of 14=2*7 is more valuable to us to use than 2,3,5,7 separately? [[Special:Contributions/134.204.1.226|134.204.1.226]] ([[User talk:134.204.1.226|talk]]) 19:32, 27 February 2025 (UTC)

== determinsitic variants ==
Under Deterministic variants -> Miller Test, I quote "Assuming the truth of the extended Riemann hypothesis (ERH), it is known that the group is generated by its elements smaller than O((ln n)2)".  Is it fair to say then that if we tested all base values up to n/4, we have a deterministic test without assuming the ERH?  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/134.204.1.226|134.204.1.226]] ([[User talk:134.204.1.226#top|talk]]) 19:22, 27 February 2025 (UTC)</small> <!--Autosigned by SineBot-->
: I don't know offhand what the best unconditional bounds are, but I'm sure n/4 would work for n > 6. But the resulting algorithm is dramatically slower than trial division. - [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 20:00, 3 March 2025 (UTC)