2826:
1869:
1568:
2430:
1660:
2821:{\displaystyle {\begin{aligned}\Pr(\lnot P\mid M\!R_{k})&={\frac {\Pr(\lnot P\land M\!R_{k})}{\Pr(\lnot P\land M\!R_{k})+\Pr(P\land M\!R_{k})}}\\&={\frac {1}{1+{\frac {\Pr(M\!R_{k}\mid P)}{\Pr(M\!R_{k}\mid \lnot P)}}{\frac {\Pr(P)}{\Pr(\lnot P)}}}}\\&={\frac {1}{1+{\frac {1}{\Pr(M\!R_{k}\mid \lnot P)}}{\frac {\Pr(P)}{1-\Pr(P)}}}}\end{aligned}}}
1359:
4959:
1864:{\displaystyle {\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &137^{{2^{0}}55}{\text{ mod }}221\equiv 137^{55}\equiv 188{\text{. Since }}188\neq 1{\text{ and }}188\neq n-1{\text{, we continue.}}\\&137^{{2^{1}}55}{\text{ mod }}221\equiv 137^{110}\equiv 205\neq n-1\end{aligned}}}
1563:{\displaystyle {\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &174^{{2^{0}}55}{\text{ mod }}221\equiv 174^{55}\equiv 47{\text{. Since }}47\neq 1{\text{ and }}47\neq n-1{\text{, we continue.}}\\&174^{{2^{1}}55}{\text{ mod }}221\equiv 174^{110}\equiv 220=n-1\end{aligned}}}
4065:
In order to find factors more often, the same ideas can also be applied to the square roots of −1 (or any other number). This strategy can be implemented by exploiting knowledge from previous rounds of the Miller–Rabin test. In those rounds we may have identified a square root modulo
4752:
4443:
2963:
685:
However, a pre-selected set of a few small bases guarantees the identification of all composites up to a pre-computed maximum. This maximum is generally quite large compared to the bases. This gives very fast deterministic tests for small enough
4659:
588:
to an arbitrarily small rate, by combining the outcome of as many independently chosen bases as necessary to achieve the said rate. This is the Miller–Rabin test. There seems to be diminishing returns in trying many bases, because if
5157:
4561:
3768:). Hence, if factoring is a goal, these gcd calculations can be inserted into the algorithm at little additional computational cost. This leads to the following pseudocode, where the added or changed code is highlighted:
3559:
Other criteria of this sort, often more efficient (fewer bases required) than those shown above, exist. They give very fast deterministic primality tests for numbers in the appropriate range, without any assumptions.
553:). However no simple way of finding a witness is known. A naïve solution is to try all possible bases, which yields an inefficient deterministic algorithm. The Miller test is a more efficient variant of this (see
1123:
1873:
Hence 137 is a witness for the compositeness of 221, and 174 was in fact a strong liar. Note that this tells us nothing about the factors of 221 (which are 13 and 17). However, the example with 341 in
864:
95:
Similarly to the Fermat and
Solovay–Strassen tests, the Miller–Rabin primality test checks whether a specific property, which is known to hold for prime values, holds for the number under testing.
2435:
1665:
1364:
1225:
1019:
281:
4954:{\displaystyle \Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\left({\tfrac {1}{\Pr(P)}}-1\right)\leq 4^{-k}\left({\tfrac {\ln 2}{2}}b-1+{\mathcal {O}}\left(b^{-1}\right)\right).}
4298:
1607:
5019:
465:
6592:
3019:
2418:
2350:
3571:‐bit numbers). However, no finite set of bases is sufficient for all composite numbers. Alford, Granville, and Pomerance have shown that there exist infinitely many composite numbers
217:
1265:
549:
Thankfully, no composite number is a strong pseudoprime to all bases at the same time (contrary to the Fermat primality test for which Fermat pseudoprimes to all bases exist: the
335:
4317:
2845:
1323:
384:
2972:
of the input number. In the general case, as said earlier, this distribution is controlled by a cryptographic adversary, thus unknown, so we cannot deduce much about
4744:
3353:
which give results that do not rely on unproven assumptions. For theoretical purposes requiring a deterministic polynomial time algorithm, it was superseded by the
1653:
1352:
1178:
5211:
For instance, in 1995, Arnault gives a 397-digit composite number for which all bases less than 307 are strong liars; this number was reported to be prime by the
6596:
4567:
4157:
The Miller–Rabin test can be used to generate strong probable primes, simply by drawing integers at random until one passes the test. This algorithm terminates
3380:
is not necessary, as much smaller sets of potential witnesses are known to suffice. For example, Pomerance, Selfridge, Wagstaff and
Jaeschke have verified that
1627:
1285:
4307:
As any prime number passes the test, the probability of being prime gives a coarse lower bound to the probability of passing the test. If we draw odd integers
2226:, whose worst‐case error bound is 2. Moreover, the Miller–Rabin test is strictly stronger than the Solovay–Strassen test in the sense that for every composite
6104:
5077:
2831:
In the last equation, we simplified the expression using the fact that all prime numbers are correctly reported as strong probable primes (the test has no
4470:
6137:
3346:
6072:
5859:"Sequence A014233 (Smallest odd number for which Miller–Rabin primality test on bases <= n-th prime does not reveal compositeness)"
2420:: the probability that a number which has been declared as a strong probable prime is in fact composite. These two probabilities are related by
5235:, composite numbers that these libraries declared prime, thus demonstrating that they were not implemented with an adversarial context in mind.
2253:, the probability for a composite number to be declared probably prime is often significantly smaller than 4. For instance, for most numbers
1889:
3312:
The full power of the generalized
Riemann hypothesis is not needed to ensure the correctness of the test: as we deal with subgroups of even
3065:
of the input. To improve the running time, the challenge is then to lower the limit as much as possible while keeping the test reliable.
65:
deterministic primality test. Its probabilistic variant remains widely used in practice, as one of the simplest and fastest tests known.
2175:
The error made by the primality test is measured by the probability that a composite number is declared probably prime. The more bases
2968:
Hence this conditional probability is related not only to the error measure discussed above — which is bounded by 4 — but also to the
675:, choosing bases at random is essential, as we don't know the distribution of witnesses and strong liars among the numbers 2, 3, ...,
6461:
6097:
5864:
3497:
1027:
5998:
6329:
3345:
gives sufficient confidence while running much faster. It is also slower in practice than commonly used proof methods such as
1141:. At the end, either one of the terms is congruent to −1, or all of them are congruent to 1, and in particular the last term,
5934:
5502:
17:
1125:
is a square root of the previous term. Since the first term is congruent to 1, the second term is a square root of 1 modulo
778:
6271:
6090:
3327:
2154:
6200:
5590:
4054:
is a pseudoprime base 2, but not a strong pseudoprime base 2. By computing a gcd at this stage, we find a factor of 341:
2223:
55:
6377:
3341:
The Miller test is not used in practice. For most purposes, proper use of the probabilistic Miller–Rabin test or the
2289:
adversary might send a carefully chosen pseudoprime in order to defeat the primality test. In such contexts, only the
390:
For each value of r, the value of the expression may be calculated using the value obtained for the previous value of
5464:
761:
1183:
962:
224:
6324:
6286:
6261:
6175:
5327:
Artjuhov, M. M. (1966–1967), "Certain criteria for primality of numbers connected with the little Fermat theorem",
5258:
3597:
2296:
The above error measure is the probability for a composite number to be declared as a strong probable prime after
6466:
6357:
6276:
6266:
6168:
4252:
1575:
4971:
415:
6294:
6142:
3342:
2975:
2374:
2306:
173:
6547:
4308:
6542:
6509:
6471:
6372:
1230:
6067:
4438:{\displaystyle \Pr(M\!R_{k})>\Pr(P)={\frac {\pi \left(2^{b}\right)-\pi \left(2^{b-1}\right)}{2^{b-2}}}}
4241:
is infinite, since the outer loop may never terminate, but that happens with probability zero. As per the
3532:
Sorenson and
Webster verify the above and calculate precise results for these larger than 64‐bit results:
6423:
3495:
Using the work of
Feitsma and Galway enumerating all base 2 pseudoprimes in 2010, this was extended (see
3119:
2958:{\displaystyle \Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\left({\tfrac {1}{\Pr(P)}}-1\right)}
76:
5227:
For instance, in 2018, Albrecht et al. were able to construct, for many cryptographic libraries such as
297:
6588:
6578:
6537:
6313:
6307:
6281:
6152:
6077:
6047:
2357:
2105:
409:
6573:
6514:
3114:)*, one of them must lie outside the said subgroup, hence must be a witness for the compositeness of
3100:
1908:
determines the accuracy of the test. The greater the number of rounds, the more accurate the result.
1290:
340:
6652:
6476:
6349:
6195:
6147:
5024:
Using the fact that the Miller–Rabin test itself often has an error bound much smaller than 4 (see
4161:(since at each iteration there is a chance to draw a prime number). The pseudocode for generating
3350:
2969:
2282:
565:
4664:
Hence we can expect the generator to run no more Miller–Rabin tests than a number proportional to
619:
6491:
5579:
5218:
function, because it implemented the Miller–Rabin test with the specific bases 2, 3, 5, 7 and 11.
4449:
3618:
2301:
2136:
72:
68:
6382:
6657:
6602:
6552:
6532:
5950:
5364:
4242:
2132:
1138:
5794:"Finding primes & proving primality — 2.3: Strong probable-primality and a practical test"
593:
is a pseudoprime to some base, then it seems more likely to be a pseudoprime to another base.
6612:
6253:
6228:
6157:
5818:
Zhang, Zhenxiang & Tang, Min (2003), "Finding strong pseudoprimes to several bases. II",
4238:
3995:
508:
51:
4720:
6607:
6499:
6481:
6456:
6418:
6162:
6013:
5983:
5827:
5755:
5736:
Sorenson, Jonathan; Webster, Jonathan (2015). "Strong
Pseudoprimes to Twelve Prime Bases".
5624:
5580:
Martin R. Albrecht; Jake
Massimo; Kenneth G. Paterson; Juraj Somorovsky (15 October 2018).
5547:
5444:
5340:
4710:
The error measure of this generator is the probability that it outputs a composite number.
4654:{\displaystyle {\tfrac {1}{\Pr(P)}}={\tfrac {\ln 2}{2}}b+{\mathcal {O}}\left(b^{-1}\right)}
4457:
4453:
1632:
1331:
1157:
757:
84:
8:
6617:
6583:
6504:
6408:
6367:
6362:
6339:
6243:
3320:
3313:
2131:
is the number of rounds performed; thus this is an efficient, polynomial-time algorithm.
1130:
753:
475:
6017:
5913:
5831:
5759:
5628:
5551:
5487:
6448:
6395:
6392:
6233:
6182:
6132:
5901:
5771:
5745:
5718:
5678:
5642:
5563:
5532:
5368:
5278:
3354:
1612:
1270:
529:
164:
6189:
6061:
5974:
5392:
5355:
3042:
The Miller–Rabin algorithm can be made deterministic by trying all possible values of
3029:), the distribution is chosen by the generator itself, so we can exploit this result.
725:, always yield 1. It remains to show that there are no other square roots of 1 modulo
6568:
6524:
6238:
6215:
6044:
5930:
5498:
5460:
5360:
5314:
5152:{\displaystyle \left({\frac {1}{7}}b^{\frac {15}{4}}2^{-{\frac {b}{2}}}\right)4^{-k}}
3125:
886:
550:
5921:, Lecture Notes in Computer Science, vol. 877, Springer-Verlag, pp. 1–16,
5722:
5713:
5696:
5282:
3563:
There is a small list of potential witnesses for every possible input size (at most
1137:. If it is congruent to −1, we are done. Otherwise, it is congruent to 1 and we can
6413:
6021:
5969:
5922:
5905:
5835:
5775:
5763:
5708:
5668:
5632:
5594:
5555:
5440:
5420:
5387:
5310:
5298:
5270:
5212:
5040:
derived several error bounds for the generator, with various classes of parameters
141:
80:
6026:
5840:
4556:{\displaystyle \Pr(P)={\tfrac {2}{\ln 2}}b^{-1}+{\mathcal {O}}\left(b^{-3}\right)}
6403:
6302:
5979:
5336:
3317:
62:
5520:
5409:"Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases"
5063:≥ 51, while Ronald Burthe Jr. completed the proof with the remaining values 2 ≤
5029:
3505:), with the first result later shown using different methods in Jiang and Deng:
6433:
6334:
6319:
6223:
6124:
5909:
5589:. ACM SIGSAC Conference on Computer and Communications Security 2018. Toronto:
5528:
5524:
5452:
5356:
5037:
5033:
4668:. Taking into account the worst-case complexity of each Miller–Rabin test (see
4246:
3134:
2832:
2371:
rounds. We are often interested instead in the inverse conditional probability
2110:
585:
487:
155:
47:
39:
6082:
6078:
Miller–Rabin primality test in JavaScript using arbitrary precision arithmetic
5483:
1609:, either 221 is prime, or 174 is a strong liar for 221. We try another random
6646:
6428:
6113:
6042:
5926:
5793:
4158:
3058:
trials, hence the running time would be exponential with respect to the size
2421:
519:
However, this property is not an exact characterization of prime numbers. If
5954:
5598:
3122:(ERH), it is known that the group is generated by its elements smaller than
6438:
5495:
Algorithmic Number Theory: Lattices, Number Fields, Curves and
Cryptography
5425:
5408:
5194:
The Miller–Rabin test is often incorrectly said to have been discovered by
4746:(shown just before), this error measure can be given a coarse upper bound:
3621:
calculations into the above algorithm, we can sometimes obtain a factor of
2286:
2261:
which invalidate this upper bound vanishes as we consider larger values of
737:
5274:
4169:
strong probable primes (with the most significant bit set) is as follows:
2269:
case has a much better accuracy than 4, a fact which can be exploited for
5854:
2836:
5767:
3141:. This leads to the following primality testing algorithm, known as the
2179:
are tried, the better the accuracy of the test. It can be shown that if
5682:
5646:
5581:
5567:
5448:
2235:
1901:
730:
5615:(1990), "Explicit bounds for primality testing and related problems",
6116:
6052:
5948:
5659:
Jaeschke, Gerhard (1993), "On strong pseudoprimes to several bases",
5612:
3138:
43:
5673:
5637:
5559:
2277:). However, such improved error bounds should not be relied upon to
523:
is composite, it may nonetheless be a strong probable prime to base
5880:
5750:
5583:
Prime and
Prejudice: Primality Testing Under Adversarial Conditions
5067:≤ 50). Again this simple bound can be improved for large values of
3081:
4713:
Using the relation between conditional probabilities (shown in an
3133:, which was already noted by Miller. The constant involved in the
5533:"Average case error estimates for the strong probable prime test"
5232:
5228:
5198:
as soon as 1967; a reading of
Artjuhov's paper (particularly his
5048:. These error bounds allow an implementor to choose a reasonable
564:
Another solution is to pick a base at random. This yields a fast
572:
is composite, most bases are witnesses, so the test will detect
1877:
shows how these calculations can sometimes produce a factor of
760:
than its degree (this theorem follows from the existence of an
6062:
Interactive Online Implementation of the Deterministic Variant
5202:) shows that he actually discovered the Solovay–Strassen test.
5071:. For instance, another bound derived by the same authors is:
3998:
algorithm because it is only able to find factors for numbers
2257:, this probability is bounded by 8; the proportion of numbers
5515:
5513:
5459:(3rd ed.). MIT Press and McGraw-Hill. pp. 968–971.
3551:< 3,317,044,064,679,887,385,961,981, it is enough to test
312:
71:
discovered the test in 1976. Miller's version of the test is
5999:"Further investigations with the strong probable prime test"
3021:. However, in the case when we use the Miller–Rabin test to
923:
is an odd prime, then it is a strong probable prime to base
5912:(1994), "On the difficulty of finding reliable witnesses",
5881:"Deterministic variants of the Miller–Rabin primality test"
5858:
3540:< 318,665,857,834,031,151,167,461, it is enough to test
3501:
1118:{\displaystyle a^{2^{s}d},a^{2^{s-1}d},\dots ,a^{2d},a^{d}}
132:
is an odd positive integer. Let’s consider an integer
5510:
5439:
4672:), the expected running time of the generator with inputs
3524:< 18,446,744,073,709,551,616 = 2, it is enough to test
404:
is an odd prime, it passes the test because of two facts:
5301:(1980), "Probabilistic algorithm for testing primality",
4166:
3583:. They also argue heuristically that the smallest number
5900:
5519:
5261:(1976), "Riemann's Hypothesis and Tests for Primality",
956:
is an odd positive integer, by Fermat's little theorem:
691:
6633:
indicate that algorithm is for numbers of special forms
2367:
is the event that it passes the Miller–Rabin test with
752:, of the more general fact that a polynomial over some
103:
The property is the following. For a given odd integer
5853:
4976:
4884:
4829:
4598:
4572:
4490:
4257:
3360:
2922:
859:{\displaystyle (x-1)(x+1)=x^{2}-1\equiv 0{\pmod {n}}.}
764:). Here follows a more elementary proof. Suppose that
5080:
4974:
4755:
4723:
4570:
4473:
4320:
4255:
3555:= 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41.
3513:< 3,825,123,056,546,413,051, it is enough to test
2978:
2848:
2433:
2377:
2309:
1663:
1635:
1615:
1578:
1362:
1334:
1293:
1273:
1233:
1186:
1160:
1030:
965:
781:
576:
as composite with a reasonably high probability (see
418:
343:
300:
227:
176:
61:
It is of historical significance in the search for a
5697:"Strong pseudoprimes to the first eight prime bases"
5055:
One of these error bounds is 4, which holds for all
3357:, which also does not rely on unproven assumptions.
2300:
rounds of testing; in mathematical words, it is the
710:is a prime, then the only square roots of 1 modulo
5151:
5013:
4953:
4738:
4653:
4555:
4437:
4292:
4020:). For other numbers, the algorithm only returns “
3778:> 2, an odd integer to be tested for primality
3752:are nontrivial (not necessarily prime) factors of
3155:> 2, an odd integer to be tested for primality
3013:
2957:
2820:
2412:
2344:
1918:> 2, an odd integer to be tested for primality
1863:
1647:
1621:
1601:
1562:
1346:
1317:
1279:
1259:
1219:
1172:
1117:
1013:
858:
467:(this property alone defines the weaker notion of
459:
378:
329:
275:
211:
4800:
4774:
4330:
4272:
3575:whose smallest compositeness witness is at least
3544:= 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37.
3528:= 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37.
2997:
2893:
2867:
2747:
2646:
2615:
2564:
2532:
2498:
2456:
2396:
2319:
2215:iterations of the Miller–Rabin test will declare
1874:
6644:
4835:
4791:
4756:
4724:
4578:
4474:
4347:
4321:
4263:
4152:
3316:, it suffices to assume the validity of GRH for
2979:
2928:
2884:
2849:
2796:
2776:
2738:
2689:
2675:
2637:
2606:
2549:
2514:
2480:
2438:
2378:
2310:
729:. This is a special case, here applied with the
652:is odd, for the same reason. That is why random
6112:
5735:
3612:
3487:< 341,550,071,728,321, it is enough to test
1884:For a practical guide to choosing the value of
5787:
5785:
5400:
1220:{\displaystyle n-1{\text{ as }}2^{2}\times 55}
1014:{\displaystyle a^{2^{s}d}\equiv 1{\pmod {n}}.}
584:). We can quickly reduce the probability of a
276:{\displaystyle a^{2^{r}d}\equiv -1{\pmod {n}}}
6098:
6064:(stepping through the algorithm step-by-step)
5326:
4187:, the number of rounds of testing to perform
3818:is otherwise found to be composite, “
3786:, the number of rounds of testing to perform
3476:< 3,474,749,660,383, it is enough to test
3465:< 2,152,302,898,747, it is enough to test
3454:< 1,122,004,669,633, it is enough to test
3326:The running time of the algorithm is, in the
2219:probably prime with a probability at most 4.
1926:, the number of rounds of testing to perform
75:, but its correctness relies on the unproven
5174:/4. This bound is smaller than 4 as soon as
4460:), we can approximate this probability when
5782:
4293:{\displaystyle {\tfrac {1}{\Pr(M\!R_{k})}}}
3629:is composite. This occurs for example when
3145:, which is deterministic assuming the GRH:
2360:that the number being tested is prime, and
1602:{\displaystyle 220\equiv -1{\text{ mod }}n}
1133:, it is congruent to either 1 or −1 modulo
46:which determines whether a given number is
6105:
6091:
5996:
5406:
5014:{\displaystyle {\tfrac {\ln 2}{2}}4^{-k}b}
460:{\displaystyle a^{n-1}\equiv 1{\pmod {n}}}
6025:
5973:
5865:On-Line Encyclopedia of Integer Sequences
5839:
5817:
5749:
5712:
5694:
5672:
5636:
5424:
5391:
3871:is always a probable prime to base 1 and
3443:< 4,759,123,141, it is enough to test
3432:< 3,215,031,751, it is enough to test
3032:
3014:{\displaystyle \Pr(\lnot P\mid M\!R_{k})}
2413:{\displaystyle \Pr(\lnot P\mid M\!R_{k})}
2345:{\displaystyle \Pr(M\!R_{k}\mid \lnot P)}
1991:is always a probable prime to base 1 and
98:
5658:
5478:
5476:
5253:
5251:
3648:is a nontrivial square root of 1 modulo
3637:but not a strong probable prime to base
2127:is the number tested for primality, and
2108:, the running time of this algorithm is
893:is prime, it divides one of the factors
721:Certainly 1 and −1, when squared modulo
400:The idea beneath this test is that when
212:{\displaystyle a^{d}\equiv 1{\pmod {n}}}
90:
5942:
5293:
5291:
5263:Journal of Computer and System Sciences
3587:such that every composite number below
494:is not a strong probable prime to base
83:modified it to obtain an unconditional
14:
6645:
6048:"Rabin-Miller Strong Pseudoprime Test"
5990:
5482:
5257:
3760:is odd, these factors are coprime and
3591:has a compositeness witness less than
3421:< 25,326,001, it is enough to test
911:is congruent to either 1 or −1 modulo
294:This simplifies to first checking for
6086:
6043:
5878:
5473:
5351:
5349:
5297:
5248:
5021:. However, much better bounds exist.
3932:# nontrivial square root of 1 modulo
3517:= 2, 3, 5, 7, 11, 13, 17, 19, and 23.
3410:< 9,080,191, it is enough to test
3399:< 1,373,653, it is enough to test
3264:# nontrivial square root of 1 modulo
2293:error bound of 4 can be relied upon.
2051:# nontrivial square root of 1 modulo
1260:{\displaystyle s=2{\text{ and }}d=55}
618:, because the congruence relation is
471:, on which the Fermat test is based);
5791:
5695:Jiang, Yupeng; Deng, Yingpu (2014).
5611:
5288:
5059:≥ 2 (the authors only showed it for
4200:True: pick a random odd integer
3843:# by factoring out powers of 2 from
3193:# by factoring out powers of 2 from
3095:)*, which means that if we test all
2835:). By dropping the left part of the
1964:# by factoring out powers of 2 from
1895:
5591:Association for Computing Machinery
5488:"Four primality testing algorithms"
4179:, the number of bits of the result
3625:instead of merely determining that
3361:Testing against small sets of bases
2139:) can decrease the running time to
1890:Testing against small sets of bases
1000:
845:
694:Testing against small sets of bases
656:are usually chosen in the interval
544:
449:
265:
201:
24:
5346:
4968:, this error measure is less than
4917:
4814:
4762:
4625:
4527:
4208:the Miller–Rabin test with inputs
3369:to be tested is small, trying all
3338:(using FFT‐based multiplication).
2985:
2907:
2855:
2839:, we derive a simple upper bound:
2761:
2695:
2660:
2520:
2486:
2444:
2384:
2333:
762:Euclidean division for polynomials
330:{\displaystyle a^{d}{\bmod {n}}=1}
25:
6669:
6314:Special number field sieve (SNFS)
6308:General number field sieve (GNFS)
6073:Miller–Rabin primality test in C#
6036:
5975:10.1090/S0025-5718-1980-0583518-6
5393:10.1090/S0025-5718-1980-0572872-7
4717:) and the asymptotic behavior of
4702:using FFT-based multiplication).
4464:grows towards infinity. We find:
3388:< 2,047, it is enough to test
2249:In addition, for large values of
394:by squaring under the modulus of
2222:This is an improvement over the
1900:The algorithm can be written in
1154:Suppose we wish to determine if
554:
5894:
5872:
5847:
5811:
5729:
5714:10.1090/S0025-5718-2014-02830-5
5688:
5652:
5605:
5573:
5413:Journal of Symbolic Computation
5221:
4669:
4232:
4024:” with no further information.
3072:is composite, the strong liars
3026:
2274:
1318:{\displaystyle 2\leq a\leq n-2}
993:
838:
527:, in which case it is called a
442:
258:
194:
56:Solovay–Strassen primality test
5997:Burthe Jr., Ronald J. (1996),
5497:, Cambridge University Press,
5433:
5320:
5205:
5188:
4844:
4838:
4820:
4794:
4785:
4759:
4733:
4727:
4587:
4581:
4483:
4477:
4356:
4350:
4341:
4324:
4283:
4266:
4089:, we can compare the value of
4002:which are pseudoprime to base
3046:below a certain limit. Taking
3037:
3008:
2982:
2937:
2931:
2913:
2887:
2878:
2852:
2805:
2799:
2785:
2779:
2767:
2741:
2701:
2692:
2684:
2678:
2666:
2640:
2632:
2609:
2575:
2552:
2543:
2517:
2509:
2483:
2467:
2441:
2407:
2381:
2339:
2313:
2230:, the set of strong liars for
1698:
1397:
1267:. We randomly select a number
1004:
994:
849:
839:
809:
797:
794:
782:
671:For testing arbitrarily large
620:compatible with exponentiation
453:
443:
379:{\displaystyle a^{2^{r}d}=n-1}
269:
259:
205:
195:
13:
1:
6027:10.1090/S0025-5718-96-00695-3
5841:10.1090/S0025-5718-03-01545-X
5242:
5025:
4714:
4705:
4301:
4153:Generation of probable primes
4006:(in other words, for numbers
3491:= 2, 3, 5, 7, 11, 13, and 17.
2099:
938:is an odd prime and we write
768:is a square root of 1 modulo
577:
502:is definitely composite, and
6272:Lenstra elliptic curve (ECM)
5315:10.1016/0022-314X(80)90084-0
4311:in the range , then we get:
3633:is a probable prime to base
3613:Variants for finding factors
3118:. Assuming the truth of the
7:
3120:extended Riemann hypothesis
2285:is not controlled, since a
2183:is composite, then at most
2170:
1938:is found to be composite, “
77:extended Riemann hypothesis
36:Rabin–Miller primality test
32:Miller–Rabin primality test
10:
6674:
6579:Exponentiation by squaring
6262:Continued fraction (CFRAC)
6006:Mathematics of Computation
5962:Mathematics of Computation
5855:Sloane, N. J. A.
5820:Mathematics of Computation
5738:Mathematics of Computation
5701:Mathematics of Computation
5661:Mathematics of Computation
5617:Mathematics of Computation
5540:Mathematics of Computation
5457:Introduction to Algorithms
5407:F. Arnault (August 1995).
5380:Mathematics of Computation
4456:of π (an extension of the
4191:: a strong probable prime
4145:are nontrivial factors of
3343:Baillie–PSW primality test
3080:are contained in a proper
2234:is a subset of the set of
2211:is composite then running
1904:as follows. The parameter
1149:
1024:Each term of the sequence
952:is a positive integer and
128:is a positive integer and
6626:
6561:
6523:
6490:
6447:
6391:
6348:
6252:
6214:
6123:
5915:Algorithmic Number Theory
3800:) if a nontrivial factor
3722:From this we deduce that
3480:= 2, 3, 5, 7, 11, and 13;
3458:= 2, 13, 23, and 1662803;
3050:as the limit would imply
919:Here is a proof that, if
706:Here is a proof that, if
701:
512:for the compositeness of
386:for successive values of
5927:10.1007/3-540-58691-1_36
5303:Journal of Number Theory
5181:
5052:for a desired accuracy.
4964:Hence, for large enough
4300:(reusing notations from
2970:probability distribution
2283:probability distribution
2246:, the subset is proper.
469:probable prime to base a
6492:Greatest common divisor
5951:Samuel S. Wagstaff, Jr.
5599:10.1145/3243734.3243787
5365:Samuel S. Wagstaff, Jr.
4450:prime-counting function
4239:worst-case running time
3619:greatest common divisor
2302:conditional probability
2207:. As a consequence, if
2137:Harvey-Hoeven algorithm
2135:-based multiplication (
410:Fermat's little theorem
85:probabilistic algorithm
6603:Modular exponentiation
5426:10.1006/jsco.1995.1042
5153:
5015:
4955:
4740:
4739:{\displaystyle \Pr(P)}
4655:
4557:
4439:
4294:
4243:geometric distribution
4027:For example, consider
3033:Deterministic variants
3015:
2959:
2822:
2414:
2346:
1865:
1649:
1623:
1603:
1564:
1348:
1319:
1281:
1261:
1221:
1174:
1119:
1015:
860:
461:
380:
331:
277:
213:
99:Strong probable primes
6330:Shanks's square forms
6254:Integer factorization
6229:Sieve of Eratosthenes
5879:Izykowski, Wojciech.
5445:Leiserson, Charles E.
5369:"The pseudoprimes to
5275:10.1145/800116.803773
5154:
5016:
4956:
4741:
4656:
4558:
4440:
4295:
4056:gcd(32 − 1, 341) = 31
4050:. This tells us that
3835:odd > 0 such that
3469:= 2, 3, 5, 7, and 11;
3184:odd > 0 such that
3068:If the tested number
3016:
2960:
2823:
2415:
2347:
2273:probable primes (see
2224:Solovay–Strassen test
2203:are strong liars for
1955:odd > 0 such that
1866:
1650:
1648:{\displaystyle a=137}
1629:, this time choosing
1624:
1604:
1565:
1349:
1347:{\displaystyle a=174}
1320:
1282:
1262:
1222:
1175:
1173:{\displaystyle n=221}
1139:iterate the reasoning
1120:
1016:
861:
462:
381:
332:
278:
214:
91:Mathematical concepts
52:Fermat primality test
6608:Montgomery reduction
6482:Function field sieve
6457:Baby-step giant-step
6303:Quadratic sieve (QS)
5955:"Lucas Pseudoprimes"
5593:. pp. 281–298.
5162:which holds for all
5078:
4972:
4753:
4721:
4568:
4471:
4458:prime number theorem
4454:asymptotic expansion
4318:
4253:
3321:Dirichlet characters
3137:was reduced to 2 by
2976:
2846:
2431:
2375:
2307:
1661:
1633:
1613:
1576:
1360:
1332:
1291:
1271:
1231:
1184:
1158:
1028:
963:
873:divides the product
779:
637:holds trivially for
607:holds trivially for
416:
341:
298:
225:
174:
165:congruence relations
6618:Trachtenberg system
6584:Integer square root
6525:Modular square root
6244:Wheel factorization
6196:Quadratic Frobenius
6176:Lucas–Lehmer–Riesel
6018:1996MaCom..65..373B
5832:2003MaCom..72.2085Z
5760:2015arXiv150900864S
5629:1990MaCom..55..355B
5552:1993MaCom..61..177D
4680:is then bounded by
4249:number of draws is
3595:should be of order
1180:is prime. We write
38:is a probabilistic
6510:Extended Euclidean
6449:Discrete logarithm
6378:Schönhage–Strassen
6234:Sieve of Pritchard
6045:Weisstein, Eric W.
5968:(152): 1391–1417.
5868:. OEIS Foundation.
5707:(290): 2915–2924.
5386:(151): 1003–1026.
5149:
5011:
4993:
4951:
4901:
4849:
4736:
4651:
4615:
4592:
4553:
4507:
4435:
4290:
4288:
4204:in the range
3355:AKS primality test
3011:
2955:
2942:
2818:
2816:
2410:
2342:
1861:
1859:
1645:
1619:
1599:
1560:
1558:
1344:
1315:
1277:
1257:
1227:, so that we have
1217:
1170:
1129:. By the previous
1115:
1011:
932:
856:
719:
566:probabilistic test
551:Carmichael numbers
530:strong pseudoprime
457:
376:
327:
273:
209:
48:likely to be prime
6640:
6639:
6239:Sieve of Sundaram
5936:978-3-540-58691-3
5826:(44): 2085–2097,
5792:Caldwell, Chris.
5768:10.1090/mcom/3134
5744:(304): 985–1003.
5504:978-0-521-80854-5
5449:Rivest, Ronald L.
5441:Cormen, Thomas H.
5361:John L. Selfridge
5299:Rabin, Michael O.
5127:
5108:
5094:
4992:
4900:
4848:
4614:
4591:
4506:
4433:
4287:
3436:= 2, 3, 5, and 7;
3099:from a set which
2941:
2812:
2809:
2771:
2708:
2705:
2670:
2579:
2106:repeated squaring
1896:Miller–Rabin test
1821:
1789:
1769:
1755:
1728:
1693:
1622:{\displaystyle a}
1594:
1520:
1488:
1468:
1454:
1427:
1392:
1280:{\displaystyle a}
1246:
1199:
930:
717:
50:, similar to the
18:Miller–Rabin test
16:(Redirected from
6665:
6589:Integer relation
6562:Other algorithms
6467:Pollard kangaroo
6358:Ancient Egyptian
6216:Prime-generating
6201:Solovay–Strassen
6114:Number-theoretic
6107:
6100:
6093:
6084:
6083:
6058:
6057:
6031:
6030:
6029:
6012:(213): 373–381,
6003:
5994:
5988:
5987:
5977:
5959:
5953:(October 1980).
5949:Robert Baillie;
5946:
5940:
5939:
5920:
5898:
5892:
5891:
5889:
5887:
5876:
5870:
5869:
5851:
5845:
5844:
5843:
5815:
5809:
5808:
5806:
5804:
5789:
5780:
5779:
5753:
5733:
5727:
5726:
5716:
5692:
5686:
5685:
5676:
5667:(204): 915–926,
5656:
5650:
5649:
5640:
5623:(191): 355–380,
5609:
5603:
5602:
5588:
5577:
5571:
5570:
5546:(203): 177–194,
5537:
5517:
5508:
5507:
5492:
5480:
5471:
5470:
5437:
5431:
5430:
5428:
5404:
5398:
5397:
5395:
5377:
5372:
5353:
5344:
5343:
5329:Acta Arithmetica
5324:
5318:
5317:
5295:
5286:
5285:
5255:
5236:
5225:
5219:
5217:
5209:
5203:
5201:
5197:
5192:
5158:
5156:
5155:
5150:
5148:
5147:
5135:
5131:
5130:
5129:
5128:
5120:
5110:
5109:
5101:
5095:
5087:
5020:
5018:
5017:
5012:
5007:
5006:
4994:
4988:
4977:
4960:
4958:
4957:
4952:
4947:
4943:
4942:
4938:
4937:
4921:
4920:
4902:
4896:
4885:
4877:
4876:
4861:
4857:
4850:
4847:
4830:
4810:
4809:
4784:
4783:
4745:
4743:
4742:
4737:
4701:
4690:
4660:
4658:
4657:
4652:
4650:
4646:
4645:
4629:
4628:
4616:
4610:
4599:
4593:
4590:
4573:
4562:
4560:
4559:
4554:
4552:
4548:
4547:
4531:
4530:
4521:
4520:
4508:
4505:
4491:
4444:
4442:
4441:
4436:
4434:
4432:
4431:
4416:
4415:
4411:
4410:
4385:
4381:
4380:
4363:
4340:
4339:
4299:
4297:
4296:
4291:
4289:
4286:
4282:
4281:
4258:
4144:
4128:
4088:
4061:
4057:
4049:
4045:
4041:
4019:
3994:a probabilistic
3954:
3809:
3756:(in fact, since
3751:
3736:
3717:
3710:
3704:does not divide
3699:
3685:
3666:
3609:
3582:
3504:
3379:
3365:When the number
3337:
3208:the range :
3132:
3064:
3057:
3020:
3018:
3017:
3012:
3007:
3006:
2964:
2962:
2961:
2956:
2954:
2950:
2943:
2940:
2923:
2903:
2902:
2877:
2876:
2827:
2825:
2824:
2819:
2817:
2813:
2811:
2810:
2808:
2788:
2774:
2772:
2770:
2757:
2756:
2733:
2721:
2713:
2709:
2707:
2706:
2704:
2687:
2673:
2671:
2669:
2656:
2655:
2635:
2625:
2624:
2604:
2592:
2584:
2580:
2578:
2574:
2573:
2542:
2541:
2512:
2508:
2507:
2478:
2466:
2465:
2419:
2417:
2416:
2411:
2406:
2405:
2351:
2349:
2348:
2343:
2329:
2328:
2198:
2196:
2195:
2192:
2189:
2166:
2122:
1870:
1868:
1867:
1862:
1860:
1838:
1837:
1822:
1819:
1817:
1816:
1812:
1811:
1810:
1794:
1790:
1787:
1770:
1767:
1756:
1753:
1745:
1744:
1729:
1726:
1724:
1723:
1719:
1718:
1717:
1694:
1691:
1689:
1688:
1684:
1683:
1682:
1654:
1652:
1651:
1646:
1628:
1626:
1625:
1620:
1608:
1606:
1605:
1600:
1595:
1592:
1569:
1567:
1566:
1561:
1559:
1537:
1536:
1521:
1518:
1516:
1515:
1511:
1510:
1509:
1493:
1489:
1486:
1469:
1466:
1455:
1452:
1444:
1443:
1428:
1425:
1423:
1422:
1418:
1417:
1416:
1393:
1390:
1388:
1387:
1383:
1382:
1381:
1353:
1351:
1350:
1345:
1324:
1322:
1321:
1316:
1286:
1284:
1283:
1278:
1266:
1264:
1263:
1258:
1247:
1244:
1226:
1224:
1223:
1218:
1210:
1209:
1200:
1197:
1179:
1177:
1176:
1171:
1124:
1122:
1121:
1116:
1114:
1113:
1101:
1100:
1079:
1078:
1074:
1073:
1050:
1049:
1045:
1044:
1020:
1018:
1017:
1012:
1007:
985:
984:
980:
979:
947:
906:
899:
884:
869:In other words,
865:
863:
862:
857:
852:
824:
823:
751:
735:
681:
674:
667:
655:
651:
647:
636:
617:
606:
545:Choices of bases
466:
464:
463:
458:
456:
434:
433:
385:
383:
382:
377:
363:
362:
358:
357:
336:
334:
333:
328:
320:
319:
310:
309:
289:
282:
280:
279:
274:
272:
247:
246:
242:
241:
218:
216:
215:
210:
208:
186:
185:
163:if one of these
152:is said to be a
123:
116:
109:
81:Michael O. Rabin
21:
6673:
6672:
6668:
6667:
6666:
6664:
6663:
6662:
6653:Primality tests
6643:
6642:
6641:
6636:
6622:
6557:
6519:
6486:
6443:
6387:
6344:
6248:
6210:
6183:Proth's theorem
6125:Primality tests
6119:
6111:
6068:Applet (German)
6039:
6034:
6001:
5995:
5991:
5957:
5947:
5943:
5937:
5918:
5899:
5895:
5885:
5883:
5877:
5873:
5852:
5848:
5816:
5812:
5802:
5800:
5798:The Prime Pages
5790:
5783:
5734:
5730:
5693:
5689:
5674:10.2307/2153262
5657:
5653:
5638:10.2307/2008811
5610:
5606:
5586:
5578:
5574:
5560:10.2307/2152945
5535:
5518:
5511:
5505:
5490:
5481:
5474:
5467:
5455:(2009) . "31".
5453:Stein, Clifford
5438:
5434:
5405:
5401:
5375:
5370:
5354:
5347:
5325:
5321:
5296:
5289:
5259:Miller, Gary L.
5256:
5249:
5245:
5240:
5239:
5226:
5222:
5215:
5210:
5206:
5199:
5195:
5193:
5189:
5184:
5140:
5136:
5119:
5115:
5111:
5100:
5096:
5086:
5085:
5081:
5079:
5076:
5075:
4999:
4995:
4978:
4975:
4973:
4970:
4969:
4930:
4926:
4922:
4916:
4915:
4886:
4883:
4882:
4878:
4869:
4865:
4834:
4828:
4827:
4823:
4805:
4801:
4779:
4775:
4754:
4751:
4750:
4722:
4719:
4718:
4715:earlier section
4708:
4692:
4681:
4638:
4634:
4630:
4624:
4623:
4600:
4597:
4577:
4571:
4569:
4566:
4565:
4540:
4536:
4532:
4526:
4525:
4513:
4509:
4495:
4489:
4472:
4469:
4468:
4448:where π is the
4421:
4417:
4400:
4396:
4392:
4376:
4372:
4368:
4364:
4362:
4335:
4331:
4319:
4316:
4315:
4277:
4273:
4262:
4256:
4254:
4251:
4250:
4235:
4230:
4195:
4155:
4130:
4114:
4075:
4059:
4055:
4047:
4043:
4036:
4011:
3988:
3937:
3823:
3791:
3738:
3723:
3712:
3705:
3700:, we know that
3690:
3672:
3667:, we know that
3657:
3615:
3596:
3576:
3496:
3447:= 2, 7, and 61;
3370:
3363:
3331:
3310:
3172:
3167:is composite, “
3123:
3059:
3051:
3040:
3035:
3002:
2998:
2977:
2974:
2973:
2927:
2921:
2920:
2916:
2898:
2894:
2872:
2868:
2847:
2844:
2843:
2815:
2814:
2789:
2775:
2773:
2752:
2748:
2737:
2732:
2725:
2720:
2711:
2710:
2688:
2674:
2672:
2651:
2647:
2636:
2620:
2616:
2605:
2603:
2596:
2591:
2582:
2581:
2569:
2565:
2537:
2533:
2513:
2503:
2499:
2479:
2477:
2470:
2461:
2457:
2434:
2432:
2429:
2428:
2401:
2397:
2376:
2373:
2372:
2365:
2324:
2320:
2308:
2305:
2304:
2242:, and for many
2193:
2190:
2187:
2186:
2184:
2173:
2140:
2109:
2102:
2097:
1943:
1898:
1875:a later section
1858:
1857:
1833:
1829:
1820: mod
1818:
1806:
1802:
1801:
1800:
1796:
1792:
1791:
1786:
1768: and
1766:
1752:
1740:
1736:
1727: mod
1725:
1713:
1709:
1708:
1707:
1703:
1701:
1692: mod
1690:
1678:
1674:
1673:
1672:
1668:
1664:
1662:
1659:
1658:
1634:
1631:
1630:
1614:
1611:
1610:
1593: mod
1591:
1577:
1574:
1573:
1557:
1556:
1532:
1528:
1519: mod
1517:
1505:
1501:
1500:
1499:
1495:
1491:
1490:
1485:
1467: and
1465:
1451:
1439:
1435:
1426: mod
1424:
1412:
1408:
1407:
1406:
1402:
1400:
1391: mod
1389:
1377:
1373:
1372:
1371:
1367:
1363:
1361:
1358:
1357:
1333:
1330:
1329:
1292:
1289:
1288:
1272:
1269:
1268:
1245: and
1243:
1232:
1229:
1228:
1205:
1201:
1196:
1185:
1182:
1181:
1159:
1156:
1155:
1152:
1147:
1109:
1105:
1093:
1089:
1063:
1059:
1058:
1054:
1040:
1036:
1035:
1031:
1029:
1026:
1025:
992:
975:
971:
970:
966:
964:
961:
960:
939:
917:
901:
894:
874:
837:
819:
815:
780:
777:
776:
740:
733:
704:
676:
672:
657:
653:
649:
638:
623:
608:
597:
547:
441:
423:
419:
417:
414:
413:
353:
349:
348:
344:
342:
339:
338:
315:
311:
305:
301:
299:
296:
295:
284:
257:
237:
233:
232:
228:
226:
223:
222:
193:
181:
177:
175:
172:
171:
118:
111:
104:
101:
93:
63:polynomial-time
28:
23:
22:
15:
12:
11:
5:
6671:
6661:
6660:
6655:
6638:
6637:
6635:
6634:
6627:
6624:
6623:
6621:
6620:
6615:
6610:
6605:
6600:
6586:
6581:
6576:
6571:
6565:
6563:
6559:
6558:
6556:
6555:
6550:
6545:
6543:Tonelli–Shanks
6540:
6535:
6529:
6527:
6521:
6520:
6518:
6517:
6512:
6507:
6502:
6496:
6494:
6488:
6487:
6485:
6484:
6479:
6477:Index calculus
6474:
6472:Pohlig–Hellman
6469:
6464:
6459:
6453:
6451:
6445:
6444:
6442:
6441:
6436:
6431:
6426:
6424:Newton-Raphson
6421:
6416:
6411:
6406:
6400:
6398:
6389:
6388:
6386:
6385:
6380:
6375:
6370:
6365:
6360:
6354:
6352:
6350:Multiplication
6346:
6345:
6343:
6342:
6337:
6335:Trial division
6332:
6327:
6322:
6320:Rational sieve
6317:
6310:
6305:
6300:
6292:
6284:
6279:
6274:
6269:
6264:
6258:
6256:
6250:
6249:
6247:
6246:
6241:
6236:
6231:
6226:
6224:Sieve of Atkin
6220:
6218:
6212:
6211:
6209:
6208:
6203:
6198:
6193:
6186:
6179:
6172:
6165:
6160:
6155:
6150:
6148:Elliptic curve
6145:
6140:
6135:
6129:
6127:
6121:
6120:
6110:
6109:
6102:
6095:
6087:
6081:
6080:
6075:
6070:
6065:
6059:
6038:
6037:External links
6035:
6033:
6032:
5989:
5941:
5935:
5893:
5871:
5846:
5810:
5781:
5728:
5687:
5651:
5604:
5572:
5509:
5503:
5472:
5465:
5432:
5419:(2): 151–161.
5399:
5357:Carl Pomerance
5345:
5319:
5309:(1): 128–138,
5287:
5269:(3): 300–317,
5246:
5244:
5241:
5238:
5237:
5220:
5204:
5196:M. M. Artjuhov
5186:
5185:
5183:
5180:
5160:
5159:
5146:
5143:
5139:
5134:
5126:
5123:
5118:
5114:
5107:
5104:
5099:
5093:
5090:
5084:
5010:
5005:
5002:
4998:
4991:
4987:
4984:
4981:
4962:
4961:
4950:
4946:
4941:
4936:
4933:
4929:
4925:
4919:
4914:
4911:
4908:
4905:
4899:
4895:
4892:
4889:
4881:
4875:
4872:
4868:
4864:
4860:
4856:
4853:
4846:
4843:
4840:
4837:
4833:
4826:
4822:
4819:
4816:
4813:
4808:
4804:
4799:
4796:
4793:
4790:
4787:
4782:
4778:
4773:
4770:
4767:
4764:
4761:
4758:
4735:
4732:
4729:
4726:
4707:
4704:
4662:
4661:
4649:
4644:
4641:
4637:
4633:
4627:
4622:
4619:
4613:
4609:
4606:
4603:
4596:
4589:
4586:
4583:
4580:
4576:
4563:
4551:
4546:
4543:
4539:
4535:
4529:
4524:
4519:
4516:
4512:
4504:
4501:
4498:
4494:
4488:
4485:
4482:
4479:
4476:
4446:
4445:
4430:
4427:
4424:
4420:
4414:
4409:
4406:
4403:
4399:
4395:
4391:
4388:
4384:
4379:
4375:
4371:
4367:
4361:
4358:
4355:
4352:
4349:
4346:
4343:
4338:
4334:
4329:
4326:
4323:
4285:
4280:
4276:
4271:
4268:
4265:
4261:
4237:Of course the
4234:
4231:
4218:probably prime
4196:
4171:
4154:
4151:
4048:32 mod 341 = 1
4044:2 mod 341 = 32
3985:probably prime
3824:
3820:probably prime
3770:
3720:
3719:
3687:
3614:
3611:
3557:
3556:
3545:
3530:
3529:
3518:
3493:
3492:
3481:
3470:
3459:
3448:
3437:
3426:
3425:= 2, 3, and 5;
3415:
3404:
3393:
3362:
3359:
3173:
3147:
3135:Big O notation
3084:of the group (
3039:
3036:
3034:
3031:
3010:
3005:
3001:
2996:
2993:
2990:
2987:
2984:
2981:
2966:
2965:
2953:
2949:
2946:
2939:
2936:
2933:
2930:
2926:
2919:
2915:
2912:
2909:
2906:
2901:
2897:
2892:
2889:
2886:
2883:
2880:
2875:
2871:
2866:
2863:
2860:
2857:
2854:
2851:
2833:false negative
2829:
2828:
2807:
2804:
2801:
2798:
2795:
2792:
2787:
2784:
2781:
2778:
2769:
2766:
2763:
2760:
2755:
2751:
2746:
2743:
2740:
2736:
2731:
2728:
2724:
2719:
2716:
2714:
2712:
2703:
2700:
2697:
2694:
2691:
2686:
2683:
2680:
2677:
2668:
2665:
2662:
2659:
2654:
2650:
2645:
2642:
2639:
2634:
2631:
2628:
2623:
2619:
2614:
2611:
2608:
2602:
2599:
2595:
2590:
2587:
2585:
2583:
2577:
2572:
2568:
2563:
2560:
2557:
2554:
2551:
2548:
2545:
2540:
2536:
2531:
2528:
2525:
2522:
2519:
2516:
2511:
2506:
2502:
2497:
2494:
2491:
2488:
2485:
2482:
2476:
2473:
2471:
2469:
2464:
2460:
2455:
2452:
2449:
2446:
2443:
2440:
2437:
2436:
2409:
2404:
2400:
2395:
2392:
2389:
2386:
2383:
2380:
2363:
2341:
2338:
2335:
2332:
2327:
2323:
2318:
2315:
2312:
2172:
2169:
2101:
2098:
2094:probably prime
1944:
1940:probably prime
1910:
1897:
1894:
1856:
1853:
1850:
1847:
1844:
1841:
1836:
1832:
1828:
1825:
1815:
1809:
1805:
1799:
1795:
1793:
1788:, we continue.
1785:
1782:
1779:
1776:
1773:
1765:
1762:
1759:
1751:
1748:
1743:
1739:
1735:
1732:
1722:
1716:
1712:
1706:
1702:
1700:
1697:
1687:
1681:
1677:
1671:
1667:
1666:
1644:
1641:
1638:
1618:
1598:
1590:
1587:
1584:
1581:
1555:
1552:
1549:
1546:
1543:
1540:
1535:
1531:
1527:
1524:
1514:
1508:
1504:
1498:
1494:
1492:
1487:, we continue.
1484:
1481:
1478:
1475:
1472:
1464:
1461:
1458:
1450:
1447:
1442:
1438:
1434:
1431:
1421:
1415:
1411:
1405:
1401:
1399:
1396:
1386:
1380:
1376:
1370:
1366:
1365:
1343:
1340:
1337:
1314:
1311:
1308:
1305:
1302:
1299:
1296:
1276:
1256:
1253:
1250:
1242:
1239:
1236:
1216:
1213:
1208:
1204:
1198: as
1195:
1192:
1189:
1169:
1166:
1163:
1151:
1148:
1112:
1108:
1104:
1099:
1096:
1092:
1088:
1085:
1082:
1077:
1072:
1069:
1066:
1062:
1057:
1053:
1048:
1043:
1039:
1034:
1022:
1021:
1010:
1006:
1003:
999:
996:
991:
988:
983:
978:
974:
969:
929:
907:implying that
887:Euclid's lemma
867:
866:
855:
851:
848:
844:
841:
836:
833:
830:
827:
822:
818:
814:
811:
808:
805:
802:
799:
796:
793:
790:
787:
784:
716:
714:are 1 and −1.
703:
700:
586:false positive
546:
543:
488:contraposition
484:
483:
472:
455:
452:
448:
445:
440:
437:
432:
429:
426:
422:
375:
372:
369:
366:
361:
356:
352:
347:
326:
323:
318:
314:
308:
304:
292:
291:
271:
268:
264:
261:
256:
253:
250:
245:
240:
236:
231:
220:
207:
204:
200:
197:
192:
189:
184:
180:
156:probable prime
110:, let’s write
100:
97:
92:
89:
69:Gary L. Miller
40:primality test
27:Primality test
26:
9:
6:
4:
3:
2:
6670:
6659:
6658:Finite fields
6656:
6654:
6651:
6650:
6648:
6632:
6629:
6628:
6625:
6619:
6616:
6614:
6611:
6609:
6606:
6604:
6601:
6598:
6594:
6590:
6587:
6585:
6582:
6580:
6577:
6575:
6572:
6570:
6567:
6566:
6564:
6560:
6554:
6551:
6549:
6546:
6544:
6541:
6539:
6538:Pocklington's
6536:
6534:
6531:
6530:
6528:
6526:
6522:
6516:
6513:
6511:
6508:
6506:
6503:
6501:
6498:
6497:
6495:
6493:
6489:
6483:
6480:
6478:
6475:
6473:
6470:
6468:
6465:
6463:
6460:
6458:
6455:
6454:
6452:
6450:
6446:
6440:
6437:
6435:
6432:
6430:
6427:
6425:
6422:
6420:
6417:
6415:
6412:
6410:
6407:
6405:
6402:
6401:
6399:
6397:
6394:
6390:
6384:
6381:
6379:
6376:
6374:
6371:
6369:
6366:
6364:
6361:
6359:
6356:
6355:
6353:
6351:
6347:
6341:
6338:
6336:
6333:
6331:
6328:
6326:
6323:
6321:
6318:
6316:
6315:
6311:
6309:
6306:
6304:
6301:
6299:
6297:
6293:
6291:
6289:
6285:
6283:
6282:Pollard's rho
6280:
6278:
6275:
6273:
6270:
6268:
6265:
6263:
6260:
6259:
6257:
6255:
6251:
6245:
6242:
6240:
6237:
6235:
6232:
6230:
6227:
6225:
6222:
6221:
6219:
6217:
6213:
6207:
6204:
6202:
6199:
6197:
6194:
6192:
6191:
6187:
6185:
6184:
6180:
6178:
6177:
6173:
6171:
6170:
6166:
6164:
6161:
6159:
6156:
6154:
6151:
6149:
6146:
6144:
6141:
6139:
6136:
6134:
6131:
6130:
6128:
6126:
6122:
6118:
6115:
6108:
6103:
6101:
6096:
6094:
6089:
6088:
6085:
6079:
6076:
6074:
6071:
6069:
6066:
6063:
6060:
6055:
6054:
6049:
6046:
6041:
6040:
6028:
6023:
6019:
6015:
6011:
6007:
6000:
5993:
5985:
5981:
5976:
5971:
5967:
5963:
5956:
5952:
5945:
5938:
5932:
5928:
5924:
5917:
5916:
5911:
5910:Pomerance, C.
5907:
5906:Granville, A.
5903:
5902:Alford, W. R.
5897:
5882:
5875:
5867:
5866:
5860:
5856:
5850:
5842:
5837:
5833:
5829:
5825:
5821:
5814:
5799:
5795:
5788:
5786:
5777:
5773:
5769:
5765:
5761:
5757:
5752:
5747:
5743:
5739:
5732:
5724:
5720:
5715:
5710:
5706:
5702:
5698:
5691:
5684:
5680:
5675:
5670:
5666:
5662:
5655:
5648:
5644:
5639:
5634:
5630:
5626:
5622:
5618:
5614:
5608:
5600:
5596:
5592:
5585:
5584:
5576:
5569:
5565:
5561:
5557:
5553:
5549:
5545:
5541:
5534:
5530:
5529:Pomerance, C.
5526:
5522:
5516:
5514:
5506:
5500:
5496:
5489:
5485:
5479:
5477:
5468:
5466:0-262-03384-4
5462:
5458:
5454:
5450:
5446:
5442:
5436:
5427:
5422:
5418:
5414:
5410:
5403:
5394:
5389:
5385:
5381:
5374:
5367:(July 1980).
5366:
5362:
5358:
5352:
5350:
5342:
5338:
5334:
5330:
5323:
5316:
5312:
5308:
5304:
5300:
5294:
5292:
5284:
5280:
5276:
5272:
5268:
5264:
5260:
5254:
5252:
5247:
5234:
5230:
5224:
5214:
5208:
5191:
5187:
5179:
5177:
5173:
5169:
5165:
5144:
5141:
5137:
5132:
5124:
5121:
5116:
5112:
5105:
5102:
5097:
5091:
5088:
5082:
5074:
5073:
5072:
5070:
5066:
5062:
5058:
5053:
5051:
5047:
5043:
5039:
5035:
5031:
5027:
5022:
5008:
5003:
5000:
4996:
4989:
4985:
4982:
4979:
4967:
4948:
4944:
4939:
4934:
4931:
4927:
4923:
4912:
4909:
4906:
4903:
4897:
4893:
4890:
4887:
4879:
4873:
4870:
4866:
4862:
4858:
4854:
4851:
4841:
4831:
4824:
4817:
4811:
4806:
4802:
4797:
4788:
4780:
4776:
4771:
4768:
4765:
4749:
4748:
4747:
4730:
4716:
4711:
4703:
4699:
4696:
4688:
4685:
4679:
4675:
4671:
4667:
4647:
4642:
4639:
4635:
4631:
4620:
4617:
4611:
4607:
4604:
4601:
4594:
4584:
4574:
4564:
4549:
4544:
4541:
4537:
4533:
4522:
4517:
4514:
4510:
4502:
4499:
4496:
4492:
4486:
4480:
4467:
4466:
4465:
4463:
4459:
4455:
4451:
4428:
4425:
4422:
4418:
4412:
4407:
4404:
4401:
4397:
4393:
4389:
4386:
4382:
4377:
4373:
4369:
4365:
4359:
4353:
4344:
4336:
4332:
4327:
4314:
4313:
4312:
4310:
4305:
4303:
4278:
4274:
4269:
4259:
4248:
4244:
4240:
4229:
4226:
4223:
4219:
4215:
4211:
4207:
4203:
4199:
4194:
4190:
4186:
4182:
4178:
4174:
4170:
4168:
4164:
4160:
4159:almost surely
4150:
4148:
4142:
4138:
4134:
4126:
4122:
4118:
4112:
4108:
4104:
4100:
4096:
4092:
4086:
4082:
4078:
4074:. Then, when
4073:
4069:
4063:
4060:341 = 11 × 31
4053:
4039:
4035:= 2. We have
4034:
4030:
4025:
4023:
4018:
4014:
4009:
4005:
4001:
3997:
3996:factorization
3993:
3986:
3982:
3978:
3974:
3971:
3967:
3964:
3961:
3957:
3952:
3948:
3944:
3940:
3936:
3935:
3930:
3926:
3922:
3918:
3914:
3911:
3908:
3904:
3900:
3896:
3893:
3890:
3887:
3883:
3879:
3876:
3874:
3870:
3864:
3860:
3856:
3853:
3850:
3846:
3842:
3838:
3834:
3830:
3827:
3821:
3817:
3813:
3807:
3803:
3799:
3795:
3789:
3785:
3781:
3777:
3773:
3769:
3767:
3763:
3759:
3755:
3749:
3745:
3741:
3734:
3730:
3726:
3715:
3708:
3703:
3697:
3693:
3688:
3683:
3679:
3675:
3670:
3664:
3660:
3655:
3654:
3653:
3651:
3647:
3642:
3640:
3636:
3632:
3628:
3624:
3620:
3617:By inserting
3610:
3607:
3603:
3599:
3594:
3590:
3586:
3580:
3574:
3570:
3566:
3561:
3554:
3550:
3546:
3543:
3539:
3535:
3534:
3533:
3527:
3523:
3519:
3516:
3512:
3508:
3507:
3506:
3503:
3499:
3490:
3486:
3482:
3479:
3475:
3471:
3468:
3464:
3460:
3457:
3453:
3449:
3446:
3442:
3438:
3435:
3431:
3427:
3424:
3420:
3416:
3413:
3409:
3405:
3402:
3398:
3394:
3391:
3387:
3383:
3382:
3381:
3377:
3373:
3368:
3358:
3356:
3352:
3348:
3344:
3339:
3335:
3329:
3324:
3322:
3319:
3315:
3308:
3304:
3300:
3296:
3293:
3289:
3286:
3283:
3279:
3275:
3271:
3268:
3267:
3262:
3258:
3254:
3250:
3246:
3243:
3240:
3236:
3232:
3228:
3225:
3222:
3219:
3215:
3211:
3207:
3204:
3201:
3198:
3196:
3191:
3187:
3183:
3179:
3176:
3170:
3166:
3162:
3158:
3154:
3150:
3146:
3144:
3140:
3136:
3130:
3127:
3121:
3117:
3113:
3110:
3106:
3102:
3098:
3094:
3091:
3087:
3083:
3079:
3075:
3071:
3066:
3063:
3055:
3049:
3045:
3030:
3028:
3024:
3003:
2999:
2994:
2991:
2988:
2971:
2951:
2947:
2944:
2934:
2924:
2917:
2910:
2904:
2899:
2895:
2890:
2881:
2873:
2869:
2864:
2861:
2858:
2842:
2841:
2840:
2838:
2834:
2802:
2793:
2790:
2782:
2764:
2758:
2753:
2749:
2744:
2734:
2729:
2726:
2722:
2717:
2715:
2698:
2681:
2663:
2657:
2652:
2648:
2643:
2629:
2626:
2621:
2617:
2612:
2600:
2597:
2593:
2588:
2586:
2570:
2566:
2561:
2558:
2555:
2546:
2538:
2534:
2529:
2526:
2523:
2504:
2500:
2495:
2492:
2489:
2474:
2472:
2462:
2458:
2453:
2450:
2447:
2427:
2426:
2425:
2423:
2402:
2398:
2393:
2390:
2387:
2370:
2366:
2359:
2355:
2336:
2330:
2325:
2321:
2316:
2303:
2299:
2294:
2292:
2288:
2287:cryptographic
2284:
2281:primes whose
2280:
2276:
2272:
2268:
2264:
2260:
2256:
2252:
2247:
2245:
2241:
2237:
2233:
2229:
2225:
2220:
2218:
2214:
2210:
2206:
2202:
2199:of the bases
2182:
2178:
2168:
2164:
2160:
2156:
2152:
2148:
2144:
2138:
2134:
2130:
2126:
2120:
2116:
2112:
2107:
2095:
2091:
2087:
2083:
2080:
2076:
2073:
2070:
2066:
2062:
2058:
2055:
2054:
2049:
2045:
2041:
2037:
2033:
2030:
2027:
2023:
2019:
2015:
2012:
2009:
2006:
2002:
1998:
1994:
1990:
1986:
1982:
1978:
1975:
1972:
1969:
1967:
1962:
1958:
1954:
1950:
1947:
1941:
1937:
1933:
1929:
1925:
1921:
1917:
1913:
1909:
1907:
1903:
1893:
1891:
1887:
1882:
1880:
1876:
1871:
1854:
1851:
1848:
1845:
1842:
1839:
1834:
1830:
1826:
1823:
1813:
1807:
1803:
1797:
1783:
1780:
1777:
1774:
1771:
1763:
1760:
1757:
1754:. Since
1749:
1746:
1741:
1737:
1733:
1730:
1720:
1714:
1710:
1704:
1695:
1685:
1679:
1675:
1669:
1656:
1642:
1639:
1636:
1616:
1596:
1588:
1585:
1582:
1579:
1570:
1553:
1550:
1547:
1544:
1541:
1538:
1533:
1529:
1525:
1522:
1512:
1506:
1502:
1496:
1482:
1479:
1476:
1473:
1470:
1462:
1459:
1456:
1453:. Since
1448:
1445:
1440:
1436:
1432:
1429:
1419:
1413:
1409:
1403:
1394:
1384:
1378:
1374:
1368:
1355:
1341:
1338:
1335:
1326:
1312:
1309:
1306:
1303:
1300:
1297:
1294:
1274:
1254:
1251:
1248:
1240:
1237:
1234:
1214:
1211:
1206:
1202:
1193:
1190:
1187:
1167:
1164:
1161:
1146:
1144:
1140:
1136:
1132:
1128:
1110:
1106:
1102:
1097:
1094:
1090:
1086:
1083:
1080:
1075:
1070:
1067:
1064:
1060:
1055:
1051:
1046:
1041:
1037:
1032:
1008:
1001:
997:
989:
986:
981:
976:
972:
967:
959:
958:
957:
955:
951:
946:
942:
937:
928:
926:
922:
916:
914:
910:
904:
897:
892:
888:
882:
878:
872:
853:
846:
842:
834:
831:
828:
825:
820:
816:
812:
806:
803:
800:
791:
788:
785:
775:
774:
773:
771:
767:
763:
759:
755:
750:
747:
743:
739:
732:
728:
724:
715:
713:
709:
699:
697:
695:
689:
683:
679:
669:
665:
661:
645:
641:
634:
630:
626:
621:
615:
611:
604:
600:
594:
592:
587:
583:
581:
575:
571:
567:
562:
560:
558:
552:
542:
540:
536:
532:
531:
526:
522:
517:
515:
511:
510:
505:
501:
497:
493:
489:
482:are 1 and −1.
481:
477:
473:
470:
450:
446:
438:
435:
430:
427:
424:
420:
411:
407:
406:
405:
403:
398:
397:
393:
389:
373:
370:
367:
364:
359:
354:
350:
345:
324:
321:
316:
306:
302:
288:
266:
262:
254:
251:
248:
243:
238:
234:
229:
221:
202:
198:
190:
187:
182:
178:
170:
169:
168:
166:
162:
161:
157:
151:
147:
143:
139:
135:
131:
127:
122:
114:
107:
96:
88:
86:
82:
78:
74:
73:deterministic
70:
66:
64:
59:
57:
53:
49:
45:
41:
37:
33:
19:
6630:
6312:
6295:
6287:
6206:Miller–Rabin
6205:
6188:
6181:
6174:
6169:Lucas–Lehmer
6167:
6051:
6009:
6005:
5992:
5965:
5961:
5944:
5914:
5896:
5886:February 24,
5884:. Retrieved
5874:
5862:
5849:
5823:
5819:
5813:
5803:February 24,
5801:. Retrieved
5797:
5741:
5737:
5731:
5704:
5700:
5690:
5664:
5660:
5654:
5620:
5616:
5607:
5582:
5575:
5543:
5539:
5525:Landrock, P.
5494:
5484:Schoof, René
5456:
5435:
5416:
5412:
5402:
5383:
5379:
5332:
5328:
5322:
5306:
5302:
5266:
5262:
5223:
5207:
5190:
5175:
5171:
5167:
5163:
5161:
5068:
5064:
5060:
5056:
5054:
5049:
5045:
5041:
5023:
4965:
4963:
4712:
4709:
4697:
4694:
4686:
4683:
4677:
4673:
4665:
4663:
4461:
4447:
4306:
4236:
4227:
4224:
4221:
4217:
4213:
4209:
4205:
4201:
4197:
4192:
4188:
4184:
4180:
4176:
4172:
4162:
4156:
4146:
4140:
4136:
4132:
4124:
4120:
4116:
4110:
4106:
4102:
4098:
4094:
4090:
4084:
4080:
4076:
4071:
4067:
4064:
4051:
4040:− 1 = 85 × 4
4037:
4032:
4028:
4026:
4021:
4016:
4012:
4007:
4003:
3999:
3991:
3989:
3984:
3980:
3976:
3972:
3969:
3965:
3962:
3959:
3955:
3950:
3946:
3942:
3938:
3933:
3931:
3928:
3924:
3920:
3916:
3912:
3909:
3906:
3902:
3898:
3894:
3891:
3888:
3885:
3881:
3877:
3872:
3868:
3866:
3862:
3861:← random(2,
3858:
3854:
3851:
3848:
3844:
3840:
3836:
3832:
3828:
3825:
3822:” otherwise
3819:
3815:
3811:
3805:
3801:
3797:
3793:
3787:
3783:
3779:
3775:
3771:
3765:
3761:
3757:
3753:
3747:
3743:
3739:
3732:
3728:
3724:
3721:
3713:
3706:
3701:
3695:
3691:
3681:
3677:
3673:
3668:
3662:
3658:
3649:
3645:
3643:
3638:
3634:
3630:
3626:
3622:
3616:
3605:
3601:
3592:
3588:
3584:
3578:
3572:
3568:
3564:
3562:
3558:
3552:
3548:
3541:
3537:
3531:
3525:
3521:
3514:
3510:
3494:
3488:
3484:
3477:
3473:
3466:
3462:
3455:
3451:
3444:
3440:
3433:
3429:
3422:
3418:
3414:= 31 and 73;
3411:
3407:
3400:
3396:
3389:
3385:
3375:
3371:
3366:
3364:
3340:
3333:
3325:
3311:
3306:
3302:
3298:
3294:
3291:
3287:
3284:
3281:
3277:
3273:
3269:
3265:
3263:
3260:
3256:
3252:
3248:
3244:
3241:
3238:
3234:
3230:
3226:
3223:
3220:
3217:
3213:
3209:
3205:
3202:
3199:
3194:
3192:
3189:
3185:
3181:
3177:
3174:
3171:” otherwise
3168:
3164:
3160:
3156:
3152:
3148:
3142:
3128:
3115:
3111:
3108:
3104:
3096:
3092:
3089:
3085:
3077:
3073:
3069:
3067:
3061:
3053:
3047:
3043:
3041:
3025:primes (see
3022:
2967:
2830:
2368:
2361:
2353:
2297:
2295:
2290:
2278:
2270:
2266:
2265:. Hence the
2262:
2258:
2254:
2250:
2248:
2243:
2239:
2231:
2227:
2221:
2216:
2212:
2208:
2204:
2200:
2180:
2176:
2174:
2162:
2158:
2150:
2146:
2142:
2128:
2124:
2118:
2114:
2103:
2093:
2089:
2085:
2081:
2078:
2074:
2071:
2068:
2064:
2060:
2056:
2052:
2050:
2047:
2043:
2039:
2035:
2031:
2028:
2025:
2021:
2017:
2013:
2010:
2007:
2004:
2000:
1996:
1992:
1988:
1984:
1983:← random(2,
1980:
1976:
1973:
1970:
1965:
1963:
1960:
1956:
1952:
1948:
1945:
1942:” otherwise
1939:
1935:
1931:
1927:
1923:
1919:
1915:
1911:
1905:
1899:
1885:
1883:
1878:
1872:
1657:
1571:
1356:
1327:
1153:
1142:
1134:
1126:
1023:
953:
949:
944:
940:
935:
933:
924:
920:
918:
912:
908:
902:
895:
890:
880:
876:
870:
868:
769:
765:
756:has no more
748:
745:
741:
738:finite field
726:
722:
720:
711:
707:
705:
693:
687:
684:
677:
670:
663:
659:
643:
639:
632:
628:
624:
613:
609:
602:
598:
595:
590:
579:
573:
569:
563:
556:
548:
538:
534:
528:
524:
520:
518:
513:
507:
506:is called a
503:
499:
495:
491:
485:
479:
478:of 1 modulo
476:square roots
468:
401:
399:
395:
391:
387:
293:
286:
159:
153:
149:
145:
137:
133:
129:
125:
120:
112:
105:
102:
94:
67:
60:
35:
31:
29:
6462:Pollard rho
6419:Goldschmidt
6153:Pocklington
6143:Baillie–PSW
5521:Damgård, I.
5335:: 355–364,
4452:. Using an
4101:is neither
4070:of −1, say
3943:multiple of
3831:> 0 and
3794:multiple of
3567:values for
3180:> 0 and
3143:Miller test
3076:coprime to
3038:Miller test
2837:denominator
2236:Euler liars
1951:> 0 and
557:Miller test
539:strong liar
285:0 ≤ r <
140:, which is
136:, called a
6647:Categories
6574:Cornacchia
6569:Chakravala
6117:algorithms
5751:1509.00864
5613:Bach, Eric
5243:References
4233:Complexity
4058:. Indeed,
4031:= 341 and
4010:such that
3897::
3694:≢ ±1 (mod
3403:= 2 and 3;
3374:< 2(ln
3330:notation,
3276:”
3229::
2422:Bayes' law
2291:worst‐case
2271:generating
2100:Complexity
2063:”
2016::
1902:pseudocode
1287:such that
731:polynomial
642:≡ −1 (mod
631:≡ −1 (mod
596:Note that
486:Hence, by
6548:Berlekamp
6505:Euclidean
6393:Euclidean
6373:Toom–Cook
6368:Karatsuba
6053:MathWorld
5216:isprime()
5200:Theorem E
5166:≥ 21 and
5142:−
5117:−
5038:Pomerance
5001:−
4983:
4932:−
4907:−
4891:
4871:−
4863:≤
4852:−
4815:¬
4812:∣
4769:∣
4763:¬
4640:−
4605:
4542:−
4515:−
4500:
4426:−
4405:−
4390:π
4387:−
4366:π
4309:uniformly
4216:returns “
4022:composite
3977:composite
3812:composite
3808:is found,
3661:≡ 1 (mod
3318:quadratic
3299:composite
3274:composite
3161:composite
3139:Eric Bach
3101:generates
2992:∣
2986:¬
2945:−
2908:¬
2905:∣
2862:∣
2856:¬
2794:−
2762:¬
2759:∣
2696:¬
2661:¬
2658:∣
2627:∣
2559:∧
2527:∧
2521:¬
2493:∧
2487:¬
2451:∣
2445:¬
2391:∣
2385:¬
2334:¬
2331:∣
2086:composite
2061:composite
1932:composite
1852:−
1846:≠
1840:≡
1827:≡
1781:−
1775:≠
1761:≠
1747:≡
1734:≡
1699:→
1586:−
1583:≡
1551:−
1539:≡
1526:≡
1480:−
1474:≠
1460:≠
1446:≡
1433:≡
1398:→
1310:−
1304:≤
1298:≤
1212:×
1191:−
1084:…
1068:−
987:≡
832:≡
826:−
789:−
736:over the
612:≡ 1 (mod
601:≡ 1 (mod
474:the only
436:≡
428:−
371:−
337:and then
283:for some
252:−
249:≡
188:≡
87:in 1980.
44:algorithm
6515:Lehmer's
6409:Chunking
6396:division
6325:Fermat's
5723:33599405
5531:(1993),
5486:(2004),
5283:10690396
5034:Landrock
4706:Accuracy
4247:expected
4181:Input #2
4173:Input #1
4093:against
4015:≡ 1 mod
3990:This is
3919:≠ 1 and
3915:= 1 and
3780:Input #2
3772:Input #1
3671:divides
3604:log log
3251:≠ 1 and
3247:= 1 and
3082:subgroup
3023:generate
2171:Accuracy
2149:log log
2123:, where
2038:≠ 1 and
2034:= 1 and
1995:− 1
1987:− 2) #
1920:Input #2
1912:Input #1
889:, since
772:. Then:
692:section
580:Accuracy
578:section
555:section
158:to base
148:. Then,
54:and the
6631:Italics
6553:Kunerth
6533:Cipolla
6414:Fourier
6383:Fürer's
6277:Euler's
6267:Dixon's
6190:Pépin's
6014:Bibcode
5984:0583518
5857:(ed.).
5828:Bibcode
5776:6955806
5756:Bibcode
5683:2153262
5647:2008811
5625:Bibcode
5568:2152945
5548:Bibcode
5371:25 ⋅ 10
5341:0213289
5233:GNU GMP
5229:OpenSSL
5030:Damgård
5026:earlier
4670:earlier
4302:earlier
4113:, then
4042:. Then
3945:”, gcd(
3839:− 1 = 2
3676:− 1 = (
3502:A014233
3500::
3332:Õ((log
3200:for all
3188:− 1 = 2
2356:is the
2267:average
2197:
2185:
1959:− 1 = 2
1150:Example
658:1 <
568:. When
509:witness
498:, then
167:holds:
154:strong
142:coprime
6613:Schoof
6500:Binary
6404:Binary
6340:Shor's
6158:Fermat
5982:
5933:
5774:
5721:
5681:
5645:
5566:
5527:&
5501:
5463:
5339:
5281:
5178:≥ 32.
4245:, the
4225:return
4189:Output
3981:return
3973:return
3939:return
3889:repeat
3865:− 2)
3857::
3849:repeat
3788:Output
3742:= gcd(
3727:= gcd(
3689:since
3656:since
3347:APR-CL
3328:soft-O
3303:return
3295:return
3270:return
3221:repeat
3157:Output
2352:where
2279:verify
2104:Using
2090:return
2082:return
2057:return
2008:repeat
1979::
1971:repeat
1928:Output
1572:Since
1145:, is.
948:where
943:− 1= 2
702:Proofs
648:since
622:. And
533:, and
124:where
108:> 2
6434:Short
6163:Lucas
6002:(PDF)
5958:(PDF)
5919:(PDF)
5772:S2CID
5746:arXiv
5719:S2CID
5679:JSTOR
5643:JSTOR
5587:(PDF)
5564:JSTOR
5536:(PDF)
5491:(PDF)
5376:(PDF)
5279:S2CID
5213:Maple
5182:Notes
4198:while
4097:: if
3949:− 1,
3895:times
3855:times
3814:” if
3746:+ 1,
3731:− 1,
3680:− 1)(
3600:(log
3314:index
3307:prime
3227:times
3169:prime
3163:” if
3149:Input
3027:below
2358:event
2275:below
2014:times
1977:times
1934:” if
1131:lemma
931:Proof
885:. By
879:− 1)(
758:roots
754:field
734:X − 1
718:Proof
696:below
690:(see
662:<
582:below
559:below
537:is a
490:, if
42:: an
6429:Long
6363:Long
5931:ISBN
5888:2019
5863:The
5805:2019
5499:ISBN
5461:ISBN
5231:and
5044:and
5036:and
4789:<
4691:(or
4676:and
4345:>
4222:then
4212:and
4131:gcd(
4129:and
4115:gcd(
4105:nor
4079:mod
4046:and
3970:then
3968:≠ 1
3929:then
3927:− 1
3905:mod
3884:mod
3847:− 1
3737:and
3711:nor
3684:+ 1)
3577:(ln
3498:OEIS
3392:= 2;
3351:ECPP
3349:and
3292:then
3290:≠ 1
3261:then
3259:− 1
3237:mod
3216:mod
3060:log
2882:<
2238:for
2161:log
2153:) =
2145:log
2117:log
2079:then
2077:≠ 1
2048:then
2046:− 1
2024:mod
2003:mod
1888:see
1328:Say
905:+ 1,
883:+ 1)
138:base
30:The
6593:LLL
6439:SRT
6298:+ 1
6290:− 1
6138:APR
6133:AKS
6022:doi
5970:doi
5923:doi
5836:doi
5764:doi
5709:doi
5669:doi
5633:doi
5595:doi
5556:doi
5421:doi
5388:doi
5311:doi
5271:doi
5028:),
4304:).
4167:bit
4087:− 1
3992:not
3875:− 1
3826:let
3804:of
3796:”,
3716:+ 1
3709:− 1
3644:If
3547:if
3536:if
3520:if
3509:if
3483:if
3472:if
3461:if
3450:if
3439:if
3428:if
3417:if
3406:if
3395:if
3384:if
3197:− 1
3175:let
3159:: “
3124:O((
2133:FFT
1968:− 1
1946:let
1930:: “
1843:205
1835:110
1831:137
1824:221
1798:137
1772:188
1758:188
1750:188
1738:137
1731:221
1705:137
1643:137
1580:220
1542:220
1534:110
1530:174
1523:221
1497:174
1437:174
1430:221
1404:174
1342:174
1168:221
998:mod
934:If
900:or
898:− 1
843:mod
698:).
680:− 2
666:− 1
561:).
447:mod
408:by
313:mod
263:mod
199:mod
144:to
117:as
115:− 1
34:or
6649::
6597:KZ
6595:;
6050:.
6020:,
6010:65
6008:,
6004:,
5980:MR
5978:.
5966:35
5964:.
5960:.
5929:,
5908:;
5904:;
5861:.
5834:,
5824:72
5822:,
5796:.
5784:^
5770:.
5762:.
5754:.
5742:86
5740:.
5717:.
5705:83
5703:.
5699:.
5677:,
5665:61
5663:,
5641:,
5631:,
5621:55
5619:,
5562:,
5554:,
5544:61
5542:,
5538:,
5523:;
5512:^
5493:,
5475:^
5451:;
5447:;
5443:;
5417:20
5415:.
5411:.
5384:35
5382:.
5378:.
5363:;
5359:;
5348:^
5337:MR
5333:12
5331:,
5307:12
5305:,
5290:^
5277:,
5267:13
5265:,
5250:^
5170:≥
5103:15
5032:,
4980:ln
4888:ln
4836:Pr
4792:Pr
4757:Pr
4725:Pr
4693:Õ(
4682:O(
4602:ln
4579:Pr
4497:ln
4475:Pr
4348:Pr
4322:Pr
4264:Pr
4220:”
4206:if
4183::
4175::
4149:.
4139:,
4135:+
4123:,
4119:−
4083:=
4062:.
3987:”
3979:”
3963:if
3958:←
3953:))
3941:(“
3923:≠
3910:if
3901:←
3880:←
3867:#
3792:(“
3790::
3782::
3774::
3766:AB
3764:=
3652:,
3641:.
3608:).
3336:))
3323:.
3309:”
3301:”
3285:if
3280:←
3255:≠
3242:if
3233:←
3212:←
3206:in
3151::
3131:))
3126:ln
3052:O(
2980:Pr
2929:Pr
2885:Pr
2850:Pr
2797:Pr
2777:Pr
2739:Pr
2690:Pr
2676:Pr
2638:Pr
2607:Pr
2550:Pr
2515:Pr
2481:Pr
2439:Pr
2424::
2379:Pr
2362:MR
2311:Pr
2167:.
2141:O(
2096:”
2088:”
2072:if
2067:←
2042:≠
2029:if
2020:←
1999:←
1922::
1914::
1892:.
1881:.
1814:55
1742:55
1721:55
1655::
1513:55
1471:47
1457:47
1449:47
1441:55
1420:55
1354::
1325:.
1255:55
1215:55
927:.
915:.
682:.
668:.
627:=
541:.
516:.
412:,
396:n.
388:r.
79:.
58:.
6599:)
6591:(
6296:p
6288:p
6106:e
6099:t
6092:v
6056:.
6024::
6016::
5986:.
5972::
5925::
5890:.
5838::
5830::
5807:.
5778:.
5766::
5758::
5748::
5725:.
5711::
5671::
5635::
5627::
5601:.
5597::
5558::
5550::
5469:.
5429:.
5423::
5396:.
5390::
5373:"
5313::
5273::
5176:b
5172:b
5168:k
5164:b
5145:k
5138:4
5133:)
5125:2
5122:b
5113:2
5106:4
5098:b
5092:7
5089:1
5083:(
5069:b
5065:b
5061:b
5057:b
5050:k
5046:k
5042:b
5009:b
5004:k
4997:4
4990:2
4986:2
4966:b
4949:.
4945:)
4940:)
4935:1
4928:b
4924:(
4918:O
4913:+
4910:1
4904:b
4898:2
4894:2
4880:(
4874:k
4867:4
4859:)
4855:1
4845:)
4842:P
4839:(
4832:1
4825:(
4821:)
4818:P
4807:k
4803:R
4798:M
4795:(
4786:)
4781:k
4777:R
4772:M
4766:P
4760:(
4734:)
4731:P
4728:(
4700:)
4698:b
4695:k
4689:)
4687:b
4684:k
4678:k
4674:b
4666:b
4648:)
4643:1
4636:b
4632:(
4626:O
4621:+
4618:b
4612:2
4608:2
4595:=
4588:)
4585:P
4582:(
4575:1
4550:)
4545:3
4538:b
4534:(
4528:O
4523:+
4518:1
4511:b
4503:2
4493:2
4487:=
4484:)
4481:P
4478:(
4462:b
4429:2
4423:b
4419:2
4413:)
4408:1
4402:b
4398:2
4394:(
4383:)
4378:b
4374:2
4370:(
4360:=
4357:)
4354:P
4351:(
4342:)
4337:k
4333:R
4328:M
4325:(
4284:)
4279:k
4275:R
4270:M
4267:(
4260:1
4228:n
4214:k
4210:n
4202:n
4193:n
4185:k
4177:b
4165:‐
4163:b
4147:n
4143:)
4141:n
4137:R
4133:x
4127:)
4125:n
4121:R
4117:x
4111:R
4109:−
4107:n
4103:R
4099:x
4095:R
4091:x
4085:n
4081:n
4077:x
4072:R
4068:n
4052:n
4038:n
4033:a
4029:n
4017:n
4013:a
4008:n
4004:a
4000:n
3983:“
3975:“
3966:y
3960:y
3956:x
3951:n
3947:x
3934:n
3925:n
3921:x
3917:x
3913:y
3907:n
3903:x
3899:y
3892:s
3886:n
3882:a
3878:x
3873:n
3869:n
3863:n
3859:a
3852:k
3845:n
3841:d
3837:n
3833:d
3829:s
3816:n
3810:“
3806:n
3802:m
3798:m
3784:k
3776:n
3762:n
3758:n
3754:n
3750:)
3748:n
3744:x
3740:B
3735:)
3733:n
3729:x
3725:A
3718:.
3714:x
3707:x
3702:n
3698:)
3696:n
3692:x
3686:;
3682:x
3678:x
3674:x
3669:n
3665:)
3663:n
3659:x
3650:n
3646:x
3639:a
3635:a
3631:n
3627:n
3623:n
3606:n
3602:n
3598:Θ
3593:w
3589:n
3585:w
3581:)
3579:n
3573:n
3569:b
3565:b
3553:a
3549:n
3542:a
3538:n
3526:a
3522:n
3515:a
3511:n
3489:a
3485:n
3478:a
3474:n
3467:a
3463:n
3456:a
3452:n
3445:a
3441:n
3434:a
3430:n
3423:a
3419:n
3412:a
3408:n
3401:a
3397:n
3390:a
3386:n
3378:)
3376:n
3372:a
3367:n
3334:n
3305:“
3297:“
3288:y
3282:y
3278:x
3272:“
3266:n
3257:n
3253:x
3249:x
3245:y
3239:n
3235:x
3231:y
3224:s
3218:n
3214:a
3210:x
3203:a
3195:n
3190:d
3186:n
3182:d
3178:s
3165:n
3153:n
3129:n
3116:n
3112:Z
3109:n
3107:/
3105:Z
3103:(
3097:a
3093:Z
3090:n
3088:/
3086:Z
3078:n
3074:a
3070:n
3062:n
3056:)
3054:n
3048:n
3044:a
3009:)
3004:k
3000:R
2995:M
2989:P
2983:(
2952:)
2948:1
2938:)
2935:P
2932:(
2925:1
2918:(
2914:)
2911:P
2900:k
2896:R
2891:M
2888:(
2879:)
2874:k
2870:R
2865:M
2859:P
2853:(
2806:)
2803:P
2800:(
2791:1
2786:)
2783:P
2780:(
2768:)
2765:P
2754:k
2750:R
2745:M
2742:(
2735:1
2730:+
2727:1
2723:1
2718:=
2702:)
2699:P
2693:(
2685:)
2682:P
2679:(
2667:)
2664:P
2653:k
2649:R
2644:M
2641:(
2633:)
2630:P
2622:k
2618:R
2613:M
2610:(
2601:+
2598:1
2594:1
2589:=
2576:)
2571:k
2567:R
2562:M
2556:P
2553:(
2547:+
2544:)
2539:k
2535:R
2530:M
2524:P
2518:(
2510:)
2505:k
2501:R
2496:M
2490:P
2484:(
2475:=
2468:)
2463:k
2459:R
2454:M
2448:P
2442:(
2408:)
2403:k
2399:R
2394:M
2388:P
2382:(
2369:k
2364:k
2354:P
2340:)
2337:P
2326:k
2322:R
2317:M
2314:(
2298:k
2263:n
2259:n
2255:n
2251:n
2244:n
2240:n
2232:n
2228:n
2217:n
2213:k
2209:n
2205:n
2201:a
2194:4
2191:/
2188:1
2181:n
2177:a
2165:)
2163:n
2159:k
2157:(
2155:Õ
2151:n
2147:n
2143:k
2129:k
2125:n
2121:)
2119:n
2115:k
2113:(
2111:O
2092:“
2084:“
2075:y
2069:y
2065:x
2059:“
2053:n
2044:n
2040:x
2036:x
2032:y
2026:n
2022:x
2018:y
2011:s
2005:n
2001:a
1997:x
1993:n
1989:n
1985:n
1981:a
1974:k
1966:n
1961:d
1957:n
1953:d
1949:s
1936:n
1924:k
1916:n
1906:k
1886:a
1879:n
1855:1
1849:n
1808:1
1804:2
1784:1
1778:n
1764:1
1715:0
1711:2
1696:n
1686:d
1680:0
1676:s
1670:a
1640:=
1637:a
1617:a
1597:n
1589:1
1554:1
1548:n
1545:=
1507:1
1503:2
1483:1
1477:n
1463:1
1414:0
1410:2
1395:n
1385:d
1379:0
1375:s
1369:a
1339:=
1336:a
1313:2
1307:n
1301:a
1295:2
1275:a
1252:=
1249:d
1241:2
1238:=
1235:s
1207:2
1203:2
1194:1
1188:n
1165:=
1162:n
1143:a
1135:n
1127:n
1111:d
1107:a
1103:,
1098:d
1095:2
1091:a
1087:,
1081:,
1076:d
1071:1
1065:s
1061:2
1056:a
1052:,
1047:d
1042:s
1038:2
1033:a
1009:.
1005:)
1002:n
995:(
990:1
982:d
977:s
973:2
968:a
954:d
950:s
945:d
941:n
936:n
925:a
921:n
913:n
909:x
903:x
896:x
891:n
881:x
877:x
875:(
871:n
854:.
850:)
847:n
840:(
835:0
829:1
821:2
817:x
813:=
810:)
807:1
804:+
801:x
798:(
795:)
792:1
786:x
783:(
770:n
766:x
749:Z
746:n
744:/
742:Z
727:n
723:n
712:n
708:n
688:n
678:n
673:n
664:n
660:a
654:a
650:d
646:)
644:n
640:a
635:)
633:n
629:a
625:a
616:)
614:n
610:a
605:)
603:n
599:a
591:n
574:n
570:n
535:a
525:a
521:n
514:n
504:a
500:n
496:a
492:n
480:n
454:)
451:n
444:(
439:1
431:1
425:n
421:a
402:n
392:r
374:1
368:n
365:=
360:d
355:r
351:2
346:a
325:1
322:=
317:n
307:d
303:a
290:.
287:s
270:)
267:n
260:(
255:1
244:d
239:r
235:2
230:a
219:;
206:)
203:n
196:(
191:1
183:d
179:a
160:a
150:n
146:n
134:a
130:d
126:s
121:d
119:2
113:n
106:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.