1507:
1249:
1612:
1804:, the better the accuracy of test. Hence the chance of the algorithm failing in this way is so small that the (pseudo) prime is used in practice in cryptographic applications, but for applications for which it is important to have a prime, a test like
1739:
1960:
364:
169:
1502:{\displaystyle (a\cdot a_{i})^{(n-1)/2}=a^{(n-1)/2}\cdot a_{i}^{(n-1)/2}=a^{(n-1)/2}\cdot \left({\frac {a_{i}}{n}}\right)\not \equiv \left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right){\pmod {n}}.}
503:
1117:
1035:
699:
554:
254:
209:
941:
Hence 2 is an Euler witness for the compositeness of 221, and 47 was in fact an Euler liar. Note that this tells us nothing about the prime factors of 221, which are actually 13 and 17.
651:
2767:
1518:
1766:, which is also an Euler witness. So each Euler liar gives an Euler witness and so the number of Euler witnesses is larger or equal to the number of Euler liars. Therefore, when
836:
935:
896:
797:
1623:
1838:
1832:
for which the bound is (approximately) attained are extremely rare. On the average, the error probability of the algorithm is significantly smaller: it is less than
580:
2771:
2279:
2312:
43:. The idea behind the test was discovered by M. M. Artjuhov in 1967 (see Theorem E in the paper). This test has been largely superseded by the
285:
90:
2251:
2636:
2272:
2504:
2235:
2226:
Dietzfelbinger, Martin (2004-06-29). "Primality
Testing in Polynomial Time, From Randomized Algorithms to "PRIMES Is in P"".
2165:
2446:
2265:
748:
454:
1053:
997:
2552:
656:
511:
2499:
2461:
2436:
2350:
2038:
Artjuhov, M. M. (1966–1967), "Certain criteria for primality of numbers connected with the little Fermat theorem",
1805:
1607:{\displaystyle \left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right)=\left({\frac {a\cdot a_{i}}{n}}\right),}
222:
177:
2641:
2532:
2451:
2441:
2380:
2343:
2121:
I. Damgård; P. Landrock; C. Pomerance (1993). "Average case error estimates for the strong probable prime test".
1786:
48:
585:
2837:
2469:
2317:
44:
2722:
2717:
2684:
2646:
2547:
1186:
1824:
The bound 1/2 on the error probability of a single round of the
Solovay–Strassen test holds for any input
806:
2832:
2598:
905:
2763:
2753:
2712:
2488:
2482:
2456:
2327:
1809:
866:
767:
1734:{\displaystyle (a\cdot a_{i})^{(n-1)/2}\not \equiv \left({\frac {a\cdot a_{i}}{n}}\right){\pmod {n}}.}
708:, for which the proportion of witnesses may be much smaller. Therefore, there are no (odd) composite
2748:
2689:
1785:
Hence, the probability of failure is at most 2 (compare this with the probability of failure for the
2827:
2651:
2524:
2370:
2322:
2666:
2557:
1955:{\displaystyle 2^{-k}\exp \left(-(1+o(1)){\frac {\log x\,\log \log \log x}{\log \log x}}\right)}
2777:
2727:
2707:
2205:
Solovay, Robert M.; Strassen, Volker (1978). "Erratum: A fast Monte-Carlo test for primality".
1979:. The same bound also applies to the related problem of what is the conditional probability of
1138:
2787:
2428:
2403:
2332:
705:
269:
842:
This gives that, either 221 is prime, or 47 is an Euler liar for 221. We try another random
2782:
2674:
2656:
2631:
2593:
2337:
2063:
2051:
32:
2086:
P. Erdős; C. Pomerance (1986). "On the number of false witnesses for a composite number".
559:
8:
2792:
2758:
2679:
2583:
2542:
2537:
2514:
2418:
2074:
2623:
2570:
2567:
2408:
2357:
2307:
2138:
2103:
2364:
2185:
Solovay, Robert M.; Strassen, Volker (1977). "A fast Monte-Carlo test for primality".
2743:
2699:
2413:
2390:
2231:
2161:
713:
59:
24:
2588:
2214:
2194:
2130:
2095:
2013:
2006:
378:
36:
51:, but has great historical importance in showing the practical feasibility of the
2578:
2477:
2047:
2017:
212:
52:
28:
2608:
2509:
2494:
2398:
2299:
261:
70:
40:
19:
2257:
2821:
2603:
2288:
1165:
It is possible for the algorithm to return an incorrect answer. If the input
216:
2613:
1793:
74:
55:
1208:) = 1 are Euler witnesses. We can prove this as follows: let {
508:
are (Euler) witnesses as the set of Euler liars is a proper subgroup of
359:{\displaystyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}
164:{\displaystyle a^{(p-1)/2}\equiv \left({\frac {a}{p}}\right){\pmod {p}}}
2142:
2107:
950:
743:): 47. Using an efficient method for raising a number to a power (mod
405:
is not prime (but this does not tell us a nontrivial factorization of
2291:
2218:
2198:
2134:
2099:
1177:
is composite then it is possible for the output to be incorrectly
260:
can be any odd integer. The Jacobi symbol can be computed in time
2120:
397:
at random and test the congruence, then as soon as we find an
2254:
Implementation of the
Solovay–Strassen primality test in Maple
1169:
is indeed prime, then the output will always correctly be
2808:
indicate that algorithm is for numbers of special forms
1800:
we test, i.e. if we pick a sufficiently large value of
967:, a parameter that determines the accuracy of the test
762: = 47 mod 221 = −1 mod 221
1012:
913:
874:
814:
775:
231:
186:
2155:
1841:
1626:
1521:
1252:
1056:
1000:
908:
869:
809:
770:
659:
588:
562:
514:
498:{\displaystyle a\in (\mathbb {Z} /n\mathbb {Z} )^{*}}
457:
288:
225:
180:
93:
2085:
2005:
The
Solovay–Strassen algorithm shows that the
1112:{\displaystyle a^{(n-1)/2}\not \equiv x{\pmod {n}}}
1030:{\displaystyle x\gets \left({\tfrac {a}{n}}\right)}
1954:
1733:
1606:
1501:
1111:
1029:
929:
890:
830:
791:
693:
645:
574:
548:
497:
358:
279:one can contemplate whether or not the congruence
248:
203:
163:
2819:
2160:. Cambridge University Press. pp. 417–423.
1969:rounds of the test, applied to uniformly random
861: = 2 mod 221 = 30 mod 221
694:{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}
549:{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}
2287:
2204:
2184:
2225:
401:which doesn't fit the congruence we know that
389:is prime then this congruence is true for all
219:is a generalisation of the Legendre symbol to
58:. The Solovay–Strassen test is essentially an
2273:
2037:
944:
640:
592:
249:{\displaystyle \left({\tfrac {a}{n}}\right)}
204:{\displaystyle \left({\tfrac {a}{p}}\right)}
1196:is odd and composite, at least half of all
712:without many witnesses, unlike the case of
421:; it is a witness for the compositeness of
2280:
2266:
1141:, the running time of this algorithm is O(
646:{\displaystyle =\{1,8,14,18,47,51,57,64\}}
1905:
1819:
677:
664:
582:, the set of Euler liars has order 8 and
532:
519:
481:
468:
268:)²) using Jacobi's generalization of the
963:, a value to test for primality
1160:
937:mod 221 = −1 mod 221.
838:mod 221 = −1 mod 221.
369:holds for various values of the "base"
2820:
2261:
1782:) = 1 is an Euler witness.
1153:is the number of different values of
728: = 221 is prime. We write (
1983:being composite for a random number
831:{\displaystyle ({\tfrac {47}{221}})}
1770:is composite, at least half of all
1720:
1488:
1101:
930:{\displaystyle ({\tfrac {2}{221}})}
348:
153:
13:
2178:
14:
2849:
2489:Special number field sieve (SNFS)
2483:General number field sieve (GNFS)
2245:
2228:Lecture Notes in Computer Science
1993:which has been declared prime in
891:{\displaystyle ({\tfrac {a}{n}})}
792:{\displaystyle ({\tfrac {a}{n}})}
739:(greater than 1 and smaller than
35:test to determine if a number is
2156:R. Motwani; P. Raghavan (1995).
949:The algorithm can be written in
724:Suppose we wish to determine if
437:if the congruence is true while
1713:
1481:
1094:
341:
146:
2149:
2114:
2079:
2068:
2057:
2031:
1890:
1887:
1881:
1869:
1724:
1714:
1663:
1651:
1647:
1627:
1492:
1482:
1393:
1381:
1360:
1348:
1322:
1310:
1289:
1277:
1273:
1253:
1105:
1095:
1074:
1062:
1004:
924:
909:
885:
870:
825:
810:
786:
771:
682:
660:
537:
515:
486:
464:
352:
342:
306:
294:
157:
147:
111:
99:
1:
2075:Pocklington test on Mathworld
2024:
2000:
1512:Because the following holds:
448:, at least half of all bases
2447:Lenstra elliptic curve (ECM)
2230:. Vol. 3000. Springer.
1235:an Euler witness. Then, for
270:law of quadratic reciprocity
7:
1787:Miller–Rabin primality test
993:randomly in the range
393:. So if we pick values of
65:
60:Euler–Jacobi probable prime
49:Miller–Rabin primality test
10:
2854:
2754:Exponentiation by squaring
2437:Continued fraction (CFRAC)
2123:Mathematics of Computation
2088:Mathematics of Computation
1810:Pocklington primality test
1137:Using fast algorithms for
945:Algorithm and running time
719:
45:Baillie–PSW primality test
2801:
2736:
2698:
2665:
2622:
2566:
2523:
2427:
2389:
2298:
2207:SIAM Journal on Computing
2187:SIAM Journal on Computing
1231:} be the Euler liars and
1173:. However, if the input
1187:Euler–Jacobi pseudoprime
979:is composite, otherwise
704:This contrasts with the
444:For every composite odd
73:proved that for any odd
2667:Greatest common divisor
1789:, which is at most 4).
2778:Modular exponentiation
1956:
1820:Average-case behaviour
1735:
1608:
1503:
1139:modular exponentiation
1113:
1031:
931:
892:
832:
793:
735:We randomly select an
695:
647:
576:
550:
499:
360:
250:
205:
165:
2838:Randomized algorithms
2505:Shanks's square forms
2429:Integer factorization
2404:Sieve of Eratosthenes
2158:Randomized Algorithms
1957:
1812:should be used which
1744:This gives that each
1736:
1609:
1504:
1239: = 1,2,...,
1114:
1032:
932:
893:
846:, this time choosing
833:
794:
749:binary exponentiation
706:Fermat primality test
696:
648:
577:
551:
500:
361:
251:
206:
166:
2783:Montgomery reduction
2657:Function field sieve
2632:Baby-step giant-step
2478:Quadratic sieve (QS)
1997:rounds of the test.
1839:
1828:, but those numbers
1624:
1519:
1250:
1161:Accuracy of the test
1054:
998:
906:
867:
807:
768:
657:
586:
575:{\displaystyle n=65}
560:
512:
455:
286:
275:Given an odd number
223:
178:
91:
2793:Trachtenberg system
2759:Integer square root
2700:Modular square root
2419:Wheel factorization
2371:Quadratic Frobenius
2351:Lucas–Lehmer–Riesel
1372:
716:for Fermat's test.
556:. For example, for
2833:Modular arithmetic
2685:Extended Euclidean
2624:Discrete logarithm
2553:Schönhage–Strassen
2409:Sieve of Pritchard
1952:
1731:
1604:
1499:
1338:
1185:is then called an
1109:
1027:
1021:
989:times: choose
927:
922:
888:
883:
828:
823:
789:
784:
714:Carmichael numbers
691:
643:
572:
546:
495:
356:
246:
240:
201:
195:
161:
2815:
2814:
2414:Sieve of Sundaram
2237:978-3-540-40344-9
2167:978-0-521-47465-8
2064:Euler's criterion
1945:
1706:
1617:now we know that
1595:
1559:
1534:
1474:
1449:
1428:
1020:
921:
882:
822:
783:
732:−1)/2=110.
334:
239:
194:
139:
25:Robert M. Solovay
18:Solovay–Strassen
2845:
2764:Integer relation
2737:Other algorithms
2642:Pollard kangaroo
2533:Ancient Egyptian
2391:Prime-generating
2376:Solovay–Strassen
2289:Number-theoretic
2282:
2275:
2268:
2259:
2258:
2252:Solovay-Strassen
2241:
2222:
2202:
2172:
2171:
2153:
2147:
2146:
2129:(203): 177–194.
2118:
2112:
2111:
2094:(173): 259–279.
2083:
2077:
2072:
2066:
2061:
2055:
2054:
2040:Acta Arithmetica
2035:
2014:complexity class
2007:decision problem
1992:
1978:
1961:
1959:
1958:
1953:
1951:
1947:
1946:
1944:
1927:
1894:
1854:
1853:
1792:For purposes of
1740:
1738:
1737:
1732:
1727:
1711:
1707:
1702:
1701:
1700:
1684:
1675:
1674:
1670:
1645:
1644:
1613:
1611:
1610:
1605:
1600:
1596:
1591:
1590:
1589:
1573:
1564:
1560:
1555:
1554:
1545:
1539:
1535:
1527:
1508:
1506:
1505:
1500:
1495:
1479:
1475:
1470:
1469:
1460:
1454:
1450:
1442:
1433:
1429:
1424:
1423:
1414:
1405:
1404:
1400:
1371:
1367:
1346:
1334:
1333:
1329:
1301:
1300:
1296:
1271:
1270:
1119:
1118:
1116:
1115:
1110:
1108:
1086:
1085:
1081:
1046:
1037:
1036:
1034:
1033:
1028:
1026:
1022:
1013:
936:
934:
933:
928:
923:
914:
897:
895:
894:
889:
884:
875:
850: = 2:
837:
835:
834:
829:
824:
815:
798:
796:
795:
790:
785:
776:
700:
698:
697:
692:
690:
689:
680:
672:
667:
652:
650:
649:
644:
581:
579:
578:
573:
555:
553:
552:
547:
545:
544:
535:
527:
522:
504:
502:
501:
496:
494:
493:
484:
476:
471:
379:relatively prime
365:
363:
362:
357:
355:
339:
335:
327:
318:
317:
313:
255:
253:
252:
247:
245:
241:
232:
210:
208:
207:
202:
200:
196:
187:
170:
168:
167:
162:
160:
144:
140:
132:
123:
122:
118:
80:and any integer
2853:
2852:
2848:
2847:
2846:
2844:
2843:
2842:
2828:Primality tests
2818:
2817:
2816:
2811:
2797:
2732:
2694:
2661:
2618:
2562:
2519:
2423:
2385:
2358:Proth's theorem
2300:Primality tests
2294:
2286:
2248:
2238:
2219:10.1137/0207009
2199:10.1137/0206006
2181:
2179:Further reading
2176:
2175:
2168:
2154:
2150:
2135:10.2307/2152945
2119:
2115:
2100:10.2307/2008231
2084:
2080:
2073:
2069:
2062:
2058:
2036:
2032:
2027:
2003:
1984:
1970:
1928:
1895:
1893:
1865:
1861:
1846:
1842:
1840:
1837:
1836:
1822:
1796:the more bases
1765:
1753:gives a number
1752:
1712:
1696:
1692:
1685:
1683:
1679:
1666:
1650:
1646:
1640:
1636:
1625:
1622:
1621:
1585:
1581:
1574:
1572:
1568:
1550:
1546:
1544:
1540:
1526:
1522:
1520:
1517:
1516:
1480:
1465:
1461:
1459:
1455:
1441:
1437:
1419:
1415:
1413:
1409:
1396:
1380:
1376:
1363:
1347:
1342:
1325:
1309:
1305:
1292:
1276:
1272:
1266:
1262:
1251:
1248:
1247:
1230:
1221:
1214:
1163:
1135:
1093:
1077:
1061:
1057:
1055:
1052:
1051:
1050:
1041:
1011:
1007:
999:
996:
995:
994:
947:
912:
907:
904:
903:
873:
868:
865:
864:
813:
808:
805:
804:
774:
769:
766:
765:
722:
685:
681:
676:
668:
663:
658:
655:
654:
587:
584:
583:
561:
558:
557:
540:
536:
531:
523:
518:
513:
510:
509:
489:
485:
480:
472:
467:
456:
453:
452:
340:
326:
322:
309:
293:
289:
287:
284:
283:
230:
226:
224:
221:
220:
213:Legendre symbol
185:
181:
179:
176:
175:
145:
131:
127:
114:
98:
94:
92:
89:
88:
68:
29:Volker Strassen
23:, developed by
12:
11:
5:
2851:
2841:
2840:
2835:
2830:
2813:
2812:
2810:
2809:
2802:
2799:
2798:
2796:
2795:
2790:
2785:
2780:
2775:
2761:
2756:
2751:
2746:
2740:
2738:
2734:
2733:
2731:
2730:
2725:
2720:
2718:Tonelli–Shanks
2715:
2710:
2704:
2702:
2696:
2695:
2693:
2692:
2687:
2682:
2677:
2671:
2669:
2663:
2662:
2660:
2659:
2654:
2652:Index calculus
2649:
2647:Pohlig–Hellman
2644:
2639:
2634:
2628:
2626:
2620:
2619:
2617:
2616:
2611:
2606:
2601:
2599:Newton-Raphson
2596:
2591:
2586:
2581:
2575:
2573:
2564:
2563:
2561:
2560:
2555:
2550:
2545:
2540:
2535:
2529:
2527:
2525:Multiplication
2521:
2520:
2518:
2517:
2512:
2510:Trial division
2507:
2502:
2497:
2495:Rational sieve
2492:
2485:
2480:
2475:
2467:
2459:
2454:
2449:
2444:
2439:
2433:
2431:
2425:
2424:
2422:
2421:
2416:
2411:
2406:
2401:
2399:Sieve of Atkin
2395:
2393:
2387:
2386:
2384:
2383:
2378:
2373:
2368:
2361:
2354:
2347:
2340:
2335:
2330:
2325:
2323:Elliptic curve
2320:
2315:
2310:
2304:
2302:
2296:
2295:
2285:
2284:
2277:
2270:
2262:
2256:
2255:
2247:
2246:External links
2244:
2243:
2242:
2236:
2223:
2180:
2177:
2174:
2173:
2166:
2148:
2113:
2078:
2067:
2056:
2029:
2028:
2026:
2023:
2002:
1999:
1963:
1962:
1950:
1943:
1940:
1937:
1934:
1931:
1926:
1923:
1920:
1917:
1914:
1911:
1908:
1904:
1901:
1898:
1892:
1889:
1886:
1883:
1880:
1877:
1874:
1871:
1868:
1864:
1860:
1857:
1852:
1849:
1845:
1821:
1818:
1761:
1748:
1742:
1741:
1730:
1726:
1723:
1719:
1716:
1710:
1705:
1699:
1695:
1691:
1688:
1682:
1678:
1673:
1669:
1665:
1662:
1659:
1656:
1653:
1649:
1643:
1639:
1635:
1632:
1629:
1615:
1614:
1603:
1599:
1594:
1588:
1584:
1580:
1577:
1571:
1567:
1563:
1558:
1553:
1549:
1543:
1538:
1533:
1530:
1525:
1510:
1509:
1498:
1494:
1491:
1487:
1484:
1478:
1473:
1468:
1464:
1458:
1453:
1448:
1445:
1440:
1436:
1432:
1427:
1422:
1418:
1412:
1408:
1403:
1399:
1395:
1392:
1389:
1386:
1383:
1379:
1375:
1370:
1366:
1362:
1359:
1356:
1353:
1350:
1345:
1341:
1337:
1332:
1328:
1324:
1321:
1318:
1315:
1312:
1308:
1304:
1299:
1295:
1291:
1288:
1285:
1282:
1279:
1275:
1269:
1265:
1261:
1258:
1255:
1226:
1219:
1212:
1179:probably prime
1171:probably prime
1162:
1159:
1133:probably prime
1107:
1104:
1100:
1097:
1092:
1089:
1084:
1080:
1076:
1073:
1070:
1067:
1064:
1060:
1045: = 0
1025:
1019:
1016:
1010:
1006:
1003:
981:probably prime
955:
946:
943:
939:
938:
926:
920:
917:
911:
902: =
887:
881:
878:
872:
862:
840:
839:
827:
821:
818:
812:
803: =
788:
782:
779:
773:
763:
751:, we compute:
721:
718:
701:has order 48.
688:
684:
679:
675:
671:
666:
662:
642:
639:
636:
633:
630:
627:
624:
621:
618:
615:
612:
609:
606:
603:
600:
597:
594:
591:
571:
568:
565:
543:
539:
534:
530:
526:
521:
517:
506:
505:
492:
488:
483:
479:
475:
470:
466:
463:
460:
441:is composite.
367:
366:
354:
351:
347:
344:
338:
333:
330:
325:
321:
316:
312:
308:
305:
302:
299:
296:
292:
244:
238:
235:
229:
199:
193:
190:
184:
172:
171:
159:
156:
152:
149:
143:
138:
135:
130:
126:
121:
117:
113:
110:
107:
104:
101:
97:
67:
64:
41:probably prime
31:in 1977, is a
20:primality test
9:
6:
4:
3:
2:
2850:
2839:
2836:
2834:
2831:
2829:
2826:
2825:
2823:
2807:
2804:
2803:
2800:
2794:
2791:
2789:
2786:
2784:
2781:
2779:
2776:
2773:
2769:
2765:
2762:
2760:
2757:
2755:
2752:
2750:
2747:
2745:
2742:
2741:
2739:
2735:
2729:
2726:
2724:
2721:
2719:
2716:
2714:
2713:Pocklington's
2711:
2709:
2706:
2705:
2703:
2701:
2697:
2691:
2688:
2686:
2683:
2681:
2678:
2676:
2673:
2672:
2670:
2668:
2664:
2658:
2655:
2653:
2650:
2648:
2645:
2643:
2640:
2638:
2635:
2633:
2630:
2629:
2627:
2625:
2621:
2615:
2612:
2610:
2607:
2605:
2602:
2600:
2597:
2595:
2592:
2590:
2587:
2585:
2582:
2580:
2577:
2576:
2574:
2572:
2569:
2565:
2559:
2556:
2554:
2551:
2549:
2546:
2544:
2541:
2539:
2536:
2534:
2531:
2530:
2528:
2526:
2522:
2516:
2513:
2511:
2508:
2506:
2503:
2501:
2498:
2496:
2493:
2491:
2490:
2486:
2484:
2481:
2479:
2476:
2474:
2472:
2468:
2466:
2464:
2460:
2458:
2457:Pollard's rho
2455:
2453:
2450:
2448:
2445:
2443:
2440:
2438:
2435:
2434:
2432:
2430:
2426:
2420:
2417:
2415:
2412:
2410:
2407:
2405:
2402:
2400:
2397:
2396:
2394:
2392:
2388:
2382:
2379:
2377:
2374:
2372:
2369:
2367:
2366:
2362:
2360:
2359:
2355:
2353:
2352:
2348:
2346:
2345:
2341:
2339:
2336:
2334:
2331:
2329:
2326:
2324:
2321:
2319:
2316:
2314:
2311:
2309:
2306:
2305:
2303:
2301:
2297:
2293:
2290:
2283:
2278:
2276:
2271:
2269:
2264:
2263:
2260:
2253:
2250:
2249:
2239:
2233:
2229:
2224:
2220:
2216:
2212:
2208:
2200:
2196:
2192:
2188:
2183:
2182:
2169:
2163:
2159:
2152:
2144:
2140:
2136:
2132:
2128:
2124:
2117:
2109:
2105:
2101:
2097:
2093:
2089:
2082:
2076:
2071:
2065:
2060:
2053:
2049:
2045:
2041:
2034:
2030:
2022:
2020:
2019:
2015:
2011:
2008:
1998:
1996:
1991:
1987:
1982:
1977:
1973:
1968:
1948:
1941:
1938:
1935:
1932:
1929:
1924:
1921:
1918:
1915:
1912:
1909:
1906:
1902:
1899:
1896:
1884:
1878:
1875:
1872:
1866:
1862:
1858:
1855:
1850:
1847:
1843:
1835:
1834:
1833:
1831:
1827:
1817:
1815:
1811:
1807:
1803:
1799:
1795:
1790:
1788:
1783:
1781:
1777:
1773:
1769:
1764:
1760:
1756:
1751:
1747:
1728:
1721:
1717:
1708:
1703:
1697:
1693:
1689:
1686:
1680:
1676:
1671:
1667:
1660:
1657:
1654:
1641:
1637:
1633:
1630:
1620:
1619:
1618:
1601:
1597:
1592:
1586:
1582:
1578:
1575:
1569:
1565:
1561:
1556:
1551:
1547:
1541:
1536:
1531:
1528:
1523:
1515:
1514:
1513:
1496:
1489:
1485:
1476:
1471:
1466:
1462:
1456:
1451:
1446:
1443:
1438:
1434:
1430:
1425:
1420:
1416:
1410:
1406:
1401:
1397:
1390:
1387:
1384:
1377:
1373:
1368:
1364:
1357:
1354:
1351:
1343:
1339:
1335:
1330:
1326:
1319:
1316:
1313:
1306:
1302:
1297:
1293:
1286:
1283:
1280:
1267:
1263:
1259:
1256:
1246:
1245:
1244:
1242:
1238:
1234:
1229:
1225:
1218:
1211:
1207:
1203:
1199:
1195:
1190:
1188:
1184:
1181:. The number
1180:
1176:
1172:
1168:
1158:
1156:
1152:
1148:
1144:
1140:
1134:
1131:
1128:
1125:
1122:
1102:
1098:
1090:
1087:
1082:
1078:
1071:
1068:
1065:
1058:
1049:
1044:
1040:
1023:
1017:
1014:
1008:
1001:
992:
988:
985:
982:
978:
974:
970:
966:
962:
958:
954:
952:
942:
918:
915:
901:
879:
876:
863:
860:
856:
853:
852:
851:
849:
845:
819:
816:
802:
780:
777:
764:
761:
757:
754:
753:
752:
750:
746:
742:
738:
733:
731:
727:
717:
715:
711:
707:
702:
686:
673:
669:
637:
634:
631:
628:
625:
622:
619:
616:
613:
610:
607:
604:
601:
598:
595:
589:
569:
566:
563:
541:
528:
524:
490:
477:
473:
461:
458:
451:
450:
449:
447:
442:
440:
436:
432:
429:is called an
428:
424:
420:
416:
415:Euler witness
413:is called an
412:
409:). This base
408:
404:
400:
396:
392:
388:
384:
380:
376:
373:, given that
372:
349:
345:
336:
331:
328:
323:
319:
314:
310:
303:
300:
297:
290:
282:
281:
280:
278:
273:
271:
267:
263:
259:
242:
236:
233:
227:
218:
217:Jacobi symbol
214:
197:
191:
188:
182:
154:
150:
141:
136:
133:
128:
124:
119:
115:
108:
105:
102:
95:
87:
86:
85:
83:
79:
76:
72:
63:
61:
57:
54:
50:
46:
42:
38:
34:
33:probabilistic
30:
26:
22:
21:
2805:
2487:
2470:
2462:
2381:Miller–Rabin
2375:
2363:
2356:
2349:
2344:Lucas–Lehmer
2342:
2227:
2210:
2206:
2193:(1): 84–85.
2190:
2186:
2157:
2151:
2126:
2122:
2116:
2091:
2087:
2081:
2070:
2059:
2043:
2039:
2033:
2016:
2009:
2004:
1994:
1989:
1985:
1980:
1975:
1971:
1966:
1964:
1829:
1825:
1823:
1813:
1801:
1797:
1794:cryptography
1791:
1784:
1779:
1775:
1771:
1767:
1762:
1758:
1754:
1749:
1745:
1743:
1616:
1511:
1240:
1236:
1232:
1227:
1223:
1216:
1209:
1205:
1201:
1197:
1193:
1191:
1182:
1178:
1174:
1170:
1166:
1164:
1154:
1150:
1146:
1142:
1136:
1132:
1129:
1126:
1123:
1120:
1047:
1042:
1038:
990:
986:
983:
980:
976:
972:
968:
964:
960:
956:
953:as follows:
948:
940:
899:
858:
854:
847:
843:
841:
800:
759:
755:
744:
740:
736:
734:
729:
725:
723:
709:
703:
507:
445:
443:
438:
434:
430:
426:
422:
418:
414:
410:
406:
402:
398:
394:
390:
386:
382:
374:
370:
368:
276:
274:
265:
257:
173:
81:
77:
75:prime number
69:
56:cryptosystem
17:
15:
2637:Pollard rho
2594:Goldschmidt
2328:Pocklington
2318:Baillie–PSW
2046:: 355–364,
1816:primality.
425:. The base
264:((log
2822:Categories
2749:Cornacchia
2744:Chakravala
2292:algorithms
2213:(1): 118.
2025:References
2012:is in the
2001:Complexity
951:pseudocode
747:) such as
431:Euler liar
2723:Berlekamp
2680:Euclidean
2568:Euclidean
2548:Toom–Cook
2543:Karatsuba
2203:See also
2010:COMPOSITE
1939:
1933:
1922:
1916:
1910:
1900:
1867:−
1859:
1848:−
1774:with gcd(
1690:⋅
1658:−
1634:⋅
1579:⋅
1407:⋅
1388:−
1355:−
1336:⋅
1317:−
1284:−
1260:⋅
1200:with gcd(
1157:we test.
1149:), where
1127:composite
1069:−
1005:←
973:composite
687:∗
542:∗
491:∗
462:∈
320:≡
301:−
125:≡
106:−
37:composite
2690:Lehmer's
2584:Chunking
2571:division
2500:Fermat's
1677:≢
1435:≢
1088:≢
256:, where
66:Concepts
47:and the
2806:Italics
2728:Kunerth
2708:Cipolla
2589:Fourier
2558:Fürer's
2452:Euler's
2442:Dixon's
2365:Pépin's
2143:2152945
2108:2008231
2052:0213289
1808:or the
1222:, ...,
720:Example
211:is the
2788:Schoof
2675:Binary
2579:Binary
2515:Shor's
2333:Fermat
2234:
2164:
2141:
2106:
2050:
1814:proves
1130:return
1124:return
984:repeat
969:output
957:inputs
653:, and
385:. If
215:. The
174:where
62:test.
2609:Short
2338:Lucas
2139:JSTOR
2104:JSTOR
1192:When
1145:·log
71:Euler
2604:Long
2538:Long
2232:ISBN
2162:ISBN
1965:for
1806:ECPP
1121:then
898:mod
857:mod
799:mod
758:mod
433:for
417:for
27:and
16:The
2768:LLL
2614:SRT
2473:+ 1
2465:− 1
2313:APR
2308:AKS
2215:doi
2195:doi
2131:doi
2096:doi
1936:log
1930:log
1919:log
1913:log
1907:log
1897:log
1856:exp
1718:mod
1486:mod
1099:mod
975:if
919:221
820:221
381:to
377:is
346:mod
151:mod
53:RSA
39:or
2824::
2772:KZ
2770:;
2209:.
2189:.
2137:.
2127:61
2125:.
2102:.
2092:46
2090:.
2048:MR
2044:12
2042:,
2021:.
2018:RP
1988:≤
1974:≤
1243::
1215:,
1189:.
1048:or
1039:if
971::
959::
817:47
638:64
632:57
626:51
620:47
614:18
608:14
570:65
272:.
84:,
2774:)
2766:(
2471:p
2463:p
2281:e
2274:t
2267:v
2240:.
2221:.
2217::
2211:7
2201:.
2197::
2191:6
2170:.
2145:.
2133::
2110:.
2098::
1995:k
1990:x
1986:n
1981:n
1976:x
1972:n
1967:k
1949:)
1942:x
1925:x
1903:x
1891:)
1888:)
1885:1
1882:(
1879:o
1876:+
1873:1
1870:(
1863:(
1851:k
1844:2
1830:n
1826:n
1802:k
1798:a
1780:n
1778:,
1776:a
1772:a
1768:n
1763:i
1759:a
1757:·
1755:a
1750:i
1746:a
1729:.
1725:)
1722:n
1715:(
1709:)
1704:n
1698:i
1694:a
1687:a
1681:(
1672:2
1668:/
1664:)
1661:1
1655:n
1652:(
1648:)
1642:i
1638:a
1631:a
1628:(
1602:,
1598:)
1593:n
1587:i
1583:a
1576:a
1570:(
1566:=
1562:)
1557:n
1552:i
1548:a
1542:(
1537:)
1532:n
1529:a
1524:(
1497:.
1493:)
1490:n
1483:(
1477:)
1472:n
1467:i
1463:a
1457:(
1452:)
1447:n
1444:a
1439:(
1431:)
1426:n
1421:i
1417:a
1411:(
1402:2
1398:/
1394:)
1391:1
1385:n
1382:(
1378:a
1374:=
1369:2
1365:/
1361:)
1358:1
1352:n
1349:(
1344:i
1340:a
1331:2
1327:/
1323:)
1320:1
1314:n
1311:(
1307:a
1303:=
1298:2
1294:/
1290:)
1287:1
1281:n
1278:(
1274:)
1268:i
1264:a
1257:a
1254:(
1241:m
1237:i
1233:a
1228:m
1224:a
1220:2
1217:a
1213:1
1210:a
1206:n
1204:,
1202:a
1198:a
1194:n
1183:n
1175:n
1167:n
1155:a
1151:k
1147:n
1143:k
1106:)
1103:n
1096:(
1091:x
1083:2
1079:/
1075:)
1072:1
1066:n
1063:(
1059:a
1043:x
1024:)
1018:n
1015:a
1009:(
1002:x
991:a
987:k
977:n
965:k
961:n
925:)
916:2
910:(
900:n
886:)
880:n
877:a
871:(
859:n
855:a
848:a
844:a
826:)
811:(
801:n
787:)
781:n
778:a
772:(
760:n
756:a
745:n
741:n
737:a
730:n
726:n
710:n
683:)
678:Z
674:n
670:/
665:Z
661:(
641:}
635:,
629:,
623:,
617:,
611:,
605:,
602:8
599:,
596:1
593:{
590:=
567:=
564:n
538:)
533:Z
529:n
525:/
520:Z
516:(
487:)
482:Z
478:n
474:/
469:Z
465:(
459:a
446:n
439:n
435:n
427:a
423:n
419:n
411:a
407:n
403:n
399:a
395:a
391:a
387:n
383:n
375:a
371:a
353:)
350:n
343:(
337:)
332:n
329:a
324:(
315:2
311:/
307:)
304:1
298:n
295:(
291:a
277:n
266:n
262:O
258:n
243:)
237:n
234:a
228:(
198:)
192:p
189:a
183:(
158:)
155:p
148:(
142:)
137:p
134:a
129:(
120:2
116:/
112:)
109:1
103:p
100:(
96:a
82:a
78:p
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.