971:
are Fermat liars. For these numbers, repeated application of the Fermat primality test performs the same as a simple random search for factors. While
Carmichael numbers are substantially rarer than prime numbers (Erdös' upper bound for the number of Carmichael numbers is lower than the
1476:
As an exception, OpenPFGW uses only the Fermat test for probable prime testing. The program is typically used with multi-thousand digit inputs with a goal of maximum speed with very large inputs. Another well known program that relies only on the Fermat test is
1354:
2383:
652:
565:
1066:
771:
456:
1110:
969:
120:
368:
2387:
257:
208:
1895:
1223:
303:
1390:
1440:
1928:
1710:
1215:
1188:
1161:
976:) there are enough of them that Fermat's primality test is not often used in the above form. Instead, other more powerful extensions of the Fermat test, such as
1134:
1009:
925:
901:
1473:
In practice with most big number libraries such as GMP, the Fermat test is not noticeably faster than a MillerâRabin test, and can be slower for many inputs.
1836:
1831:
1742:
1805:
2252:
1888:
1459:
1800:
2120:
2062:
1881:
1991:
1458:
test for primality. Sometimes a Fermat test (along with some trial division by small primes) is performed first to improve performance.
985:
580:
2168:
1841:
1815:
1966:
1694:
2077:
2115:
2052:
1996:
1959:
1451:
981:
860:
2257:
2148:
2067:
2057:
1860:
1785:
1933:
1455:
977:
2085:
2338:
499:
1017:
2333:
2262:
2163:
2300:
2214:
657:
So 221 is composite and 38 was indeed a Fermat liar. Furthermore, 24 is a Fermat witness for the compositeness of 221.
2448:
721:
406:
1735:
2379:
2369:
2328:
2104:
2098:
2072:
1943:
1780:
1684:
46:
2364:
2305:
1728:
1071:
930:
67:
318:
2443:
2267:
2140:
1986:
1938:
1765:
2282:
2173:
1513:
1462:
since version 3.0 uses a base-210 Fermat test after trial division and before running MillerâRabin tests.
217:
2393:
2343:
2323:
1852:
1650:
813:
171:
1349:{\displaystyle (a\cdot a_{i})^{n-1}\equiv a^{n-1}\cdot a_{i}^{n-1}\equiv a^{n-1}\not \equiv 1{\pmod {n}}}
2044:
2019:
1580:
2403:
1775:
2398:
2290:
2272:
2247:
2209:
1953:
1672:
1481:
where it is only used for testing of self-generated large random values (an open source counterpart,
973:
31:
1655:
2408:
2374:
2295:
2199:
2158:
2153:
2130:
2034:
1478:
270:
1362:
2239:
2186:
2183:
2024:
1923:
1790:
1704:
1597:
1560:
1542:
1395:
872:
386:
211:
1980:
1973:
1810:
20:
2359:
2315:
2029:
2006:
1690:
1509:
1482:
880:
2204:
1751:
1676:
1668:
1589:
1564:
1532:
1631:
1193:
1166:
1139:
2194:
2093:
1627:
2224:
2125:
2110:
2014:
1915:
1680:
1572:
1568:
1505:
1119:
994:
910:
886:
834:
818:
162:
35:
1537:
2437:
2219:
1904:
1770:
1615:
2229:
1846:
1795:
1011:
is a composite number that is not a
Carmichael number, then at least half of all
1873:
1517:
153:
is composite. Therefore, if the equality does hold for one or more values of
1907:
1463:
816:
and multiprecision multiplication, the running time of this algorithm is
137:
and see whether the congruence holds. If it does not hold for a value of
1601:
1546:
1467:
684:: a parameter that determines the number of times to test for primality
493: = 38. We check the above congruence and find that it holds:
263:
is odd, for the same reason. That is why one usually chooses a random
1593:
647:{\displaystyle a^{n-1}=24^{220}\equiv 81\not \equiv 1{\pmod {221}}.}
1720:
19:
For the test for determining whether a Fermat number is prime, see
1689:(Second ed.). MIT Press; McGraw-Hill. p. 889–890.
570:
Either 221 is prime, or 38 is a Fermat liar, so we take another
1877:
1724:
145:
is composite. This congruence is unlikely to hold for a random
1647:
1466:
uses a similar process with base 2 for the Fermat test, but
168:
However, note that the above congruence holds trivially for
1485:, uses a Fermat pretest followed by MillerâRabin tests).
2424:
indicate that algorithm is for numbers of special forms
560:{\displaystyle a^{n-1}=38^{220}\equiv 1{\pmod {221}}.}
1398:
1365:
1226:
1196:
1169:
1142:
1122:
1074:
1061:{\displaystyle a\in (\mathbb {Z} /n\mathbb {Z} )^{*}}
1020:
997:
933:
913:
889:
724:
583:
502:
409:
321:
273:
220:
174:
70:
2352:
2314:
2281:
2238:
2182:
2139:
2043:
2005:
1914:
1824:
1758:
1618:(1956). "On pseudoprimes and Carmichael numbers".
1434:
1384:
1348:
1209:
1182:
1155:
1128:
1104:
1060:
1003:
963:
919:
895:
765:
646:
559:
450:
362:
297:
251:
202:
114:
859:is the value we want to test for primality; see
804:respectively, hence testing them adds no value.
485: = 221 is prime. Randomly pick 1 <
766:{\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}
451:{\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}
1573:"There are Infinitely Many Carmichael Numbers"
1116:are Fermat witnesses. For proof of this, let
879:> 1. Even worse, there are infinitely many
796:-1 are not used as the equality holds for all
1889:
1736:
8:
1709:: CS1 maint: multiple names: authors list (
1450:As mentioned above, most applications use a
1832:List of things named after Pierre de Fermat
1683:(2001). "Section 31.8: Primality testing".
1105:{\displaystyle \operatorname {gcd} (a,n)=1}
964:{\displaystyle \operatorname {gcd} (a,n)=1}
129:is prime, then we can pick random integers
115:{\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}
1896:
1882:
1874:
1743:
1729:
1721:
363:{\displaystyle a^{n-1}\equiv 1{\pmod {n}}}
1654:
1536:
1397:
1376:
1364:
1330:
1312:
1293:
1288:
1269:
1250:
1240:
1225:
1201:
1195:
1174:
1168:
1147:
1141:
1121:
1073:
1052:
1044:
1043:
1035:
1031:
1030:
1019:
996:
932:
912:
888:
747:
729:
723:
665:The algorithm can be written as follows:
625:
607:
588:
582:
538:
526:
507:
501:
432:
414:
408:
344:
326:
320:
272:
233:
219:
184:
173:
93:
75:
69:
851:is the number of times we test a random
34:test to determine whether a number is a
1806:Fermat's theorem on sums of two squares
1494:
781:If composite is never returned: return
1837:Wiles's proof of Fermat's Last Theorem
1702:
1500:
1498:
481:Suppose we wish to determine whether
252:{\displaystyle a\equiv -1{\pmod {p}}}
210:, because the congruence relation is
7:
1801:Fermat's theorem (stationary points)
203:{\displaystyle a\equiv 1{\pmod {p}}}
1338:
755:
633:
546:
440:
352:
241:
192:
101:
14:
2105:Special number field sieve (SNFS)
2099:General number field sieve (GNFS)
1538:10.1090/S0025-5718-1980-0572872-7
676:: a value to test for primality,
1842:Fermat's Last Theorem in fiction
1816:Fermat's right triangle theorem
1786:Fermat polygonal number theorem
1331:
748:
626:
539:
433:
345:
234:
185:
94:
1342:
1332:
1247:
1227:
1093:
1081:
1049:
1027:
974:prime number function n/log(n)
952:
940:
759:
749:
637:
627:
550:
540:
444:
434:
356:
346:
245:
235:
214:. It also holds trivially for
212:compatible with exponentiation
196:
186:
105:
95:
1:
298:{\displaystyle 1<a<p-1}
125:If one wants to test whether
2063:Lenstra elliptic curve (ECM)
1385:{\displaystyle a\cdot a_{i}}
16:Probabilistic primality test
1518:"The pseudoprimes to 25·10"
1435:{\displaystyle i=1,2,...,s}
861:MillerâRabin primality test
377:is composite is known as a
2465:
2370:Exponentiation by squaring
2053:Continued fraction (CFRAC)
1686:Introduction to Algorithms
1525:Mathematics of Computation
871:There are infinitely many
812:Using fast algorithms for
18:
2417:
469:for the compositeness of
1136:be a Fermat witness and
988:are more commonly used.
698:is composite, otherwise
2283:Greatest common divisor
1781:Fermat's little theorem
1514:Samuel S. Wagstaff, Jr.
1217:be Fermat liars. Then
47:Fermat's little theorem
2394:Modular exponentiation
1864:(popular science book)
1442:are Fermat witnesses.
1436:
1386:
1350:
1211:
1184:
1157:
1130:
1106:
1062:
1005:
965:
921:
897:
814:modular exponentiation
767:
715:randomly in the range
648:
561:
452:
364:
299:
253:
204:
116:
2121:Shanks's square forms
2045:Integer factorization
2020:Sieve of Eratosthenes
1861:Fermat's Last Theorem
1766:Fermat's Last Theorem
1581:Annals of Mathematics
1437:
1387:
1351:
1212:
1210:{\displaystyle a_{s}}
1185:
1183:{\displaystyle a_{2}}
1158:
1156:{\displaystyle a_{1}}
1131:
1107:
1063:
1006:
966:
922:
898:
768:
649:
562:
453:
365:
300:
254:
205:
117:
28:Fermat primality test
2399:Montgomery reduction
2273:Function field sieve
2248:Baby-step giant-step
2094:Quadratic sieve (QS)
1673:Charles E. Leiserson
1620:Publ. Math. Debrecen
1396:
1363:
1224:
1194:
1167:
1140:
1120:
1072:
1018:
995:
931:
911:
887:
883:. These are numbers
722:
581:
500:
407:
319:
271:
218:
172:
68:
57:is not divisible by
2409:Trachtenberg system
2375:Integer square root
2316:Modular square root
2035:Wheel factorization
1987:Quadratic Frobenius
1967:LucasâLehmerâRiesel
1853:Fermat's Last Tango
1304:
875:to any given basis
873:Fermat pseudoprimes
157:, then we say that
2449:Modular arithmetic
2301:Extended Euclidean
2240:Discrete logarithm
2169:SchönhageâStrassen
2025:Sieve of Pritchard
1791:Fermat pseudoprime
1776:Fermat's principle
1531:(151): 1003â1026.
1432:
1382:
1346:
1284:
1207:
1180:
1153:
1126:
1102:
1058:
1001:
961:
917:
893:
881:Carmichael numbers
763:
644:
557:
448:
387:Fermat pseudoprime
360:
295:
249:
200:
112:
2431:
2430:
2030:Sieve of Sundaram
1871:
1870:
1645:Joe Hurd (2003),
1565:Granville, Andrew
1510:John L. Selfridge
1483:GNU Privacy Guard
1129:{\displaystyle a}
1004:{\displaystyle n}
920:{\displaystyle a}
896:{\displaystyle n}
396:If we do pick an
133:not divisible by
2456:
2380:Integer relation
2353:Other algorithms
2258:Pollard kangaroo
2149:Ancient Egyptian
2007:Prime-generating
1992:SolovayâStrassen
1905:Number-theoretic
1898:
1891:
1884:
1875:
1752:Pierre de Fermat
1745:
1738:
1731:
1722:
1714:
1708:
1700:
1677:Ronald L. Rivest
1669:Thomas H. Cormen
1660:
1659:
1658:
1642:
1636:
1635:
1612:
1606:
1605:
1577:
1557:
1551:
1550:
1540:
1522:
1502:
1441:
1439:
1438:
1433:
1391:
1389:
1388:
1383:
1381:
1380:
1355:
1353:
1352:
1347:
1345:
1323:
1322:
1303:
1292:
1280:
1279:
1261:
1260:
1245:
1244:
1216:
1214:
1213:
1208:
1206:
1205:
1189:
1187:
1186:
1181:
1179:
1178:
1162:
1160:
1159:
1154:
1152:
1151:
1135:
1133:
1132:
1127:
1111:
1109:
1108:
1103:
1067:
1065:
1064:
1059:
1057:
1056:
1047:
1039:
1034:
1010:
1008:
1007:
1002:
986:SolovayâStrassen
970:
968:
967:
962:
926:
924:
923:
918:
902:
900:
899:
894:
846:
772:
770:
769:
764:
762:
740:
739:
653:
651:
650:
645:
640:
612:
611:
599:
598:
566:
564:
563:
558:
553:
531:
530:
518:
517:
457:
455:
454:
449:
447:
425:
424:
369:
367:
366:
361:
359:
337:
336:
304:
302:
301:
296:
267:in the interval
258:
256:
255:
250:
248:
209:
207:
206:
201:
199:
121:
119:
118:
113:
108:
86:
85:
2464:
2463:
2459:
2458:
2457:
2455:
2454:
2453:
2444:Primality tests
2434:
2433:
2432:
2427:
2413:
2348:
2310:
2277:
2234:
2178:
2135:
2039:
2001:
1974:Proth's theorem
1916:Primality tests
1910:
1902:
1872:
1867:
1820:
1811:Fermat's spiral
1754:
1749:
1718:
1701:
1697:
1667:
1664:
1663:
1656:10.1.1.105.3196
1644:
1643:
1639:
1614:
1613:
1609:
1594:10.2307/2118576
1575:
1569:Pomerance, Carl
1559:
1558:
1554:
1520:
1504:
1503:
1496:
1491:
1448:
1394:
1393:
1372:
1361:
1360:
1308:
1265:
1246:
1236:
1222:
1221:
1197:
1192:
1191:
1170:
1165:
1164:
1143:
1138:
1137:
1118:
1117:
1070:
1069:
1048:
1016:
1015:
993:
992:
991:In general, if
929:
928:
909:
908:
885:
884:
869:
817:
810:
725:
720:
719:
663:
603:
584:
579:
578:
522:
503:
498:
497:
479:
410:
405:
404:
381:. In this case
322:
317:
316:
269:
268:
216:
215:
170:
169:
71:
66:
65:
49:states that if
44:
24:
17:
12:
11:
5:
2462:
2460:
2452:
2451:
2446:
2436:
2435:
2429:
2428:
2426:
2425:
2418:
2415:
2414:
2412:
2411:
2406:
2401:
2396:
2391:
2377:
2372:
2367:
2362:
2356:
2354:
2350:
2349:
2347:
2346:
2341:
2336:
2334:TonelliâShanks
2331:
2326:
2320:
2318:
2312:
2311:
2309:
2308:
2303:
2298:
2293:
2287:
2285:
2279:
2278:
2276:
2275:
2270:
2268:Index calculus
2265:
2263:PohligâHellman
2260:
2255:
2250:
2244:
2242:
2236:
2235:
2233:
2232:
2227:
2222:
2217:
2215:Newton-Raphson
2212:
2207:
2202:
2197:
2191:
2189:
2180:
2179:
2177:
2176:
2171:
2166:
2161:
2156:
2151:
2145:
2143:
2141:Multiplication
2137:
2136:
2134:
2133:
2128:
2126:Trial division
2123:
2118:
2113:
2111:Rational sieve
2108:
2101:
2096:
2091:
2083:
2075:
2070:
2065:
2060:
2055:
2049:
2047:
2041:
2040:
2038:
2037:
2032:
2027:
2022:
2017:
2015:Sieve of Atkin
2011:
2009:
2003:
2002:
2000:
1999:
1994:
1989:
1984:
1977:
1970:
1963:
1956:
1951:
1946:
1941:
1939:Elliptic curve
1936:
1931:
1926:
1920:
1918:
1912:
1911:
1903:
1901:
1900:
1893:
1886:
1878:
1869:
1868:
1866:
1865:
1857:
1856:(2000 musical)
1849:
1844:
1839:
1834:
1828:
1826:
1822:
1821:
1819:
1818:
1813:
1808:
1803:
1798:
1793:
1788:
1783:
1778:
1773:
1768:
1762:
1760:
1756:
1755:
1750:
1748:
1747:
1740:
1733:
1725:
1716:
1715:
1695:
1681:Clifford Stein
1662:
1661:
1637:
1607:
1588:(3): 703â722.
1552:
1506:Carl Pomerance
1493:
1492:
1490:
1487:
1447:
1444:
1431:
1428:
1425:
1422:
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1379:
1375:
1371:
1368:
1357:
1356:
1344:
1341:
1337:
1334:
1329:
1326:
1321:
1318:
1315:
1311:
1307:
1302:
1299:
1296:
1291:
1287:
1283:
1278:
1275:
1272:
1268:
1264:
1259:
1256:
1253:
1249:
1243:
1239:
1235:
1232:
1229:
1204:
1200:
1177:
1173:
1150:
1146:
1125:
1114:
1113:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1077:
1055:
1051:
1046:
1042:
1038:
1033:
1029:
1026:
1023:
1000:
960:
957:
954:
951:
948:
945:
942:
939:
936:
916:
906:
892:
868:
865:
809:
806:
786:
785:
783:probably prime
779:
778:
777:
773:, then return
761:
758:
754:
751:
746:
743:
738:
735:
732:
728:
716:
702:
700:probably prime
685:
662:
659:
655:
654:
643:
639:
636:
632:
629:
624:
621:
618:
615:
610:
606:
602:
597:
594:
591:
587:
568:
567:
556:
552:
549:
545:
542:
537:
534:
529:
525:
521:
516:
513:
510:
506:
489:< 220, say
478:
475:
467:Fermat witness
465:is known as a
459:
458:
446:
443:
439:
436:
431:
428:
423:
420:
417:
413:
371:
370:
358:
355:
351:
348:
343:
340:
335:
332:
329:
325:
294:
291:
288:
285:
282:
279:
276:
247:
244:
240:
237:
232:
229:
226:
223:
198:
195:
191:
188:
183:
180:
177:
163:probably prime
123:
122:
111:
107:
104:
100:
97:
92:
89:
84:
81:
78:
74:
43:
40:
36:probable prime
15:
13:
10:
9:
6:
4:
3:
2:
2461:
2450:
2447:
2445:
2442:
2441:
2439:
2423:
2420:
2419:
2416:
2410:
2407:
2405:
2402:
2400:
2397:
2395:
2392:
2389:
2385:
2381:
2378:
2376:
2373:
2371:
2368:
2366:
2363:
2361:
2358:
2357:
2355:
2351:
2345:
2342:
2340:
2337:
2335:
2332:
2330:
2329:Pocklington's
2327:
2325:
2322:
2321:
2319:
2317:
2313:
2307:
2304:
2302:
2299:
2297:
2294:
2292:
2289:
2288:
2286:
2284:
2280:
2274:
2271:
2269:
2266:
2264:
2261:
2259:
2256:
2254:
2251:
2249:
2246:
2245:
2243:
2241:
2237:
2231:
2228:
2226:
2223:
2221:
2218:
2216:
2213:
2211:
2208:
2206:
2203:
2201:
2198:
2196:
2193:
2192:
2190:
2188:
2185:
2181:
2175:
2172:
2170:
2167:
2165:
2162:
2160:
2157:
2155:
2152:
2150:
2147:
2146:
2144:
2142:
2138:
2132:
2129:
2127:
2124:
2122:
2119:
2117:
2114:
2112:
2109:
2107:
2106:
2102:
2100:
2097:
2095:
2092:
2090:
2088:
2084:
2082:
2080:
2076:
2074:
2073:Pollard's rho
2071:
2069:
2066:
2064:
2061:
2059:
2056:
2054:
2051:
2050:
2048:
2046:
2042:
2036:
2033:
2031:
2028:
2026:
2023:
2021:
2018:
2016:
2013:
2012:
2010:
2008:
2004:
1998:
1995:
1993:
1990:
1988:
1985:
1983:
1982:
1978:
1976:
1975:
1971:
1969:
1968:
1964:
1962:
1961:
1957:
1955:
1952:
1950:
1947:
1945:
1942:
1940:
1937:
1935:
1932:
1930:
1927:
1925:
1922:
1921:
1919:
1917:
1913:
1909:
1906:
1899:
1894:
1892:
1887:
1885:
1880:
1879:
1876:
1863:
1862:
1858:
1855:
1854:
1850:
1848:
1845:
1843:
1840:
1838:
1835:
1833:
1830:
1829:
1827:
1823:
1817:
1814:
1812:
1809:
1807:
1804:
1802:
1799:
1797:
1794:
1792:
1789:
1787:
1784:
1782:
1779:
1777:
1774:
1772:
1771:Fermat number
1769:
1767:
1764:
1763:
1761:
1757:
1753:
1746:
1741:
1739:
1734:
1732:
1727:
1726:
1723:
1719:
1712:
1706:
1698:
1696:0-262-03293-7
1692:
1688:
1687:
1682:
1678:
1674:
1670:
1666:
1665:
1657:
1652:
1649:, p. 2,
1648:
1641:
1638:
1633:
1629:
1625:
1621:
1617:
1611:
1608:
1603:
1599:
1595:
1591:
1587:
1583:
1582:
1574:
1570:
1566:
1562:
1561:Alford, W. R.
1556:
1553:
1548:
1544:
1539:
1534:
1530:
1526:
1519:
1516:(July 1980).
1515:
1511:
1507:
1501:
1499:
1495:
1488:
1486:
1484:
1480:
1474:
1471:
1469:
1465:
1461:
1457:
1453:
1445:
1443:
1429:
1426:
1423:
1420:
1417:
1414:
1411:
1408:
1405:
1402:
1399:
1377:
1373:
1369:
1366:
1339:
1335:
1327:
1324:
1319:
1316:
1313:
1309:
1305:
1300:
1297:
1294:
1289:
1285:
1281:
1276:
1273:
1270:
1266:
1262:
1257:
1254:
1251:
1241:
1237:
1233:
1230:
1220:
1219:
1218:
1202:
1198:
1175:
1171:
1148:
1144:
1123:
1099:
1096:
1090:
1087:
1084:
1078:
1075:
1053:
1040:
1036:
1024:
1021:
1014:
1013:
1012:
998:
989:
987:
983:
979:
975:
958:
955:
949:
946:
943:
937:
934:
914:
904:
890:
882:
878:
874:
866:
864:
863:for details.
862:
858:
854:
850:
844:
840:
836:
832:
828:
824:
820:
815:
807:
805:
803:
799:
795:
792:values 1 and
791:
784:
780:
776:
756:
752:
744:
741:
736:
733:
730:
726:
717:
714:
710:
709:
707:
703:
701:
697:
693:
689:
686:
683:
679:
675:
671:
668:
667:
666:
660:
658:
641:
634:
630:
622:
619:
616:
613:
608:
604:
600:
595:
592:
589:
585:
577:
576:
575:
573:
554:
547:
543:
535:
532:
527:
523:
519:
514:
511:
508:
504:
496:
495:
494:
492:
488:
484:
476:
474:
472:
468:
464:
441:
437:
429:
426:
421:
418:
415:
411:
403:
402:
401:
399:
394:
392:
388:
384:
380:
376:
353:
349:
341:
338:
333:
330:
327:
323:
315:
314:
313:
311:
306:
292:
289:
286:
283:
280:
277:
274:
266:
262:
242:
238:
230:
227:
224:
221:
213:
193:
189:
181:
178:
175:
166:
164:
160:
156:
152:
148:
144:
140:
136:
132:
128:
109:
102:
98:
90:
87:
82:
79:
76:
72:
64:
63:
62:
60:
56:
53:is prime and
52:
48:
41:
39:
37:
33:
32:probabilistic
29:
22:
2421:
2103:
2086:
2078:
1997:MillerâRabin
1979:
1972:
1965:
1960:LucasâLehmer
1958:
1948:
1859:
1851:
1847:Fermat Prize
1796:Fermat point
1717:
1685:
1646:
1640:
1623:
1619:
1610:
1585:
1579:
1555:
1528:
1524:
1475:
1472:
1452:MillerâRabin
1449:
1446:Applications
1358:
1115:
990:
982:MillerâRabin
876:
870:
856:
852:
848:
842:
838:
830:
826:
822:
811:
801:
800:and all odd
797:
793:
789:
787:
782:
774:
712:
705:
699:
695:
691:
687:
681:
677:
673:
669:
664:
656:
571:
569:
490:
486:
482:
480:
470:
466:
462:
460:
397:
395:
390:
382:
378:
374:
372:
309:
307:
264:
260:
167:
158:
154:
150:
146:
142:
138:
134:
130:
126:
124:
58:
54:
50:
45:
27:
25:
21:PĂ©pin's test
2253:Pollard rho
2210:Goldschmidt
1944:Pocklington
1934:BaillieâPSW
1626:: 201â206.
1456:BaillieâPSW
1359:and so all
978:BaillieâPSW
400:such that
379:Fermat liar
312:such that
2438:Categories
2365:Cornacchia
2360:Chakravala
1908:algorithms
1616:Paul ErdĆs
1489:References
1470:does not.
907:values of
903:for which
808:Complexity
574:, say 24:
385:is called
2339:Berlekamp
2296:Euclidean
2184:Euclidean
2164:ToomâCook
2159:Karatsuba
1705:cite book
1651:CiteSeerX
1464:Libgcrypt
1370:⋅
1317:−
1306:≡
1298:−
1282:⋅
1274:−
1263:≡
1255:−
1234:⋅
1079:
1054:∗
1025:∈
938:
841: log
775:composite
734:−
692:composite
661:Algorithm
614:≡
593:−
533:≡
512:−
419:−
339:≡
331:−
290:−
228:−
225:≡
179:≡
88:≡
80:−
2306:Lehmer's
2200:Chunking
2187:division
2116:Fermat's
1571:(1994).
1325:≢
847:, where
829:log log
742:≢
620:≢
427:≢
389:to base
2422:Italics
2344:Kunerth
2324:Cipolla
2205:Fourier
2174:FĂŒrer's
2068:Euler's
2058:Dixon's
1981:PĂ©pin's
1825:Related
1632:0079031
1602:2118576
1547:2006210
1468:OpenSSL
1190:, ...,
708:times:
704:Repeat
680:>3;
477:Example
141:, then
61:, then
42:Concept
2404:Schoof
2291:Binary
2195:Binary
2131:Shor's
1949:Fermat
1693:
1653:
1630:
1600:
1545:
1068:(i.e.
984:, and
855:, and
688:Output
670:Inputs
2225:Short
1954:Lucas
1598:JSTOR
1576:(PDF)
1543:JSTOR
1521:(PDF)
927:with
711:Pick
461:then
373:when
30:is a
2220:Long
2154:Long
1759:Work
1711:link
1691:ISBN
1392:for
867:Flaw
833:) =
788:The
308:Any
284:<
278:<
26:The
2384:LLL
2230:SRT
2089:+ 1
2081:â 1
1929:APR
1924:AKS
1590:doi
1586:140
1533:doi
1479:PGP
1460:GMP
1454:or
1336:mod
1076:gcd
935:gcd
905:all
825:log
753:mod
718:If
694:if
635:221
631:mod
609:220
548:221
544:mod
528:220
438:mod
350:mod
259:if
239:mod
190:mod
161:is
149:if
99:mod
2440::
2388:KZ
2386:;
1707:}}
1703:{{
1679:,
1675:,
1671:,
1628:MR
1622:.
1596:.
1584:.
1578:.
1567:;
1563:;
1541:.
1529:35
1527:.
1523:.
1512:;
1508:;
1497:^
1163:,
980:,
690::
672::
617:81
605:24
524:38
473:.
393:.
305:.
165:.
38:.
2390:)
2382:(
2087:p
2079:p
1897:e
1890:t
1883:v
1744:e
1737:t
1730:v
1713:)
1699:.
1634:.
1624:4
1604:.
1592::
1549:.
1535::
1430:s
1427:,
1424:.
1421:.
1418:.
1415:,
1412:2
1409:,
1406:1
1403:=
1400:i
1378:i
1374:a
1367:a
1343:)
1340:n
1333:(
1328:1
1320:1
1314:n
1310:a
1301:1
1295:n
1290:i
1286:a
1277:1
1271:n
1267:a
1258:1
1252:n
1248:)
1242:i
1238:a
1231:a
1228:(
1203:s
1199:a
1176:2
1172:a
1149:1
1145:a
1124:a
1112:)
1100:1
1097:=
1094:)
1091:n
1088:,
1085:a
1082:(
1050:)
1045:Z
1041:n
1037:/
1032:Z
1028:(
1022:a
999:n
959:1
956:=
953:)
950:n
947:,
944:a
941:(
915:a
891:n
877:a
857:n
853:a
849:k
845:)
843:n
839:k
837:(
835:Ă
831:n
827:n
823:k
821:(
819:O
802:n
798:n
794:n
790:a
760:)
757:n
750:(
745:1
737:1
731:n
727:a
713:a
706:k
696:n
682:k
678:n
674:n
642:.
638:)
628:(
623:1
601:=
596:1
590:n
586:a
572:a
555:.
551:)
541:(
536:1
520:=
515:1
509:n
505:a
491:a
487:a
483:n
471:n
463:a
445:)
442:n
435:(
430:1
422:1
416:n
412:a
398:a
391:a
383:n
375:n
357:)
354:n
347:(
342:1
334:1
328:n
324:a
310:a
293:1
287:p
281:a
275:1
265:a
261:p
246:)
243:p
236:(
231:1
222:a
197:)
194:p
187:(
182:1
176:a
159:p
155:a
151:p
147:a
143:p
139:a
135:p
131:a
127:p
110:.
106:)
103:p
96:(
91:1
83:1
77:p
73:a
59:p
55:a
51:p
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.