6813:
6389:
2364:
6284:
6808:{\displaystyle {\begin{aligned}\omega ^{\frac {M_{p}+1}{2}}{\bar {\omega }}^{\frac {M_{p}+1}{4}}&=-{\bar {\omega }}^{\frac {M_{p}+1}{4}}\\\omega ^{\frac {M_{p}+1}{4}}+{\bar {\omega }}^{\frac {M_{p}+1}{4}}&=0\\\omega ^{\frac {2^{p}-1+1}{4}}+{\bar {\omega }}^{\frac {2^{p}-1+1}{4}}&=0\\\omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}&=0\\s_{p-2}&=0.\end{aligned}}}
5652:
2041:
5988:
5398:
5264:
6896:(GIMPS) to locate large primes. This search has been successful in locating many of the largest primes known to date. The test is considered valuable because it can provably test a large set of very large numbers for primality within an affordable amount of time. In contrast, the equivalently fast
2359:{\displaystyle {\begin{aligned}s_{n}&=s_{n-1}^{2}-2\\&=\left(\omega ^{2^{n-1}}+{\bar {\omega }}^{2^{n-1}}\right)^{2}-2\\&=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}}+2(\omega {\bar {\omega }})^{2^{n-1}}-2\\&=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}}.\end{aligned}}}
6279:{\displaystyle {\begin{aligned}\omega ^{\frac {M_{p}+1}{2}}&={\frac {(6+\sigma )^{M_{p}+1}}{24^{\frac {M_{p}+1}{2}}}}\\&={\frac {(6+\sigma )(6+\sigma )^{M_{p}}}{24\cdot 24^{\frac {M_{p}-1}{2}}}}\\&={\frac {(6+\sigma )(6-\sigma )}{-24}}\\&=-1.\end{aligned}}}
2030:
3008:
1601:
262:
1214:
th bit to the 1st bit), which can be done in linear time. This algorithm has a small exceptional case. It will produce 2−1 for a multiple of the modulus rather than the correct value of 0. However, this case is easy to detect and correct.
1392:, this is in the same complexity class as the Lucas-Lehmer test. In practice however, the cost of doing many iterations and other differences leads to worse performance for Miller–Rabin. The most efficient deterministic primality test for any
2454:
5647:{\displaystyle {\begin{aligned}(6+\sigma )^{M_{p}}&=6^{M_{p}}+\left(2^{M_{p}}\right)\left({\sqrt {3}}^{M_{p}}\right)\\&=6+2\left(3^{\frac {M_{p}-1}{2}}\right){\sqrt {3}}\\&=6+2(-1){\sqrt {3}}\\&=6-\sigma ,\end{aligned}}}
5070:
1054:
886:
3440:
4977:
3110:
3251:
8191:
5771:
5386:
2821:
2717:
4781:
5059:
1889:
741:
6984:
7055:
7163:
4251:
5929:
6343:
6394:
5993:
5403:
2046:
5845:
7109:
2623:
1681:
352:
4520:
2524:
1809:
1901:
5976:
4871:
4578:
3677:
1352:
8195:
6381:
3816:
1720:
4347:
3728:
4095:
2872:
1764:
5300:
3875:
1501:
162:
7703:
3995:
3925:
2864:
7216:
4396:
3543:
3168:
4658:
7255:
3754:
7283:
150:
7736:
4131:
3595:
7187:
6849:
5872:
4019:
3948:
3514:
6883:
4692:
4604:
4161:
4049:
2372:
4815:
4458:
4423:
4285:
2551:
5259:{\displaystyle 24^{\frac {M_{p}-1}{2}}\equiv \left(2^{\frac {M_{p}-1}{2}}\right)^{3}\left(3^{\frac {M_{p}-1}{2}}\right)\equiv (1)^{3}(-1)\equiv -1{\pmod {M_{p}}}.}
3488:
3271:
949:
767:
3279:
4876:
8060:
7696:
593:
498:
274:
3019:
3177:
577: = 3 (mod 4). This starting value was often used where suitable in the era of hand computation, including by Lucas in proving
562:. There are infinitely many additional universal starting values. However, some other starting values are only valid for a subset of all possible
7928:
30:
This article is about the Lucas–Lehmer test that applies only to
Mersenne numbers. For the Lucas–Lehmer test that applies to a natural number
5667:
7870:
7689:
6893:
5309:
7799:
5658:
2732:
7976:
2631:
1247:
7540:
7675:
4704:
7774:
7631:
6918:
4985:
1818:
39:
666:
7885:
7923:
7860:
6939:
7804:
6989:
1495:
The proof of correctness for this test presented here is simpler than the original proof given by Lehmer. Recall the definition
1362:
8065:
7956:
7875:
7865:
7741:
7114:
7893:
4171:
8146:
5877:
510:
is a
Mersenne prime. However, the terms of the sequence will be different and a non-zero Lucas-Lehmer residue for non-prime
6292:
8141:
8070:
7971:
8108:
8022:
5787:
2025:{\displaystyle s_{0}=\omega ^{2^{0}}+{\bar {\omega }}^{2^{0}}=\left(2+{\sqrt {3}}\right)+\left(2-{\sqrt {3}}\right)=4}
7554:
7069:
2563:
1621:
292:
4463:
2467:
1769:
8187:
8177:
8136:
7912:
7906:
7880:
7751:
5778:
5934:
4820:
8172:
8113:
4528:
1400:, requires Õ(n) bit operations in its best known variant and is extremely slow even for relatively small values.
3604:
1293:
931:
In the algorithm as written above, there are two expensive operations during each iteration: the multiplication
8256:
8251:
8075:
7948:
7794:
7746:
6348:
3762:
3003:{\displaystyle \left(\omega ^{2^{p-2}}\right)^{2}=kM_{p}\omega ^{2^{p-2}}-(\omega {\bar {\omega }})^{2^{p-2}}.}
1688:
1219:
6913:
4293:
3684:
1487: = 2047 has nontrivial factors, the Lucas–Lehmer test gives no indication about what they might be.
4054:
1596:{\displaystyle s_{i}={\begin{cases}4&{\text{if }}i=0;\\s_{i-1}^{2}-2&{\text{otherwise.}}\end{cases}}}
257:{\displaystyle s_{i}={\begin{cases}4&{\text{if }}i=0;\\s_{i-1}^{2}-2&{\text{otherwise.}}\end{cases}}}
8090:
7981:
1287:
1733:
8201:
8151:
8131:
5272:
3831:
1812:
1251:
473:
7852:
7827:
7756:
3957:
3890:
8211:
2829:
7192:
4355:
3519:
3144:
8206:
8098:
8080:
8055:
8017:
7761:
4695:
4661:
3998:
1727:
70:
35:
1523:
501:). The Lucas-Lehmer residue calculated with these alternative starting values will still be zero if
184:
8216:
8182:
8103:
8007:
7966:
7961:
7938:
7842:
6904:
can only be used on a much smaller set of very large numbers before reaching computational limits.
4613:
1723:
558:
Starting values like 4, 10, and 2/3 are universal, that is, they are valid for all (or nearly all)
7225:
3733:
8047:
7994:
7991:
7832:
7731:
7577:
7522:
7462:
7332:
7264:
1397:
7788:
7781:
6897:
1218:
With the modulus out of the way, the asymptotic complexity of the algorithm only depends on the
2449:{\displaystyle \omega {\bar {\omega }}=\left(2+{\sqrt {3}}\right)\left(2-{\sqrt {3}}\right)=1.}
547:), usually denoted by 2/3 for short. This starting value equals (2 + 1) /3, the
122:
8167:
8123:
7837:
7814:
7648:
7627:
4787:
4100:
3560:
472:
bits (otherwise the number of bits would double each iteration). The same strategy is used in
7172:
6821:
5857:
4004:
3933:
3499:
8012:
7615:
7569:
7514:
7452:
7417:
7396:
7324:
6858:
4667:
4583:
4136:
4024:
943:
operation can be made particularly efficient on standard binary computers by observing that
66:
4793:
4436:
4401:
4263:
2529:
17:
8002:
7901:
7605:
4607:
3460:
548:
1049:{\displaystyle k\equiv (k\,{\bmod {\,}}2^{n})+\lfloor k/2^{n}\rfloor {\pmod {2^{n}-1}}.}
881:{\displaystyle \epsilon (10,\ p)=\epsilon (4,\ p)\ \times \ (-1)^{{(p+1)(p+3)} \over 8}}
8032:
7933:
7918:
7822:
7723:
7619:
3256:
1227:
103:
62:
58:
7651:
7401:
7384:
2456:
This closed form is used in both the proof of sufficiency and the proof of necessity.
1361:
By comparison, the most efficient randomized primality test for general integers, the
757:
The same author also proved that the Lehmer symbols for starting values 4 and 10 when
8245:
8027:
7712:
7581:
7360:
6901:
7336:
3435:{\displaystyle \left(a+{\sqrt {3}}b\right)\left(c+{\sqrt {3}}d\right)=+{\sqrt {3}}.}
8037:
4972:{\displaystyle 2\equiv 2^{p+1}=\left(2^{\frac {p+1}{2}}\right)^{2}{\pmod {M_{p}}}.}
2554:
95:
1083:
by the
Mersenne number 2−1 is computed without using division. For example,
7471:
The use of the FFT speeds up the asymptotic time for the Lucas–Lehmer test for M
7309:
46:
7681:
1412:= 2−1 = 7 is prime. The Lucas–Lehmer test verifies this as follows. Initially
1226:
at each step. The simple "grade-school" algorithm for multiplication requires
519:
will have a different numerical value from the non-zero value calculated when
411:
7601:
7328:
3105:{\displaystyle \omega ^{2^{p-1}}=kM_{p}\omega ^{2^{p-2}}-1.\qquad \qquad (1)}
903: = 5 or 7 (mod 8) and p ≠ 2, 5.
7715:
7656:
3246:{\displaystyle X=\left\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{q}\right\}.}
656:
In 2000 S.Y. Gebre-Egziabher proved that for the starting value 2/3 and for
1388:
is the number of iterations and is related to the error rate. For constant
7585:
1439: = 2047 = 23 × 89 is not prime. Again,
267:
The first few terms of this sequence are 4, 14, 194, 37634, ... (sequence
3445:
Clearly, this multiplication is closed, i.e. the product of numbers from
1206:
will never exceed M < 2, this simple technique converges in at most 1
7505:
Bruce, J. W. (1993). "A Really
Trivial Proof of the Lucas–Lehmer Test".
2553:
is prime. What follows is a straightforward proof exploiting elementary
1075:
modulo 2−1. This equivalence can be used repeatedly until at most
7573:
7526:
7466:
586:
prime. The first few terms of the sequence are 3, 7, 47, ... (sequence
90: = 2 − 1 be the Mersenne number to test with
5766:{\displaystyle (x+y)^{M_{p}}\equiv x^{M_{p}}+y^{M_{p}}{\pmod {M_{p}}}}
6892:
The Lucas–Lehmer test is one of the main primality tests used by the
5381:{\displaystyle X=\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{M_{p}}\}.}
4165:
The order of an element is at most the order (size) of the group, so
491:
other than 4 are possible, for instance 10, 52, and others (sequence
7518:
7457:
2816:{\displaystyle \omega ^{2^{p-2}}=kM_{p}-{\bar {\omega }}^{2^{p-2}}.}
468:
at each iteration ensures that all intermediate results are at most
2712:{\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kM_{p}}
7670:
4433:
In the other direction, the goal is to show that the primality of
642:. The sign of this penultimate term is called the Lehmer symbol ϵ(
446:
p − 2 times: s = ((s × s) − 2) mod M
7685:
7443:
Colquitt, W. N.; Welsh, L. Jr. (1991), "A New
Mersenne Prime",
6289:
All that remains is to multiply both sides of this equation by
4776:{\displaystyle 3^{\frac {M_{p}-1}{2}}\equiv -1{\pmod {M_{p}}}.}
1443:
is set to 4 but is now updated 11−2 = 9 times:
529:
It is also possible to use the starting value (2 mod
5054:{\displaystyle 2^{\frac {M_{p}-1}{2}}\equiv 1{\pmod {M_{p}}}.}
1884:{\displaystyle s_{i}=\omega ^{2^{i}}+{\bar {\omega }}^{2^{i}}}
1616:
1416:
is set to 4 and then is updated 3−2 = 1 time:
3416:
3367:
967:
736:{\displaystyle \epsilon ({2 \over 3},\ p)=(-1)^{p-1 \over 2}}
6979:{\displaystyle \mathbb {Z} _{q}=\mathbb {Z} /q\mathbb {Z} }
4522:. The following simplified proof is by Öystein J. Rödseth.
1589:
907:
588:
493:
269:
250:
7665:
7050:{\displaystyle X=\mathbb {Z} _{q}/\langle T^{2}-3\rangle }
7158:{\displaystyle {\bar {\omega }}+\langle T^{2}-3\rangle }
2557:
102:
can be efficiently checked with a simple algorithm like
8232:
indicate that algorithm is for numbers of special forms
4246:{\displaystyle 2^{p}\leq |X^{*}|\leq q^{2}-1<q^{2}.}
1079:
bits remain. In this way, the remainder after dividing
7671:
A proof of Lucas–Lehmer–Reix test (for Fermat numbers)
5924:{\displaystyle \omega ={\frac {(6+\sigma )^{2}}{24}}.}
754: = 1 (mod 4) and p ≠ 5.
7267:
7228:
7195:
7175:
7117:
7072:
6992:
6942:
6861:
6824:
6392:
6351:
6338:{\displaystyle {\bar {\omega }}^{\frac {M_{p}+1}{4}}}
6295:
5991:
5937:
5880:
5860:
5790:
5670:
5401:
5312:
5275:
5073:
4988:
4879:
4823:
4796:
4707:
4670:
4616:
4586:
4531:
4466:
4439:
4404:
4358:
4296:
4266:
4174:
4139:
4103:
4057:
4027:
4007:
3960:
3936:
3893:
3834:
3765:
3736:
3687:
3607:
3563:
3522:
3502:
3463:
3282:
3259:
3180:
3147:
3022:
2875:
2832:
2735:
2634:
2566:
2532:
2470:
2375:
2044:
1904:
1821:
1772:
1736:
1691:
1624:
1504:
1296:
952:
770:
669:
295:
165:
125:
7626:(1st ed.), Berlin: Springer, pp. 167–170,
1286:). An even more efficient multiplication algorithm,
1246:). A more efficient multiplication algorithm is the
8160:
8122:
8089:
8046:
7990:
7947:
7851:
7813:
7722:
7277:
7249:
7210:
7181:
7157:
7103:
7049:
6978:
6877:
6843:
6807:
6375:
6337:
6278:
5970:
5923:
5866:
5839:
5765:
5646:
5380:
5294:
5258:
5053:
4971:
4865:
4809:
4775:
4686:
4652:
4598:
4572:
4514:
4452:
4417:
4390:
4341:
4279:
4245:
4155:
4125:
4089:
4043:
4013:
3989:
3942:
3919:
3869:
3810:
3748:
3722:
3671:
3589:
3537:
3508:
3482:
3434:
3265:
3245:
3162:
3104:
3002:
2858:
2815:
2711:
2617:
2545:
2518:
2448:
2358:
2024:
1883:
1803:
1758:
1714:
1675:
1595:
1346:
1048:
880:
735:
346:
256:
144:
7365:(Doctoral thesis). Leiden University. p. iii
5064:Combining these two equivalence relations yields
3553:with inverses forms a group, which is denoted by
1465:s ← ((1877 × 1877) − 2) mod 2047 = 240
1380:) bit operations using FFT multiplication for an
1234:) bit-level or word-level operations to square a
7666:GIMPS (The Great Internet Mersenne Prime Search)
7622:(2001), "Section 4.2.1: The Lucas–Lehmer test",
5840:{\displaystyle a^{M_{p}}\equiv a{\pmod {M_{p}}}}
1471:s ← ((282 × 282) − 2) mod 2047 = 1736
1462:s ← ((119 × 119) − 2) mod 2047 = 1877
7104:{\displaystyle \omega +\langle T^{2}-3\rangle }
2618:{\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}.}
1676:{\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}.}
1468:s ← ((240 × 240) − 2) mod 2047 = 282
1459:s ← ((701 × 701) − 2) mod 2047 = 119
1456:s ← ((788 × 788) − 2) mod 2047 = 701
1453:s ← ((194 × 194) − 2) mod 2047 = 788
347:{\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}.}
4515:{\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}
4260:is the smallest prime factor of the composite
2519:{\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}
1804:{\displaystyle {\bar {\omega }}=2-{\sqrt {3}}}
1270:-bit number. This reduces the complexity to O(
7697:
7541:Mersenne Primes, An Introduction and Overview
1450:s ← ((14 × 14) − 2) mod 2047 = 194
1210:-bit addition (and possibly a carry from the
8:
7152:
7133:
7098:
7079:
7044:
7025:
5971:{\displaystyle \omega ^{\frac {M_{p}+1}{2}}}
5372:
5319:
4866:{\displaystyle 2^{p}\equiv 1{\pmod {M_{p}}}}
1708:
1693:
1011:
990:
139:
126:
81:The Lucas–Lehmer test works as follows. Let
4573:{\displaystyle 2^{p}-1\equiv 7{\pmod {12}}}
1109:((916 mod 2) + int(916 ÷ 2)) mod 2−1
7704:
7690:
7682:
7624:Prime Numbers: A Computational Perspective
7317:Bulletin of the Irish Mathematical Society
5931:Consequently, this can be used to compute
3672:{\displaystyle |X^{*}|\leq |X|-1=q^{2}-1.}
1483: = 2047 is not prime. Although M
1447:s ← ((4 × 4) − 2) mod 2047 = 14
1347:{\displaystyle p\log p\ 2^{O(\log ^{*}p)}}
7555:"A note on primality tests for N=h·2^n−1"
7456:
7400:
7268:
7266:
7237:
7230:
7229:
7227:
7222:under the natural ring homomorphism from
7197:
7196:
7194:
7174:
7140:
7119:
7118:
7116:
7086:
7071:
7032:
7020:
7005:
7001:
7000:
6991:
6972:
6971:
6963:
6959:
6958:
6949:
6945:
6944:
6941:
6866:
6860:
6829:
6823:
6779:
6747:
6742:
6731:
6730:
6712:
6707:
6664:
6657:
6646:
6645:
6616:
6609:
6572:
6565:
6554:
6553:
6530:
6523:
6496:
6489:
6478:
6477:
6447:
6440:
6429:
6428:
6408:
6401:
6393:
6391:
6376:{\displaystyle \omega {\bar {\omega }}=1}
6356:
6355:
6350:
6316:
6309:
6298:
6297:
6294:
6212:
6180:
6173:
6153:
6148:
6114:
6083:
6076:
6057:
6052:
6033:
6007:
6000:
5992:
5990:
5949:
5942:
5936:
5906:
5887:
5879:
5859:
5827:
5814:
5800:
5795:
5789:
5753:
5740:
5732:
5727:
5712:
5707:
5692:
5687:
5669:
5611:
5573:
5550:
5543:
5504:
5499:
5492:
5475:
5470:
5451:
5446:
5427:
5422:
5402:
5400:
5364:
5359:
5355:
5354:
5331:
5311:
5285:
5274:
5243:
5230:
5203:
5167:
5160:
5146:
5123:
5116:
5085:
5078:
5072:
5038:
5025:
5000:
4993:
4987:
4956:
4943:
4937:
4914:
4890:
4878:
4853:
4840:
4828:
4822:
4801:
4795:
4760:
4747:
4719:
4712:
4706:
4675:
4669:
4632:
4623:
4615:
4585:
4554:
4536:
4530:
4502:
4489:
4471:
4465:
4444:
4438:
4409:
4403:
4376:
4363:
4357:
4327:
4314:
4301:
4295:
4271:
4265:
4234:
4215:
4203:
4197:
4188:
4179:
4173:
4144:
4138:
4108:
4102:
4067:
4062:
4056:
4032:
4026:
4006:
3970:
3965:
3959:
3935:
3903:
3898:
3892:
3844:
3839:
3833:
3811:{\displaystyle kM_{p}\omega ^{2^{p-2}}=0}
3788:
3783:
3773:
3764:
3735:
3704:
3692:
3686:
3657:
3639:
3631:
3623:
3617:
3608:
3606:
3579:
3573:
3564:
3562:
3524:
3523:
3521:
3501:
3472:
3464:
3462:
3420:
3419:
3415:
3414:
3383:
3371:
3370:
3366:
3365:
3320:
3294:
3281:
3258:
3229:
3225:
3224:
3201:
3179:
3154:
3150:
3149:
3146:
3071:
3066:
3056:
3032:
3027:
3021:
2983:
2978:
2963:
2962:
2939:
2934:
2924:
2908:
2890:
2885:
2874:
2842:
2837:
2831:
2796:
2791:
2780:
2779:
2769:
2745:
2740:
2734:
2703:
2679:
2674:
2663:
2662:
2644:
2639:
2633:
2602:
2589:
2571:
2565:
2537:
2531:
2506:
2493:
2475:
2469:
2428:
2405:
2380:
2379:
2374:
2341:
2336:
2325:
2324:
2312:
2307:
2273:
2268:
2253:
2252:
2232:
2227:
2216:
2215:
2203:
2198:
2172:
2153:
2148:
2137:
2136:
2118:
2113:
2081:
2070:
2053:
2045:
2043:
2004:
1978:
1956:
1951:
1940:
1939:
1927:
1922:
1909:
1903:
1873:
1868:
1857:
1856:
1844:
1839:
1826:
1820:
1794:
1774:
1773:
1771:
1749:
1735:
1715:{\displaystyle {\langle }s_{i}{\rangle }}
1707:
1701:
1692:
1690:
1660:
1647:
1629:
1623:
1581:
1567:
1556:
1531:
1518:
1509:
1503:
1327:
1316:
1295:
1027:
1014:
1005:
996:
978:
971:
970:
966:
965:
951:
840:
838:
769:
714:
676:
668:
331:
318:
300:
294:
242:
228:
217:
192:
179:
170:
164:
133:
124:
7354:
7352:
7350:
7348:
7346:
4342:{\displaystyle q^{2}\leq M_{p}=2^{p}-1.}
3723:{\displaystyle M_{p}\equiv 0{\pmod {q}}}
1242:) times, the total time complexity is O(
38:. For the Lucas–Lehmer–Riesel test, see
7300:
6929:
4090:{\displaystyle \omega ^{2^{p-1}}\neq 1}
3601:that does not have an inverse is 0, so
1479:is not 0, the conclusion is that M
1420:s ← ((4 × 4) − 2) mod 7 = 0.
65:. The test was originally developed by
7362:Mersenne primes and class field theory
7323:(2). Irish Mathematical Society: 63.
1759:{\displaystyle \omega =2+{\sqrt {3}}}
1059:This says that the least significant
7:
7218:are identified with their images in
6894:Great Internet Mersenne Prime Search
5295:{\displaystyle \sigma =2{\sqrt {3}}}
3870:{\displaystyle \omega ^{2^{p-1}}=-1}
633: = ± 2 mod
5822:
5748:
5238:
5033:
4979:This time, Euler's criterion gives
4951:
4848:
4755:
4562:
4497:
3712:
3496: > 2, it follows that
2597:
2501:
1655:
1428:is 0, the conclusion is that M
1022:
326:
69:in 1878 and subsequently proved by
5659:Binomial Theorem in a finite field
5657:where the first equality uses the
3990:{\displaystyle \omega ^{2^{p}-1}.}
3920:{\displaystyle \omega ^{2^{p}}=1.}
1238:-bit number. Since this happens O(
27:Test if a Mersenne number is prime
25:
7913:Special number field sieve (SNFS)
7907:General number field sieve (GNFS)
7507:The American Mathematical Monthly
7402:10.1090/S0002-9939-1954-0064787-4
4608:properties of the Legendre symbol
3884:, and squaring both sides gives
2859:{\displaystyle \omega ^{2^{p-2}}}
384:. (Some authors equivalently set
7211:{\displaystyle {\bar {\omega }}}
4391:{\displaystyle 2^{p}<2^{p}-1}
3538:{\displaystyle {\bar {\omega }}}
3163:{\displaystyle \mathbb {Z} _{q}}
3128:be the smallest prime factor of
7310:"Note on the Lucas–Lehmer Test"
5815:
5741:
5231:
5026:
4944:
4841:
4748:
4555:
4490:
4097:, so the order does not divide
3705:
3137:. Mersenne numbers are odd, so
3092:
3091:
2590:
2494:
1648:
1015:
414:, the test might be written as
319:
7425:(Technical report). p. 20
7244:
7234:
7202:
7124:
7017:
7011:
6736:
6651:
6559:
6483:
6434:
6361:
6303:
6242:
6230:
6227:
6215:
6145:
6132:
6129:
6117:
6049:
6036:
5903:
5890:
5833:
5816:
5759:
5742:
5684:
5671:
5608:
5599:
5419:
5406:
5249:
5232:
5218:
5209:
5200:
5193:
5044:
5027:
4962:
4945:
4859:
4842:
4766:
4749:
4638:
4624:
4617:
4566:
4556:
4508:
4491:
4352:This yields the contradiction
4204:
4189:
3716:
3706:
3640:
3632:
3624:
3609:
3580:
3565:
3529:
3473:
3465:
3426:
3411:
3393:
3390:
3377:
3362:
3341:
3338:
3099:
3093:
2975:
2968:
2956:
2785:
2668:
2608:
2591:
2512:
2495:
2385:
2330:
2265:
2258:
2246:
2221:
2142:
1945:
1862:
1779:
1666:
1649:
1339:
1320:
1039:
1016:
984:
959:
868:
856:
853:
841:
835:
825:
813:
798:
789:
774:
761:is not 2 or 5 are related by:
711:
701:
695:
673:
573: = 3 can be used if
337:
320:
110:is exponentially smaller than
1:
7385:"Mersenne and Fermat numbers"
7383:Robinson, Raphael M. (1954).
5777:and the second equality uses
4653:{\displaystyle (3|M_{p})=-1.}
3115:For a contradiction, suppose
623:then the penultimate term is
614: = 0 mod
7871:Lenstra elliptic curve (ECM)
7553:Rödseth, Öystein J. (1994).
7250:{\displaystyle \mathbb {Z} }
3749:{\displaystyle \omega \in X}
3549:. The subset of elements in
1248:Schönhage–Strassen algorithm
660: ≠ 5 the sign is:
7602:The "Top Ten" Record Primes
7278:{\displaystyle {\sqrt {3}}}
4133:Thus, the order is exactly
1363:Miller–Rabin primality test
1067:plus the remaining bits of
426:= 2 − 1 is prime for
18:Lucas-Lehmer primality test
8273:
8178:Exponentiation by squaring
7861:Continued fraction (CFRAC)
7445:Mathematics of Computation
914:) for each Mersenne prime
29:
8225:
7562:BIT Numerical Mathematics
3825:. Then by equation (1),
2464:The goal is to show that
1606:The goal is to show that
1475:Since the final value of
1424:Since the final value of
895:) × ϵ(10,
480:Alternate starting values
145:{\displaystyle \{s_{i}\}}
7329:10.33232/BIMS.0054.63.72
7308:Jaroma, John H. (2004).
7169:. By abuse of language
6919:Lucas–Lehmer–Riesel test
4698:, this is equivalent to
4126:{\displaystyle 2^{p-1}.}
3590:{\displaystyle |X^{*}|.}
3141: > 2. Let
1250:, which is based on the
1220:multiplication algorithm
600:Sign of penultimate term
391: = 4 and test
286:is prime if and only if
40:Lucas–Lehmer–Riesel test
8091:Greatest common divisor
7359:Jansen, B.J.H. (2012).
7182:{\displaystyle \omega }
6844:{\displaystyle s_{p-2}}
5867:{\displaystyle \sigma }
5779:Fermat's little theorem
4660:This means that 3 is a
4014:{\displaystyle \omega }
3943:{\displaystyle \omega }
3509:{\displaystyle \omega }
3170:be the integers modulo
8202:Modular exponentiation
7279:
7251:
7212:
7183:
7159:
7105:
7051:
6980:
6879:
6878:{\displaystyle M_{p}.}
6855:, it is also 0 modulo
6845:
6809:
6377:
6339:
6280:
5972:
5925:
5868:
5841:
5767:
5648:
5382:
5306:as before as the ring
5296:
5260:
5055:
4973:
4867:
4811:
4777:
4688:
4687:{\displaystyle M_{p}.}
4654:
4600:
4599:{\displaystyle p>1}
4574:
4516:
4454:
4419:
4392:
4343:
4281:
4247:
4157:
4156:{\displaystyle 2^{p}.}
4127:
4091:
4045:
4044:{\displaystyle 2^{p}.}
4015:
3991:
3944:
3921:
3871:
3812:
3750:
3724:
3673:
3591:
3539:
3510:
3484:
3436:
3267:
3247:
3164:
3124:is composite, and let
3106:
3004:
2860:
2817:
2713:
2619:
2547:
2520:
2450:
2360:
2026:
1885:
1805:
1760:
1716:
1677:
1597:
1348:
1252:Fast Fourier transform
1050:
882:
737:
474:modular exponentiation
348:
258:
146:
7929:Shanks's square forms
7853:Integer factorization
7828:Sieve of Eratosthenes
7539:Jason Wojciechowski.
7416:Haworth, Guy (1990).
7389:Proc. Amer. Math. Soc
7280:
7252:
7213:
7184:
7160:
7106:
7052:
6981:
6914:Mersenne's conjecture
6880:
6846:
6810:
6378:
6340:
6281:
5973:
5926:
5869:
5842:
5768:
5649:
5383:
5297:
5261:
5056:
4974:
4868:
4812:
4810:{\displaystyle M_{p}}
4778:
4689:
4655:
4601:
4575:
4517:
4455:
4453:{\displaystyle M_{p}}
4420:
4418:{\displaystyle M_{p}}
4393:
4344:
4282:
4280:{\displaystyle M_{p}}
4248:
4158:
4128:
4092:
4046:
4016:
3992:
3945:
3922:
3872:
3813:
3751:
3725:
3674:
3592:
3540:
3511:
3485:
3437:
3268:
3248:
3165:
3107:
3005:
2861:
2818:
2714:
2620:
2548:
2546:{\displaystyle M_{p}}
2521:
2451:
2361:
2027:
1886:
1811:. It then follows by
1806:
1761:
1717:
1678:
1598:
1408:The Mersenne number M
1384:-digit number, where
1354:time to multiply two
1349:
1254:. It only requires O(
1051:
883:
746:That is, ϵ(2/3,
738:
349:
259:
147:
8207:Montgomery reduction
8081:Function field sieve
8056:Baby-step giant-step
7902:Quadratic sieve (QS)
7265:
7226:
7193:
7173:
7115:
7070:
6990:
6940:
6859:
6822:
6390:
6349:
6293:
5989:
5935:
5878:
5858:
5788:
5668:
5399:
5310:
5273:
5071:
4986:
4877:
4821:
4794:
4786:In contrast, 2 is a
4705:
4668:
4662:quadratic nonresidue
4614:
4584:
4529:
4464:
4437:
4402:
4356:
4294:
4264:
4172:
4137:
4101:
4055:
4025:
4005:
3958:
3934:
3891:
3832:
3763:
3734:
3685:
3605:
3561:
3520:
3500:
3483:{\displaystyle |X|.}
3461:
3280:
3257:
3178:
3145:
3020:
2873:
2830:
2733:
2632:
2564:
2530:
2468:
2373:
2042:
1902:
1819:
1770:
1734:
1728:closed-form solution
1689:
1622:
1502:
1491:Proof of correctness
1435:On the other hand, M
1294:
950:
933:s × s
768:
750:) = +1 if
667:
442:M = 2 − 1
378:Lucas–Lehmer residue
365: − 2
293:
163:
123:
119:. Define a sequence
71:Derrick Henry Lehmer
36:Lucas primality test
8217:Trachtenberg system
8183:Integer square root
8124:Modular square root
7843:Wheel factorization
7795:Quadratic Frobenius
7775:Lucas–Lehmer–Riesel
7652:"Lucas–Lehmer test"
5874:was chosen so that
2369:The last step uses
2086:
1724:recurrence relation
1572:
1396:-digit number, the
1266:) time to square a
899:) = 1 if
891:That is, ϵ(4,
233:
98:. The primality of
8109:Extended Euclidean
8048:Discrete logarithm
7977:Schönhage–Strassen
7833:Sieve of Pritchard
7649:Weisstein, Eric W.
7574:10.1007/BF01935653
7275:
7247:
7208:
7179:
7155:
7101:
7047:
6976:
6875:
6841:
6805:
6803:
6373:
6335:
6276:
6274:
5968:
5921:
5864:
5837:
5763:
5644:
5642:
5392:, it follows that
5378:
5292:
5256:
5051:
4969:
4863:
4807:
4773:
4684:
4650:
4606:, it follows from
4596:
4570:
4512:
4450:
4415:
4388:
4339:
4277:
4243:
4153:
4123:
4087:
4041:
4011:
3987:
3954:* and has inverse
3940:
3917:
3867:
3808:
3746:
3720:
3669:
3587:
3535:
3506:
3480:
3432:
3263:
3253:Multiplication in
3243:
3160:
3102:
3000:
2856:
2813:
2709:
2615:
2543:
2516:
2446:
2356:
2354:
2066:
2022:
1881:
1801:
1756:
1712:
1673:
1593:
1588:
1552:
1398:AKS primality test
1344:
1071:are equivalent to
1046:
878:
733:
538:)(3 mod
344:
254:
249:
213:
142:
8239:
8238:
7838:Sieve of Sundaram
7676:Lucas–Lehmer test
7616:Crandall, Richard
7591:on March 6, 2016.
7493:) bit operations.
7273:
7242:
7205:
7127:
6739:
6686:
6654:
6638:
6588:
6562:
6546:
6512:
6486:
6463:
6437:
6424:
6364:
6332:
6306:
6254:
6200:
6196:
6102:
6099:
6023:
5965:
5916:
5616:
5578:
5566:
5497:
5388:Then in the ring
5336:
5290:
5183:
5139:
5101:
5016:
4930:
4788:quadratic residue
4735:
4696:Euler's criterion
3997:Furthermore, the
3532:
3388:
3325:
3299:
3266:{\displaystyle X}
3206:
2971:
2788:
2722:for some integer
2671:
2433:
2410:
2388:
2333:
2261:
2224:
2145:
2009:
1983:
1948:
1865:
1799:
1782:
1754:
1584:
1534:
1311:
1288:Fürer's algorithm
1200:
1199:
1089:916 mod 2−1
875:
824:
818:
809:
785:
730:
691:
684:
245:
195:
51:Lucas–Lehmer test
16:(Redirected from
8264:
8188:Integer relation
8161:Other algorithms
8066:Pollard kangaroo
7957:Ancient Egyptian
7815:Prime-generating
7800:Solovay–Strassen
7713:Number-theoretic
7706:
7699:
7692:
7683:
7662:
7661:
7636:
7608:
7599:
7593:
7592:
7590:
7584:. Archived from
7559:
7550:
7544:
7537:
7531:
7530:
7502:
7496:
7495:
7460:
7451:(194): 867–870,
7440:
7434:
7433:
7431:
7430:
7424:
7419:Mersenne numbers
7413:
7407:
7406:
7404:
7380:
7374:
7373:
7371:
7370:
7356:
7341:
7340:
7314:
7305:
7290:
7284:
7282:
7281:
7276:
7274:
7269:
7256:
7254:
7253:
7248:
7243:
7238:
7233:
7217:
7215:
7214:
7209:
7207:
7206:
7198:
7188:
7186:
7185:
7180:
7164:
7162:
7161:
7156:
7145:
7144:
7129:
7128:
7120:
7110:
7108:
7107:
7102:
7091:
7090:
7064:
7058:
7056:
7054:
7053:
7048:
7037:
7036:
7024:
7010:
7009:
7004:
6985:
6983:
6982:
6977:
6975:
6967:
6962:
6954:
6953:
6948:
6934:
6884:
6882:
6881:
6876:
6871:
6870:
6850:
6848:
6847:
6842:
6840:
6839:
6814:
6812:
6811:
6806:
6804:
6790:
6789:
6760:
6759:
6758:
6757:
6741:
6740:
6732:
6725:
6724:
6723:
6722:
6688:
6687:
6682:
6669:
6668:
6658:
6656:
6655:
6647:
6640:
6639:
6634:
6621:
6620:
6610:
6590:
6589:
6584:
6577:
6576:
6566:
6564:
6563:
6555:
6548:
6547:
6542:
6535:
6534:
6524:
6514:
6513:
6508:
6501:
6500:
6490:
6488:
6487:
6479:
6465:
6464:
6459:
6452:
6451:
6441:
6439:
6438:
6430:
6426:
6425:
6420:
6413:
6412:
6402:
6382:
6380:
6379:
6374:
6366:
6365:
6357:
6344:
6342:
6341:
6336:
6334:
6333:
6328:
6321:
6320:
6310:
6308:
6307:
6299:
6285:
6283:
6282:
6277:
6275:
6259:
6255:
6253:
6245:
6213:
6205:
6201:
6199:
6198:
6197:
6192:
6185:
6184:
6174:
6161:
6160:
6159:
6158:
6157:
6115:
6107:
6103:
6101:
6100:
6095:
6088:
6087:
6077:
6071:
6070:
6069:
6062:
6061:
6034:
6025:
6024:
6019:
6012:
6011:
6001:
5977:
5975:
5974:
5969:
5967:
5966:
5961:
5954:
5953:
5943:
5930:
5928:
5927:
5922:
5917:
5912:
5911:
5910:
5888:
5873:
5871:
5870:
5865:
5854:. The value of
5850:for any integer
5846:
5844:
5843:
5838:
5836:
5832:
5831:
5807:
5806:
5805:
5804:
5772:
5770:
5769:
5764:
5762:
5758:
5757:
5739:
5738:
5737:
5736:
5719:
5718:
5717:
5716:
5699:
5698:
5697:
5696:
5653:
5651:
5650:
5645:
5643:
5621:
5617:
5612:
5583:
5579:
5574:
5572:
5568:
5567:
5562:
5555:
5554:
5544:
5519:
5515:
5511:
5510:
5509:
5508:
5498:
5493:
5486:
5482:
5481:
5480:
5479:
5458:
5457:
5456:
5455:
5434:
5433:
5432:
5431:
5387:
5385:
5384:
5379:
5371:
5370:
5369:
5368:
5358:
5337:
5332:
5301:
5299:
5298:
5293:
5291:
5286:
5265:
5263:
5262:
5257:
5252:
5248:
5247:
5208:
5207:
5189:
5185:
5184:
5179:
5172:
5171:
5161:
5151:
5150:
5145:
5141:
5140:
5135:
5128:
5127:
5117:
5103:
5102:
5097:
5090:
5089:
5079:
5060:
5058:
5057:
5052:
5047:
5043:
5042:
5018:
5017:
5012:
5005:
5004:
4994:
4978:
4976:
4975:
4970:
4965:
4961:
4960:
4942:
4941:
4936:
4932:
4931:
4926:
4915:
4901:
4900:
4872:
4870:
4869:
4864:
4862:
4858:
4857:
4833:
4832:
4816:
4814:
4813:
4808:
4806:
4805:
4782:
4780:
4779:
4774:
4769:
4765:
4764:
4737:
4736:
4731:
4724:
4723:
4713:
4693:
4691:
4690:
4685:
4680:
4679:
4659:
4657:
4656:
4651:
4637:
4636:
4627:
4605:
4603:
4602:
4597:
4579:
4577:
4576:
4571:
4569:
4541:
4540:
4521:
4519:
4518:
4513:
4511:
4507:
4506:
4482:
4481:
4459:
4457:
4456:
4451:
4449:
4448:
4424:
4422:
4421:
4416:
4414:
4413:
4397:
4395:
4394:
4389:
4381:
4380:
4368:
4367:
4348:
4346:
4345:
4340:
4332:
4331:
4319:
4318:
4306:
4305:
4286:
4284:
4283:
4278:
4276:
4275:
4252:
4250:
4249:
4244:
4239:
4238:
4220:
4219:
4207:
4202:
4201:
4192:
4184:
4183:
4162:
4160:
4159:
4154:
4149:
4148:
4132:
4130:
4129:
4124:
4119:
4118:
4096:
4094:
4093:
4088:
4080:
4079:
4078:
4077:
4050:
4048:
4047:
4042:
4037:
4036:
4020:
4018:
4017:
4012:
3996:
3994:
3993:
3988:
3983:
3982:
3975:
3974:
3949:
3947:
3946:
3941:
3926:
3924:
3923:
3918:
3910:
3909:
3908:
3907:
3876:
3874:
3873:
3868:
3857:
3856:
3855:
3854:
3817:
3815:
3814:
3809:
3801:
3800:
3799:
3798:
3778:
3777:
3755:
3753:
3752:
3747:
3729:
3727:
3726:
3721:
3719:
3697:
3696:
3678:
3676:
3675:
3670:
3662:
3661:
3643:
3635:
3627:
3622:
3621:
3612:
3596:
3594:
3593:
3588:
3583:
3578:
3577:
3568:
3544:
3542:
3541:
3536:
3534:
3533:
3525:
3515:
3513:
3512:
3507:
3489:
3487:
3486:
3481:
3476:
3468:
3441:
3439:
3438:
3433:
3422:
3421:
3389:
3384:
3373:
3372:
3334:
3330:
3326:
3321:
3308:
3304:
3300:
3295:
3272:
3270:
3269:
3264:
3252:
3250:
3249:
3244:
3239:
3235:
3234:
3233:
3228:
3207:
3202:
3169:
3167:
3166:
3161:
3159:
3158:
3153:
3111:
3109:
3108:
3103:
3084:
3083:
3082:
3081:
3061:
3060:
3045:
3044:
3043:
3042:
3009:
3007:
3006:
3001:
2996:
2995:
2994:
2993:
2973:
2972:
2964:
2952:
2951:
2950:
2949:
2929:
2928:
2913:
2912:
2907:
2903:
2902:
2901:
2900:
2865:
2863:
2862:
2857:
2855:
2854:
2853:
2852:
2822:
2820:
2819:
2814:
2809:
2808:
2807:
2806:
2790:
2789:
2781:
2774:
2773:
2758:
2757:
2756:
2755:
2718:
2716:
2715:
2710:
2708:
2707:
2692:
2691:
2690:
2689:
2673:
2672:
2664:
2657:
2656:
2655:
2654:
2624:
2622:
2621:
2616:
2611:
2607:
2606:
2582:
2581:
2552:
2550:
2549:
2544:
2542:
2541:
2525:
2523:
2522:
2517:
2515:
2511:
2510:
2486:
2485:
2455:
2453:
2452:
2447:
2439:
2435:
2434:
2429:
2416:
2412:
2411:
2406:
2390:
2389:
2381:
2365:
2363:
2362:
2357:
2355:
2348:
2347:
2346:
2345:
2335:
2334:
2326:
2319:
2318:
2317:
2316:
2296:
2286:
2285:
2284:
2283:
2263:
2262:
2254:
2239:
2238:
2237:
2236:
2226:
2225:
2217:
2210:
2209:
2208:
2207:
2187:
2177:
2176:
2171:
2167:
2166:
2165:
2164:
2163:
2147:
2146:
2138:
2131:
2130:
2129:
2128:
2096:
2085:
2080:
2058:
2057:
2031:
2029:
2028:
2023:
2015:
2011:
2010:
2005:
1989:
1985:
1984:
1979:
1963:
1962:
1961:
1960:
1950:
1949:
1941:
1934:
1933:
1932:
1931:
1914:
1913:
1890:
1888:
1887:
1882:
1880:
1879:
1878:
1877:
1867:
1866:
1858:
1851:
1850:
1849:
1848:
1831:
1830:
1810:
1808:
1807:
1802:
1800:
1795:
1784:
1783:
1775:
1765:
1763:
1762:
1757:
1755:
1750:
1721:
1719:
1718:
1713:
1711:
1706:
1705:
1696:
1682:
1680:
1679:
1674:
1669:
1665:
1664:
1640:
1639:
1602:
1600:
1599:
1594:
1592:
1591:
1585:
1582:
1571:
1566:
1535:
1532:
1514:
1513:
1353:
1351:
1350:
1345:
1343:
1342:
1332:
1331:
1309:
1205:
1202:Moreover, since
1159:) mod 2−1
1127:) mod 2−1
1086:
1085:
1055:
1053:
1052:
1047:
1042:
1032:
1031:
1010:
1009:
1000:
983:
982:
973:
972:
942:
938:
934:
910:shows ϵ(4,
887:
885:
884:
879:
877:
876:
871:
839:
822:
816:
807:
783:
742:
740:
739:
734:
732:
731:
726:
715:
689:
685:
677:
591:
526: = 4.
496:
484:Starting values
467:
417:// Determine if
353:
351:
350:
345:
340:
336:
335:
311:
310:
272:
263:
261:
260:
255:
253:
252:
246:
243:
232:
227:
196:
193:
175:
174:
151:
149:
148:
143:
138:
137:
63:Mersenne numbers
21:
8272:
8271:
8267:
8266:
8265:
8263:
8262:
8261:
8257:Mersenne primes
8252:Primality tests
8242:
8241:
8240:
8235:
8221:
8156:
8118:
8085:
8042:
7986:
7943:
7847:
7809:
7782:Proth's theorem
7724:Primality tests
7718:
7710:
7678:at MersenneWiki
7647:
7646:
7643:
7634:
7620:Pomerance, Carl
7614:
7611:
7606:The Prime Pages
7600:
7596:
7588:
7557:
7552:
7551:
7547:
7538:
7534:
7519:10.2307/2324959
7504:
7503:
7499:
7476:
7458:10.2307/2008415
7442:
7441:
7437:
7428:
7426:
7422:
7415:
7414:
7410:
7382:
7381:
7377:
7368:
7366:
7358:
7357:
7344:
7312:
7307:
7306:
7302:
7298:
7293:
7263:
7262:
7224:
7223:
7191:
7190:
7171:
7170:
7136:
7113:
7112:
7082:
7068:
7067:
7065:
7061:
7028:
6999:
6988:
6987:
6943:
6938:
6937:
6935:
6931:
6927:
6910:
6890:
6862:
6857:
6856:
6825:
6820:
6819:
6802:
6801:
6791:
6775:
6772:
6771:
6761:
6743:
6729:
6708:
6703:
6700:
6699:
6689:
6660:
6659:
6644:
6612:
6611:
6605:
6602:
6601:
6591:
6568:
6567:
6552:
6526:
6525:
6519:
6516:
6515:
6492:
6491:
6476:
6466:
6443:
6442:
6427:
6404:
6403:
6397:
6388:
6387:
6347:
6346:
6312:
6311:
6296:
6291:
6290:
6273:
6272:
6257:
6256:
6246:
6214:
6203:
6202:
6176:
6175:
6169:
6162:
6149:
6144:
6116:
6105:
6104:
6079:
6078:
6072:
6053:
6048:
6035:
6026:
6003:
6002:
5996:
5987:
5986:
5945:
5944:
5938:
5933:
5932:
5902:
5889:
5876:
5875:
5856:
5855:
5823:
5796:
5791:
5786:
5785:
5749:
5728:
5723:
5708:
5703:
5688:
5683:
5666:
5665:
5641:
5640:
5619:
5618:
5581:
5580:
5546:
5545:
5539:
5535:
5517:
5516:
5500:
5491:
5487:
5471:
5466:
5462:
5447:
5442:
5435:
5423:
5418:
5397:
5396:
5360:
5353:
5308:
5307:
5271:
5270:
5239:
5199:
5163:
5162:
5156:
5152:
5119:
5118:
5112:
5108:
5107:
5081:
5080:
5074:
5069:
5068:
5034:
4996:
4995:
4989:
4984:
4983:
4952:
4916:
4910:
4906:
4905:
4886:
4875:
4874:
4849:
4824:
4819:
4818:
4797:
4792:
4791:
4756:
4715:
4714:
4708:
4703:
4702:
4671:
4666:
4665:
4628:
4612:
4611:
4582:
4581:
4532:
4527:
4526:
4498:
4467:
4462:
4461:
4440:
4435:
4434:
4431:
4405:
4400:
4399:
4372:
4359:
4354:
4353:
4323:
4310:
4297:
4292:
4291:
4267:
4262:
4261:
4230:
4211:
4193:
4175:
4170:
4169:
4140:
4135:
4134:
4104:
4099:
4098:
4063:
4058:
4053:
4052:
4028:
4023:
4022:
4003:
4002:
3966:
3961:
3956:
3955:
3932:
3931:
3899:
3894:
3889:
3888:
3840:
3835:
3830:
3829:
3784:
3779:
3769:
3761:
3760:
3732:
3731:
3688:
3683:
3682:
3653:
3613:
3603:
3602:
3597:One element in
3569:
3559:
3558:
3557:* and has size
3518:
3517:
3498:
3497:
3459:
3458:
3453:. The size of
3313:
3309:
3287:
3283:
3278:
3277:
3255:
3254:
3223:
3191:
3187:
3176:
3175:
3148:
3143:
3142:
3136:
3123:
3067:
3062:
3052:
3028:
3023:
3018:
3017:
2979:
2974:
2935:
2930:
2920:
2886:
2881:
2877:
2876:
2871:
2870:
2838:
2833:
2828:
2827:
2826:Multiplying by
2792:
2778:
2765:
2741:
2736:
2731:
2730:
2699:
2675:
2661:
2640:
2635:
2630:
2629:
2598:
2567:
2562:
2561:
2533:
2528:
2527:
2502:
2471:
2466:
2465:
2462:
2421:
2417:
2398:
2394:
2371:
2370:
2353:
2352:
2337:
2323:
2308:
2303:
2294:
2293:
2269:
2264:
2228:
2214:
2199:
2194:
2185:
2184:
2149:
2135:
2114:
2109:
2108:
2104:
2103:
2094:
2093:
2059:
2049:
2040:
2039:
1997:
1993:
1971:
1967:
1952:
1938:
1923:
1918:
1905:
1900:
1899:
1869:
1855:
1840:
1835:
1822:
1817:
1816:
1768:
1767:
1732:
1731:
1697:
1687:
1686:
1656:
1625:
1620:
1619:
1614:
1587:
1586:
1579:
1549:
1548:
1529:
1519:
1505:
1500:
1499:
1493:
1486:
1482:
1438:
1431:
1411:
1406:
1323:
1312:
1292:
1291:
1222:used to square
1203:
1186:
1172:
1158:
1154:
1140:
1126:
1122:
1098:
1023:
1001:
974:
948:
947:
940:
939:operation. The
936:
932:
929:
927:Time complexity
922:
834:
766:
765:
716:
710:
665:
664:
648:
641:
632:
622:
613:
602:
587:
585:
572:
549:Wagstaff number
546:
537:
525:
518:
509:
492:
490:
482:
465:
464:Performing the
462:
425:
409:
400:
390:
375:
367: mod
366:
327:
296:
291:
290:
285:
268:
248:
247:
240:
210:
209:
190:
180:
166:
161:
160:
129:
121:
120:
118:
89:
79:
43:
28:
23:
22:
15:
12:
11:
5:
8270:
8268:
8260:
8259:
8254:
8244:
8243:
8237:
8236:
8234:
8233:
8226:
8223:
8222:
8220:
8219:
8214:
8209:
8204:
8199:
8185:
8180:
8175:
8170:
8164:
8162:
8158:
8157:
8155:
8154:
8149:
8144:
8142:Tonelli–Shanks
8139:
8134:
8128:
8126:
8120:
8119:
8117:
8116:
8111:
8106:
8101:
8095:
8093:
8087:
8086:
8084:
8083:
8078:
8076:Index calculus
8073:
8071:Pohlig–Hellman
8068:
8063:
8058:
8052:
8050:
8044:
8043:
8041:
8040:
8035:
8030:
8025:
8023:Newton-Raphson
8020:
8015:
8010:
8005:
7999:
7997:
7988:
7987:
7985:
7984:
7979:
7974:
7969:
7964:
7959:
7953:
7951:
7949:Multiplication
7945:
7944:
7942:
7941:
7936:
7934:Trial division
7931:
7926:
7921:
7919:Rational sieve
7916:
7909:
7904:
7899:
7891:
7883:
7878:
7873:
7868:
7863:
7857:
7855:
7849:
7848:
7846:
7845:
7840:
7835:
7830:
7825:
7823:Sieve of Atkin
7819:
7817:
7811:
7810:
7808:
7807:
7802:
7797:
7792:
7785:
7778:
7771:
7764:
7759:
7754:
7749:
7747:Elliptic curve
7744:
7739:
7734:
7728:
7726:
7720:
7719:
7711:
7709:
7708:
7701:
7694:
7686:
7680:
7679:
7673:
7668:
7663:
7642:
7641:External links
7639:
7638:
7637:
7632:
7610:
7609:
7594:
7568:(3): 451–454.
7545:
7532:
7513:(4): 370–371.
7497:
7472:
7435:
7408:
7395:(5): 842–846.
7375:
7342:
7299:
7297:
7294:
7292:
7291:
7272:
7246:
7241:
7236:
7232:
7204:
7201:
7178:
7154:
7151:
7148:
7143:
7139:
7135:
7132:
7126:
7123:
7100:
7097:
7094:
7089:
7085:
7081:
7078:
7075:
7059:
7046:
7043:
7040:
7035:
7031:
7027:
7023:
7019:
7016:
7013:
7008:
7003:
6998:
6995:
6974:
6970:
6966:
6961:
6957:
6952:
6947:
6936:Formally, let
6928:
6926:
6923:
6922:
6921:
6916:
6909:
6906:
6889:
6886:
6874:
6869:
6865:
6838:
6835:
6832:
6828:
6816:
6815:
6800:
6797:
6794:
6792:
6788:
6785:
6782:
6778:
6774:
6773:
6770:
6767:
6764:
6762:
6756:
6753:
6750:
6746:
6738:
6735:
6728:
6721:
6718:
6715:
6711:
6706:
6702:
6701:
6698:
6695:
6692:
6690:
6685:
6681:
6678:
6675:
6672:
6667:
6663:
6653:
6650:
6643:
6637:
6633:
6630:
6627:
6624:
6619:
6615:
6608:
6604:
6603:
6600:
6597:
6594:
6592:
6587:
6583:
6580:
6575:
6571:
6561:
6558:
6551:
6545:
6541:
6538:
6533:
6529:
6522:
6518:
6517:
6511:
6507:
6504:
6499:
6495:
6485:
6482:
6475:
6472:
6469:
6467:
6462:
6458:
6455:
6450:
6446:
6436:
6433:
6423:
6419:
6416:
6411:
6407:
6400:
6396:
6395:
6383:, which gives
6372:
6369:
6363:
6360:
6354:
6331:
6327:
6324:
6319:
6315:
6305:
6302:
6287:
6286:
6271:
6268:
6265:
6262:
6260:
6258:
6252:
6249:
6244:
6241:
6238:
6235:
6232:
6229:
6226:
6223:
6220:
6217:
6211:
6208:
6206:
6204:
6195:
6191:
6188:
6183:
6179:
6172:
6168:
6165:
6156:
6152:
6147:
6143:
6140:
6137:
6134:
6131:
6128:
6125:
6122:
6119:
6113:
6110:
6108:
6106:
6098:
6094:
6091:
6086:
6082:
6075:
6068:
6065:
6060:
6056:
6051:
6047:
6044:
6041:
6038:
6032:
6029:
6027:
6022:
6018:
6015:
6010:
6006:
5999:
5995:
5994:
5964:
5960:
5957:
5952:
5948:
5941:
5920:
5915:
5909:
5905:
5901:
5898:
5895:
5892:
5886:
5883:
5863:
5848:
5847:
5835:
5830:
5826:
5821:
5818:
5813:
5810:
5803:
5799:
5794:
5775:
5774:
5761:
5756:
5752:
5747:
5744:
5735:
5731:
5726:
5722:
5715:
5711:
5706:
5702:
5695:
5691:
5686:
5682:
5679:
5676:
5673:
5655:
5654:
5639:
5636:
5633:
5630:
5627:
5624:
5622:
5620:
5615:
5610:
5607:
5604:
5601:
5598:
5595:
5592:
5589:
5586:
5584:
5582:
5577:
5571:
5565:
5561:
5558:
5553:
5549:
5542:
5538:
5534:
5531:
5528:
5525:
5522:
5520:
5518:
5514:
5507:
5503:
5496:
5490:
5485:
5478:
5474:
5469:
5465:
5461:
5454:
5450:
5445:
5441:
5438:
5436:
5430:
5426:
5421:
5417:
5414:
5411:
5408:
5405:
5404:
5377:
5374:
5367:
5363:
5357:
5352:
5349:
5346:
5343:
5340:
5335:
5330:
5327:
5324:
5321:
5318:
5315:
5289:
5284:
5281:
5278:
5267:
5266:
5255:
5251:
5246:
5242:
5237:
5234:
5229:
5226:
5223:
5220:
5217:
5214:
5211:
5206:
5202:
5198:
5195:
5192:
5188:
5182:
5178:
5175:
5170:
5166:
5159:
5155:
5149:
5144:
5138:
5134:
5131:
5126:
5122:
5115:
5111:
5106:
5100:
5096:
5093:
5088:
5084:
5077:
5062:
5061:
5050:
5046:
5041:
5037:
5032:
5029:
5024:
5021:
5015:
5011:
5008:
5003:
4999:
4992:
4968:
4964:
4959:
4955:
4950:
4947:
4940:
4935:
4929:
4925:
4922:
4919:
4913:
4909:
4904:
4899:
4896:
4893:
4889:
4885:
4882:
4861:
4856:
4852:
4847:
4844:
4839:
4836:
4831:
4827:
4804:
4800:
4784:
4783:
4772:
4768:
4763:
4759:
4754:
4751:
4746:
4743:
4740:
4734:
4730:
4727:
4722:
4718:
4711:
4683:
4678:
4674:
4649:
4646:
4643:
4640:
4635:
4631:
4626:
4622:
4619:
4595:
4592:
4589:
4568:
4565:
4561:
4558:
4553:
4550:
4547:
4544:
4539:
4535:
4510:
4505:
4501:
4496:
4493:
4488:
4485:
4480:
4477:
4474:
4470:
4447:
4443:
4430:
4427:
4412:
4408:
4387:
4384:
4379:
4375:
4371:
4366:
4362:
4350:
4349:
4338:
4335:
4330:
4326:
4322:
4317:
4313:
4309:
4304:
4300:
4274:
4270:
4254:
4253:
4242:
4237:
4233:
4229:
4226:
4223:
4218:
4214:
4210:
4206:
4200:
4196:
4191:
4187:
4182:
4178:
4152:
4147:
4143:
4122:
4117:
4114:
4111:
4107:
4086:
4083:
4076:
4073:
4070:
4066:
4061:
4040:
4035:
4031:
4010:
3986:
3981:
3978:
3973:
3969:
3964:
3939:
3928:
3927:
3916:
3913:
3906:
3902:
3897:
3878:
3877:
3866:
3863:
3860:
3853:
3850:
3847:
3843:
3838:
3819:
3818:
3807:
3804:
3797:
3794:
3791:
3787:
3782:
3776:
3772:
3768:
3745:
3742:
3739:
3718:
3715:
3711:
3708:
3703:
3700:
3695:
3691:
3668:
3665:
3660:
3656:
3652:
3649:
3646:
3642:
3638:
3634:
3630:
3626:
3620:
3616:
3611:
3586:
3582:
3576:
3572:
3567:
3531:
3528:
3505:
3479:
3475:
3471:
3467:
3457:is denoted by
3443:
3442:
3431:
3428:
3425:
3418:
3413:
3410:
3407:
3404:
3401:
3398:
3395:
3392:
3387:
3382:
3379:
3376:
3369:
3364:
3361:
3358:
3355:
3352:
3349:
3346:
3343:
3340:
3337:
3333:
3329:
3324:
3319:
3316:
3312:
3307:
3303:
3298:
3293:
3290:
3286:
3273:is defined as
3262:
3242:
3238:
3232:
3227:
3222:
3219:
3216:
3213:
3210:
3205:
3200:
3197:
3194:
3190:
3186:
3183:
3157:
3152:
3132:
3119:
3113:
3112:
3101:
3098:
3095:
3090:
3087:
3080:
3077:
3074:
3070:
3065:
3059:
3055:
3051:
3048:
3041:
3038:
3035:
3031:
3026:
3011:
3010:
2999:
2992:
2989:
2986:
2982:
2977:
2970:
2967:
2961:
2958:
2955:
2948:
2945:
2942:
2938:
2933:
2927:
2923:
2919:
2916:
2911:
2906:
2899:
2896:
2893:
2889:
2884:
2880:
2851:
2848:
2845:
2841:
2836:
2824:
2823:
2812:
2805:
2802:
2799:
2795:
2787:
2784:
2777:
2772:
2768:
2764:
2761:
2754:
2751:
2748:
2744:
2739:
2720:
2719:
2706:
2702:
2698:
2695:
2688:
2685:
2682:
2678:
2670:
2667:
2660:
2653:
2650:
2647:
2643:
2638:
2614:
2610:
2605:
2601:
2596:
2593:
2588:
2585:
2580:
2577:
2574:
2570:
2540:
2536:
2514:
2509:
2505:
2500:
2497:
2492:
2489:
2484:
2481:
2478:
2474:
2461:
2458:
2445:
2442:
2438:
2432:
2427:
2424:
2420:
2415:
2409:
2404:
2401:
2397:
2393:
2387:
2384:
2378:
2367:
2366:
2351:
2344:
2340:
2332:
2329:
2322:
2315:
2311:
2306:
2302:
2299:
2297:
2295:
2292:
2289:
2282:
2279:
2276:
2272:
2267:
2260:
2257:
2251:
2248:
2245:
2242:
2235:
2231:
2223:
2220:
2213:
2206:
2202:
2197:
2193:
2190:
2188:
2186:
2183:
2180:
2175:
2170:
2162:
2159:
2156:
2152:
2144:
2141:
2134:
2127:
2124:
2121:
2117:
2112:
2107:
2102:
2099:
2097:
2095:
2092:
2089:
2084:
2079:
2076:
2073:
2069:
2065:
2062:
2060:
2056:
2052:
2048:
2047:
2033:
2032:
2021:
2018:
2014:
2008:
2003:
2000:
1996:
1992:
1988:
1982:
1977:
1974:
1970:
1966:
1959:
1955:
1947:
1944:
1937:
1930:
1926:
1921:
1917:
1912:
1908:
1876:
1872:
1864:
1861:
1854:
1847:
1843:
1838:
1834:
1829:
1825:
1798:
1793:
1790:
1787:
1781:
1778:
1753:
1748:
1745:
1742:
1739:
1710:
1704:
1700:
1695:
1672:
1668:
1663:
1659:
1654:
1651:
1646:
1643:
1638:
1635:
1632:
1628:
1610:
1604:
1603:
1590:
1580:
1578:
1575:
1570:
1565:
1562:
1559:
1555:
1551:
1550:
1547:
1544:
1541:
1538:
1530:
1528:
1525:
1524:
1522:
1517:
1512:
1508:
1492:
1489:
1484:
1480:
1473:
1472:
1469:
1466:
1463:
1460:
1457:
1454:
1451:
1448:
1436:
1429:
1422:
1421:
1409:
1405:
1402:
1358:-bit numbers.
1341:
1338:
1335:
1330:
1326:
1322:
1319:
1315:
1308:
1305:
1302:
1299:
1198:
1197:
1194:
1191:
1188:
1187:
1184:
1181:
1178:
1175:
1174:
1173:mod 2−1
1170:
1167:
1164:
1161:
1160:
1156:
1152:
1149:
1146:
1143:
1142:
1141:mod 2−1
1138:
1135:
1132:
1129:
1128:
1124:
1120:
1117:
1114:
1111:
1110:
1107:
1104:
1101:
1100:
1099:mod 2−1
1096:
1093:
1090:
1057:
1056:
1045:
1041:
1038:
1035:
1030:
1026:
1021:
1018:
1013:
1008:
1004:
999:
995:
992:
989:
986:
981:
977:
969:
964:
961:
958:
955:
928:
925:
918:
906:OEIS sequence
889:
888:
874:
870:
867:
864:
861:
858:
855:
852:
849:
846:
843:
837:
833:
830:
827:
821:
815:
812:
806:
803:
800:
797:
794:
791:
788:
782:
779:
776:
773:
744:
743:
729:
725:
722:
719:
713:
709:
706:
703:
700:
697:
694:
688:
683:
680:
675:
672:
646:
637:
627:
618:
608:
601:
598:
581:
570:
566:, for example
551:with exponent
542:
533:
523:
514:
505:
488:
481:
478:
421:
416:
405:
395:
388:
376:is called the
371:
361:
355:
354:
343:
339:
334:
330:
325:
322:
317:
314:
309:
306:
303:
299:
281:
265:
264:
251:
241:
239:
236:
231:
226:
223:
220:
216:
212:
211:
208:
205:
202:
199:
191:
189:
186:
185:
183:
178:
173:
169:
141:
136:
132:
128:
114:
104:trial division
85:
78:
75:
59:primality test
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
8269:
8258:
8255:
8253:
8250:
8249:
8247:
8231:
8228:
8227:
8224:
8218:
8215:
8213:
8210:
8208:
8205:
8203:
8200:
8197:
8193:
8189:
8186:
8184:
8181:
8179:
8176:
8174:
8171:
8169:
8166:
8165:
8163:
8159:
8153:
8150:
8148:
8145:
8143:
8140:
8138:
8137:Pocklington's
8135:
8133:
8130:
8129:
8127:
8125:
8121:
8115:
8112:
8110:
8107:
8105:
8102:
8100:
8097:
8096:
8094:
8092:
8088:
8082:
8079:
8077:
8074:
8072:
8069:
8067:
8064:
8062:
8059:
8057:
8054:
8053:
8051:
8049:
8045:
8039:
8036:
8034:
8031:
8029:
8026:
8024:
8021:
8019:
8016:
8014:
8011:
8009:
8006:
8004:
8001:
8000:
7998:
7996:
7993:
7989:
7983:
7980:
7978:
7975:
7973:
7970:
7968:
7965:
7963:
7960:
7958:
7955:
7954:
7952:
7950:
7946:
7940:
7937:
7935:
7932:
7930:
7927:
7925:
7922:
7920:
7917:
7915:
7914:
7910:
7908:
7905:
7903:
7900:
7898:
7896:
7892:
7890:
7888:
7884:
7882:
7881:Pollard's rho
7879:
7877:
7874:
7872:
7869:
7867:
7864:
7862:
7859:
7858:
7856:
7854:
7850:
7844:
7841:
7839:
7836:
7834:
7831:
7829:
7826:
7824:
7821:
7820:
7818:
7816:
7812:
7806:
7803:
7801:
7798:
7796:
7793:
7791:
7790:
7786:
7784:
7783:
7779:
7777:
7776:
7772:
7770:
7769:
7765:
7763:
7760:
7758:
7755:
7753:
7750:
7748:
7745:
7743:
7740:
7738:
7735:
7733:
7730:
7729:
7727:
7725:
7721:
7717:
7714:
7707:
7702:
7700:
7695:
7693:
7688:
7687:
7684:
7677:
7674:
7672:
7669:
7667:
7664:
7659:
7658:
7653:
7650:
7645:
7644:
7640:
7635:
7633:0-387-94777-9
7629:
7625:
7621:
7617:
7613:
7612:
7607:
7603:
7598:
7595:
7587:
7583:
7579:
7575:
7571:
7567:
7563:
7556:
7549:
7546:
7542:
7536:
7533:
7528:
7524:
7520:
7516:
7512:
7508:
7501:
7498:
7494:
7492:
7488:
7484:
7480:
7475:
7468:
7464:
7459:
7454:
7450:
7446:
7439:
7436:
7421:
7420:
7412:
7409:
7403:
7398:
7394:
7390:
7386:
7379:
7376:
7364:
7363:
7355:
7353:
7351:
7349:
7347:
7343:
7338:
7334:
7330:
7326:
7322:
7318:
7311:
7304:
7301:
7295:
7288:
7270:
7260:
7239:
7221:
7199:
7176:
7168:
7149:
7146:
7141:
7137:
7130:
7121:
7095:
7092:
7087:
7083:
7076:
7073:
7063:
7060:
7041:
7038:
7033:
7029:
7021:
7014:
7006:
6996:
6993:
6968:
6964:
6955:
6950:
6933:
6930:
6924:
6920:
6917:
6915:
6912:
6911:
6907:
6905:
6903:
6902:Fermat number
6899:
6895:
6887:
6885:
6872:
6867:
6863:
6854:
6836:
6833:
6830:
6826:
6798:
6795:
6793:
6786:
6783:
6780:
6776:
6768:
6765:
6763:
6754:
6751:
6748:
6744:
6733:
6726:
6719:
6716:
6713:
6709:
6704:
6696:
6693:
6691:
6683:
6679:
6676:
6673:
6670:
6665:
6661:
6648:
6641:
6635:
6631:
6628:
6625:
6622:
6617:
6613:
6606:
6598:
6595:
6593:
6585:
6581:
6578:
6573:
6569:
6556:
6549:
6543:
6539:
6536:
6531:
6527:
6520:
6509:
6505:
6502:
6497:
6493:
6480:
6473:
6470:
6468:
6460:
6456:
6453:
6448:
6444:
6431:
6421:
6417:
6414:
6409:
6405:
6398:
6386:
6385:
6384:
6370:
6367:
6358:
6352:
6329:
6325:
6322:
6317:
6313:
6300:
6269:
6266:
6263:
6261:
6250:
6247:
6239:
6236:
6233:
6224:
6221:
6218:
6209:
6207:
6193:
6189:
6186:
6181:
6177:
6170:
6166:
6163:
6154:
6150:
6141:
6138:
6135:
6126:
6123:
6120:
6111:
6109:
6096:
6092:
6089:
6084:
6080:
6073:
6066:
6063:
6058:
6054:
6045:
6042:
6039:
6030:
6028:
6020:
6016:
6013:
6008:
6004:
5997:
5985:
5984:
5983:
5981:
5962:
5958:
5955:
5950:
5946:
5939:
5918:
5913:
5907:
5899:
5896:
5893:
5884:
5881:
5861:
5853:
5828:
5824:
5819:
5811:
5808:
5801:
5797:
5792:
5784:
5783:
5782:
5780:
5754:
5750:
5745:
5733:
5729:
5724:
5720:
5713:
5709:
5704:
5700:
5693:
5689:
5680:
5677:
5674:
5664:
5663:
5662:
5660:
5637:
5634:
5631:
5628:
5625:
5623:
5613:
5605:
5602:
5596:
5593:
5590:
5587:
5585:
5575:
5569:
5563:
5559:
5556:
5551:
5547:
5540:
5536:
5532:
5529:
5526:
5523:
5521:
5512:
5505:
5501:
5494:
5488:
5483:
5476:
5472:
5467:
5463:
5459:
5452:
5448:
5443:
5439:
5437:
5428:
5424:
5415:
5412:
5409:
5395:
5394:
5393:
5391:
5375:
5365:
5361:
5350:
5347:
5344:
5341:
5338:
5333:
5328:
5325:
5322:
5316:
5313:
5305:
5302:, and define
5287:
5282:
5279:
5276:
5253:
5244:
5240:
5235:
5227:
5224:
5221:
5215:
5212:
5204:
5196:
5190:
5186:
5180:
5176:
5173:
5168:
5164:
5157:
5153:
5147:
5142:
5136:
5132:
5129:
5124:
5120:
5113:
5109:
5104:
5098:
5094:
5091:
5086:
5082:
5075:
5067:
5066:
5065:
5048:
5039:
5035:
5030:
5022:
5019:
5013:
5009:
5006:
5001:
4997:
4990:
4982:
4981:
4980:
4966:
4957:
4953:
4948:
4938:
4933:
4927:
4923:
4920:
4917:
4911:
4907:
4902:
4897:
4894:
4891:
4887:
4883:
4880:
4854:
4850:
4845:
4837:
4834:
4829:
4825:
4802:
4798:
4789:
4770:
4761:
4757:
4752:
4744:
4741:
4738:
4732:
4728:
4725:
4720:
4716:
4709:
4701:
4700:
4699:
4697:
4681:
4676:
4672:
4663:
4647:
4644:
4641:
4633:
4629:
4620:
4609:
4593:
4590:
4587:
4563:
4559:
4551:
4548:
4545:
4542:
4537:
4533:
4523:
4503:
4499:
4494:
4486:
4483:
4478:
4475:
4472:
4468:
4445:
4441:
4428:
4426:
4410:
4406:
4398:. Therefore,
4385:
4382:
4377:
4373:
4369:
4364:
4360:
4336:
4333:
4328:
4324:
4320:
4315:
4311:
4307:
4302:
4298:
4290:
4289:
4288:
4272:
4268:
4259:
4240:
4235:
4231:
4227:
4224:
4221:
4216:
4212:
4208:
4198:
4194:
4185:
4180:
4176:
4168:
4167:
4166:
4163:
4150:
4145:
4141:
4120:
4115:
4112:
4109:
4105:
4084:
4081:
4074:
4071:
4068:
4064:
4059:
4038:
4033:
4029:
4008:
4000:
3984:
3979:
3976:
3971:
3967:
3962:
3953:
3937:
3914:
3911:
3904:
3900:
3895:
3887:
3886:
3885:
3883:
3864:
3861:
3858:
3851:
3848:
3845:
3841:
3836:
3828:
3827:
3826:
3824:
3805:
3802:
3795:
3792:
3789:
3785:
3780:
3774:
3770:
3766:
3759:
3758:
3757:
3743:
3740:
3737:
3713:
3709:
3701:
3698:
3693:
3689:
3679:
3666:
3663:
3658:
3654:
3650:
3647:
3644:
3636:
3628:
3618:
3614:
3600:
3584:
3574:
3570:
3556:
3552:
3548:
3526:
3503:
3495:
3490:
3477:
3469:
3456:
3452:
3449:is itself in
3448:
3429:
3423:
3408:
3405:
3402:
3399:
3396:
3385:
3380:
3374:
3359:
3356:
3353:
3350:
3347:
3344:
3335:
3331:
3327:
3322:
3317:
3314:
3310:
3305:
3301:
3296:
3291:
3288:
3284:
3276:
3275:
3274:
3260:
3240:
3236:
3230:
3220:
3217:
3214:
3211:
3208:
3203:
3198:
3195:
3192:
3188:
3184:
3181:
3173:
3155:
3140:
3135:
3131:
3127:
3122:
3118:
3096:
3088:
3085:
3078:
3075:
3072:
3068:
3063:
3057:
3053:
3049:
3046:
3039:
3036:
3033:
3029:
3024:
3016:
3015:
3014:
2997:
2990:
2987:
2984:
2980:
2965:
2959:
2953:
2946:
2943:
2940:
2936:
2931:
2925:
2921:
2917:
2914:
2909:
2904:
2897:
2894:
2891:
2887:
2882:
2878:
2869:
2868:
2867:
2849:
2846:
2843:
2839:
2834:
2810:
2803:
2800:
2797:
2793:
2782:
2775:
2770:
2766:
2762:
2759:
2752:
2749:
2746:
2742:
2737:
2729:
2728:
2727:
2725:
2704:
2700:
2696:
2693:
2686:
2683:
2680:
2676:
2665:
2658:
2651:
2648:
2645:
2641:
2636:
2628:
2627:
2626:
2612:
2603:
2599:
2594:
2586:
2583:
2578:
2575:
2572:
2568:
2558:
2556:
2538:
2534:
2526:implies that
2507:
2503:
2498:
2490:
2487:
2482:
2479:
2476:
2472:
2459:
2457:
2443:
2440:
2436:
2430:
2425:
2422:
2418:
2413:
2407:
2402:
2399:
2395:
2391:
2382:
2376:
2349:
2342:
2338:
2327:
2320:
2313:
2309:
2304:
2300:
2298:
2290:
2287:
2280:
2277:
2274:
2270:
2255:
2249:
2243:
2240:
2233:
2229:
2218:
2211:
2204:
2200:
2195:
2191:
2189:
2181:
2178:
2173:
2168:
2160:
2157:
2154:
2150:
2139:
2132:
2125:
2122:
2119:
2115:
2110:
2105:
2100:
2098:
2090:
2087:
2082:
2077:
2074:
2071:
2067:
2063:
2061:
2054:
2050:
2038:
2037:
2036:
2019:
2016:
2012:
2006:
2001:
1998:
1994:
1990:
1986:
1980:
1975:
1972:
1968:
1964:
1957:
1953:
1942:
1935:
1928:
1924:
1919:
1915:
1910:
1906:
1898:
1897:
1896:
1894:
1874:
1870:
1859:
1852:
1845:
1841:
1836:
1832:
1827:
1823:
1814:
1796:
1791:
1788:
1785:
1776:
1751:
1746:
1743:
1740:
1737:
1729:
1725:
1702:
1698:
1685:The sequence
1683:
1670:
1661:
1657:
1652:
1644:
1641:
1636:
1633:
1630:
1626:
1618:
1613:
1609:
1576:
1573:
1568:
1563:
1560:
1557:
1553:
1545:
1542:
1539:
1536:
1526:
1520:
1515:
1510:
1506:
1498:
1497:
1496:
1490:
1488:
1478:
1470:
1467:
1464:
1461:
1458:
1455:
1452:
1449:
1446:
1445:
1444:
1442:
1433:
1427:
1419:
1418:
1417:
1415:
1403:
1401:
1399:
1395:
1391:
1387:
1383:
1379:
1375:
1371:
1368:
1365:, requires O(
1364:
1359:
1357:
1336:
1333:
1328:
1324:
1317:
1313:
1306:
1303:
1300:
1297:
1290:, only needs
1289:
1285:
1281:
1277:
1273:
1269:
1265:
1261:
1257:
1253:
1249:
1245:
1241:
1237:
1233:
1229:
1225:
1221:
1216:
1213:
1209:
1195:
1192:
1190:
1189:
1182:
1179:
1177:
1176:
1168:
1165:
1163:
1162:
1150:
1147:
1145:
1144:
1136:
1133:
1131:
1130:
1118:
1115:
1113:
1112:
1108:
1105:
1103:
1102:
1094:
1091:
1088:
1087:
1084:
1082:
1078:
1074:
1070:
1066:
1062:
1043:
1036:
1033:
1028:
1024:
1019:
1006:
1002:
997:
993:
987:
979:
975:
962:
956:
953:
946:
945:
944:
926:
924:
921:
917:
913:
909:
904:
902:
898:
894:
872:
865:
862:
859:
850:
847:
844:
831:
828:
819:
810:
804:
801:
795:
792:
786:
780:
777:
771:
764:
763:
762:
760:
755:
753:
749:
727:
723:
720:
717:
707:
704:
698:
692:
686:
681:
678:
670:
663:
662:
661:
659:
654:
652:
645:
640:
636:
630:
626:
621:
617:
611:
607:
599:
597:
595:
590:
584:
580:
576:
569:
565:
561:
556:
554:
550:
545:
541:
536:
532:
527:
522:
517:
513:
508:
504:
500:
495:
487:
479:
477:
475:
471:
460:
457:
453:
449:
445:
441:
437:
433:
429:
424:
420:
415:
413:
408:
404:
398:
394:
387:
383:
379:
374:
370:
364:
360:
341:
332:
328:
323:
315:
312:
307:
304:
301:
297:
289:
288:
287:
284:
280:
276:
271:
237:
234:
229:
224:
221:
218:
214:
206:
203:
200:
197:
187:
181:
176:
171:
167:
159:
158:
157:
155:
134:
130:
117:
113:
109:
105:
101:
97:
93:
88:
84:
76:
74:
72:
68:
67:Édouard Lucas
64:
60:
56:
52:
48:
41:
37:
33:
19:
8229:
7911:
7894:
7886:
7805:Miller–Rabin
7787:
7780:
7773:
7768:Lucas–Lehmer
7767:
7766:
7655:
7623:
7597:
7586:the original
7565:
7561:
7548:
7535:
7510:
7506:
7500:
7490:
7486:
7482:
7478:
7473:
7470:
7448:
7444:
7438:
7427:. Retrieved
7418:
7411:
7392:
7388:
7378:
7367:. Retrieved
7361:
7320:
7316:
7303:
7286:
7261:which sends
7258:
7219:
7166:
7062:
6932:
6898:Pépin's test
6891:
6888:Applications
6852:
6817:
6288:
5979:
5978:in the ring
5851:
5849:
5776:
5656:
5389:
5303:
5268:
5063:
4785:
4524:
4432:
4351:
4257:
4255:
4164:
3951:
3929:
3881:
3879:
3822:
3820:
3680:
3598:
3554:
3550:
3546:
3493:
3491:
3454:
3450:
3446:
3444:
3171:
3138:
3133:
3129:
3125:
3120:
3116:
3114:
3012:
2825:
2723:
2721:
2559:
2555:group theory
2463:
2368:
2034:
1892:
1684:
1611:
1607:
1605:
1494:
1476:
1474:
1440:
1434:
1425:
1423:
1413:
1407:
1393:
1389:
1385:
1381:
1377:
1373:
1369:
1366:
1360:
1355:
1283:
1279:
1275:
1271:
1267:
1263:
1259:
1255:
1243:
1239:
1235:
1231:
1223:
1217:
1211:
1207:
1201:
1080:
1076:
1072:
1068:
1064:
1060:
1058:
930:
919:
915:
911:
905:
900:
896:
892:
890:
758:
756:
751:
747:
745:
657:
655:
650:
643:
638:
634:
628:
624:
619:
615:
609:
605:
603:
582:
578:
574:
567:
563:
559:
557:
552:
543:
539:
534:
530:
528:
520:
515:
511:
506:
502:
485:
483:
469:
463:
458:
455:
451:
447:
443:
439:
435:
432:Lucas–Lehmer
431:
427:
422:
418:
406:
402:
396:
392:
385:
381:
377:
372:
368:
362:
358:
356:
282:
278:
266:
153:
115:
111:
107:
99:
91:
86:
82:
80:
54:
50:
44:
31:
8061:Pollard rho
8018:Goldschmidt
7752:Pocklington
7742:Baillie–PSW
5781:, which is
5661:, which is
2460:Sufficiency
357:The number
47:mathematics
8246:Categories
8173:Cornacchia
8168:Chakravala
7716:algorithms
7429:2018-12-17
7369:2018-12-17
7296:References
7066:Formally,
4425:is prime.
3174:, and let
1583:otherwise.
1432:is prime.
1204:s × s
1095:1110010100
935:, and the
461:COMPOSITE
438:s = 4
412:pseudocode
244:otherwise.
8147:Berlekamp
8104:Euclidean
7992:Euclidean
7972:Toom–Cook
7967:Karatsuba
7657:MathWorld
7582:120438959
7203:¯
7200:ω
7177:ω
7153:⟩
7147:−
7134:⟨
7125:¯
7122:ω
7099:⟩
7093:−
7080:⟨
7074:ω
7045:⟩
7039:−
7026:⟨
6834:−
6784:−
6752:−
6737:¯
6734:ω
6717:−
6705:ω
6671:−
6652:¯
6649:ω
6623:−
6607:ω
6560:¯
6557:ω
6521:ω
6484:¯
6481:ω
6474:−
6435:¯
6432:ω
6399:ω
6362:¯
6359:ω
6353:ω
6304:¯
6301:ω
6267:−
6248:−
6240:σ
6237:−
6225:σ
6187:−
6167:⋅
6142:σ
6127:σ
6046:σ
5998:ω
5940:ω
5900:σ
5882:ω
5862:σ
5809:≡
5701:≡
5635:σ
5632:−
5603:−
5557:−
5416:σ
5351:∈
5339:∣
5277:σ
5225:−
5222:≡
5213:−
5191:≡
5174:−
5130:−
5105:≡
5092:−
5020:≡
5007:−
4884:≡
4835:≡
4742:−
4739:≡
4726:−
4645:−
4549:≡
4543:−
4484:≡
4476:−
4429:Necessity
4383:−
4334:−
4308:≤
4222:−
4209:≤
4199:∗
4186:≤
4113:−
4082:≠
4072:−
4060:ω
4009:ω
3977:−
3963:ω
3938:ω
3896:ω
3862:−
3849:−
3837:ω
3793:−
3781:ω
3741:∈
3738:ω
3699:≡
3664:−
3645:−
3629:≤
3619:∗
3575:∗
3530:¯
3527:ω
3504:ω
3221:∈
3209:∣
3086:−
3076:−
3064:ω
3037:−
3025:ω
2988:−
2969:¯
2966:ω
2960:ω
2954:−
2944:−
2932:ω
2895:−
2883:ω
2847:−
2835:ω
2801:−
2786:¯
2783:ω
2776:−
2750:−
2738:ω
2684:−
2669:¯
2666:ω
2649:−
2637:ω
2584:≡
2576:−
2488:≡
2480:−
2426:−
2386:¯
2383:ω
2377:ω
2331:¯
2328:ω
2305:ω
2288:−
2278:−
2259:¯
2256:ω
2250:ω
2222:¯
2219:ω
2196:ω
2179:−
2158:−
2143:¯
2140:ω
2123:−
2111:ω
2088:−
2075:−
2002:−
1946:¯
1943:ω
1920:ω
1863:¯
1860:ω
1837:ω
1813:induction
1792:−
1780:¯
1777:ω
1738:ω
1709:⟩
1694:⟨
1642:≡
1634:−
1615:is prime
1574:−
1561:−
1334:
1329:∗
1304:
1034:−
1012:⌋
991:⌊
957:≡
829:−
820:×
796:ϵ
772:ϵ
721:−
705:−
671:ϵ
313:≡
305:−
235:−
222:−
73:in 1930.
8114:Lehmer's
8008:Chunking
7995:division
7924:Fermat's
7489:log log
7337:16831811
6908:See also
6900:for any
6851:is 0 in
6345:and use
4580:for odd
4460:implies
4051:However
4021:divides
3950:lies in
2560:Suppose
1891:for all
1533:if
1404:Examples
1376:log log
1278:log log
1262:log log
1063:bits of
434:(p)
399:−1
277:). Then
194:if
152:for all
77:The test
8230:Italics
8152:Kunerth
8132:Cipolla
8013:Fourier
7982:Fürer's
7876:Euler's
7866:Dixon's
7789:Pépin's
7543:. 2003.
7527:2324959
7481:) to O(
7477:from O(
7467:2008415
7165:are in
4873:and so
4790:modulo
4664:modulo
3545:are in
1726:with a
1282:) or Õ(
1123:+ 11100
908:A123271
649:,
592:in the
589:A001566
497:in the
494:A018844
450:s == 0
430:> 2
273:in the
270:A003010
156:≥ 0 by
94:an odd
57:) is a
8212:Schoof
8099:Binary
8003:Binary
7939:Shor's
7757:Fermat
7630:
7580:
7525:
7465:
7335:
6818:Since
4817:since
4525:Since
3492:Since
3013:Thus,
2866:gives
2625:Then
1730:. Let
1310:
1151:(10000
1137:110000
1119:(10100
823:
817:
808:
784:
690:
459:return
454:PRIME
452:return
444:repeat
410:). In
106:since
49:, the
34:, see
8033:Short
7762:Lucas
7589:(PDF)
7578:S2CID
7558:(PDF)
7523:JSTOR
7463:JSTOR
7423:(PDF)
7333:S2CID
7313:(PDF)
6925:Notes
4610:that
4287:, so
3999:order
3930:Thus
3756:, so
2726:, so
1815:that
1722:is a
1183:10001
1169:10001
941:mod M
937:mod M
466:mod M
96:prime
8028:Long
7962:Long
7628:ISBN
7485:log
7189:and
7111:and
6986:and
5269:Let
4591:>
4370:<
4256:But
4228:<
3730:and
3681:Now
3516:and
2035:and
1766:and
1372:log
1274:log
1258:log
1196:17.
594:OEIS
499:OEIS
456:else
401:mod
275:OEIS
61:for
8192:LLL
8038:SRT
7897:+ 1
7889:− 1
7737:APR
7732:AKS
7570:doi
7515:doi
7511:100
7453:doi
7397:doi
7325:doi
7285:to
7257:to
5982:as
5820:mod
5746:mod
5236:mod
5031:mod
4949:mod
4846:mod
4753:mod
4694:By
4560:mod
4495:mod
4001:of
3880:in
3821:in
3710:mod
3417:mod
3368:mod
2595:mod
2499:mod
1653:mod
1617:iff
1325:log
1301:log
1155:+ 1
1020:mod
968:mod
653:).
604:If
596:).
583:127
440:var
436:var
380:of
324:mod
55:LLT
45:In
8248::
8196:KZ
8194:;
7654:.
7618:;
7604:,
7576:.
7566:34
7564:.
7560:.
7521:.
7509:.
7469:,
7461:,
7449:56
7447:,
7391:.
7387:.
7345:^
7331:.
7321:54
7319:.
7315:.
6799:0.
6270:1.
6251:24
6171:24
6164:24
6074:24
5914:24
5076:24
4648:1.
4564:12
4337:1.
3915:1.
3667:1.
3089:1.
2444:1.
1895::
1485:11
1481:11
1437:11
923:.
778:10
631:−3
612:−2
555:.
476:.
448:if
8198:)
8190:(
7895:p
7887:p
7705:e
7698:t
7691:v
7660:.
7572::
7529:.
7517::
7491:p
7487:p
7483:p
7479:p
7474:p
7455::
7432:.
7405:.
7399::
7393:5
7372:.
7339:.
7327::
7289:.
7287:T
7271:3
7259:X
7245:]
7240:3
7235:[
7231:Z
7220:X
7167:X
7150:3
7142:2
7138:T
7131:+
7096:3
7088:2
7084:T
7077:+
7057:.
7042:3
7034:2
7030:T
7022:/
7018:]
7015:T
7012:[
7007:q
7002:Z
6997:=
6994:X
6973:Z
6969:q
6965:/
6960:Z
6956:=
6951:q
6946:Z
6873:.
6868:p
6864:M
6853:X
6837:2
6831:p
6827:s
6796:=
6787:2
6781:p
6777:s
6769:0
6766:=
6755:2
6749:p
6745:2
6727:+
6720:2
6714:p
6710:2
6697:0
6694:=
6684:4
6680:1
6677:+
6674:1
6666:p
6662:2
6642:+
6636:4
6632:1
6629:+
6626:1
6618:p
6614:2
6599:0
6596:=
6586:4
6582:1
6579:+
6574:p
6570:M
6550:+
6544:4
6540:1
6537:+
6532:p
6528:M
6510:4
6506:1
6503:+
6498:p
6494:M
6471:=
6461:4
6457:1
6454:+
6449:p
6445:M
6422:2
6418:1
6415:+
6410:p
6406:M
6371:1
6368:=
6330:4
6326:1
6323:+
6318:p
6314:M
6264:=
6243:)
6234:6
6231:(
6228:)
6222:+
6219:6
6216:(
6210:=
6194:2
6190:1
6182:p
6178:M
6155:p
6151:M
6146:)
6139:+
6136:6
6133:(
6130:)
6124:+
6121:6
6118:(
6112:=
6097:2
6093:1
6090:+
6085:p
6081:M
6067:1
6064:+
6059:p
6055:M
6050:)
6043:+
6040:6
6037:(
6031:=
6021:2
6017:1
6014:+
6009:p
6005:M
5980:X
5963:2
5959:1
5956:+
5951:p
5947:M
5919:.
5908:2
5904:)
5897:+
5894:6
5891:(
5885:=
5852:a
5834:)
5829:p
5825:M
5817:(
5812:a
5802:p
5798:M
5793:a
5773:,
5760:)
5755:p
5751:M
5743:(
5734:p
5730:M
5725:y
5721:+
5714:p
5710:M
5705:x
5694:p
5690:M
5685:)
5681:y
5678:+
5675:x
5672:(
5638:,
5629:6
5626:=
5614:3
5609:)
5606:1
5600:(
5597:2
5594:+
5591:6
5588:=
5576:3
5570:)
5564:2
5560:1
5552:p
5548:M
5541:3
5537:(
5533:2
5530:+
5527:6
5524:=
5513:)
5506:p
5502:M
5495:3
5489:(
5484:)
5477:p
5473:M
5468:2
5464:(
5460:+
5453:p
5449:M
5444:6
5440:=
5429:p
5425:M
5420:)
5413:+
5410:6
5407:(
5390:X
5376:.
5373:}
5366:p
5362:M
5356:Z
5348:b
5345:,
5342:a
5334:3
5329:b
5326:+
5323:a
5320:{
5317:=
5314:X
5304:X
5288:3
5283:2
5280:=
5254:.
5250:)
5245:p
5241:M
5233:(
5228:1
5219:)
5216:1
5210:(
5205:3
5201:)
5197:1
5194:(
5187:)
5181:2
5177:1
5169:p
5165:M
5158:3
5154:(
5148:3
5143:)
5137:2
5133:1
5125:p
5121:M
5114:2
5110:(
5099:2
5095:1
5087:p
5083:M
5049:.
5045:)
5040:p
5036:M
5028:(
5023:1
5014:2
5010:1
5002:p
4998:M
4991:2
4967:.
4963:)
4958:p
4954:M
4946:(
4939:2
4934:)
4928:2
4924:1
4921:+
4918:p
4912:2
4908:(
4903:=
4898:1
4895:+
4892:p
4888:2
4881:2
4860:)
4855:p
4851:M
4843:(
4838:1
4830:p
4826:2
4803:p
4799:M
4771:.
4767:)
4762:p
4758:M
4750:(
4745:1
4733:2
4729:1
4721:p
4717:M
4710:3
4682:.
4677:p
4673:M
4642:=
4639:)
4634:p
4630:M
4625:|
4621:3
4618:(
4594:1
4588:p
4567:)
4557:(
4552:7
4546:1
4538:p
4534:2
4509:)
4504:p
4500:M
4492:(
4487:0
4479:2
4473:p
4469:s
4446:p
4442:M
4411:p
4407:M
4386:1
4378:p
4374:2
4365:p
4361:2
4329:p
4325:2
4321:=
4316:p
4312:M
4303:2
4299:q
4273:p
4269:M
4258:q
4241:.
4236:2
4232:q
4225:1
4217:2
4213:q
4205:|
4195:X
4190:|
4181:p
4177:2
4151:.
4146:p
4142:2
4121:.
4116:1
4110:p
4106:2
4085:1
4075:1
4069:p
4065:2
4039:.
4034:p
4030:2
3985:.
3980:1
3972:p
3968:2
3952:X
3912:=
3905:p
3901:2
3882:X
3865:1
3859:=
3852:1
3846:p
3842:2
3823:X
3806:0
3803:=
3796:2
3790:p
3786:2
3775:p
3771:M
3767:k
3744:X
3717:)
3714:q
3707:(
3702:0
3694:p
3690:M
3659:2
3655:q
3651:=
3648:1
3641:|
3637:X
3633:|
3625:|
3615:X
3610:|
3599:X
3585:.
3581:|
3571:X
3566:|
3555:X
3551:X
3547:X
3494:q
3478:.
3474:|
3470:X
3466:|
3455:X
3451:X
3447:X
3430:.
3427:]
3424:q
3412:)
3409:c
3406:b
3403:+
3400:d
3397:a
3394:(
3391:[
3386:3
3381:+
3378:]
3375:q
3363:)
3360:d
3357:b
3354:3
3351:+
3348:c
3345:a
3342:(
3339:[
3336:=
3332:)
3328:d
3323:3
3318:+
3315:c
3311:(
3306:)
3302:b
3297:3
3292:+
3289:a
3285:(
3261:X
3241:.
3237:}
3231:q
3226:Z
3218:b
3215:,
3212:a
3204:3
3199:b
3196:+
3193:a
3189:{
3185:=
3182:X
3172:q
3156:q
3151:Z
3139:q
3134:p
3130:M
3126:q
3121:p
3117:M
3100:)
3097:1
3094:(
3079:2
3073:p
3069:2
3058:p
3054:M
3050:k
3047:=
3040:1
3034:p
3030:2
2998:.
2991:2
2985:p
2981:2
2976:)
2957:(
2947:2
2941:p
2937:2
2926:p
2922:M
2918:k
2915:=
2910:2
2905:)
2898:2
2892:p
2888:2
2879:(
2850:2
2844:p
2840:2
2811:.
2804:2
2798:p
2794:2
2771:p
2767:M
2763:k
2760:=
2753:2
2747:p
2743:2
2724:k
2705:p
2701:M
2697:k
2694:=
2687:2
2681:p
2677:2
2659:+
2652:2
2646:p
2642:2
2613:.
2609:)
2604:p
2600:M
2592:(
2587:0
2579:2
2573:p
2569:s
2539:p
2535:M
2513:)
2508:p
2504:M
2496:(
2491:0
2483:2
2477:p
2473:s
2441:=
2437:)
2431:3
2423:2
2419:(
2414:)
2408:3
2403:+
2400:2
2396:(
2392:=
2350:.
2343:n
2339:2
2321:+
2314:n
2310:2
2301:=
2291:2
2281:1
2275:n
2271:2
2266:)
2247:(
2244:2
2241:+
2234:n
2230:2
2212:+
2205:n
2201:2
2192:=
2182:2
2174:2
2169:)
2161:1
2155:n
2151:2
2133:+
2126:1
2120:n
2116:2
2106:(
2101:=
2091:2
2083:2
2078:1
2072:n
2068:s
2064:=
2055:n
2051:s
2020:4
2017:=
2013:)
2007:3
1999:2
1995:(
1991:+
1987:)
1981:3
1976:+
1973:2
1969:(
1965:=
1958:0
1954:2
1936:+
1929:0
1925:2
1916:=
1911:0
1907:s
1893:i
1875:i
1871:2
1853:+
1846:i
1842:2
1833:=
1828:i
1824:s
1797:3
1789:2
1786:=
1752:3
1747:+
1744:2
1741:=
1703:i
1699:s
1671:.
1667:)
1662:p
1658:M
1650:(
1645:0
1637:2
1631:p
1627:s
1612:p
1608:M
1577:2
1569:2
1564:1
1558:i
1554:s
1546:;
1543:0
1540:=
1537:i
1527:4
1521:{
1516:=
1511:i
1507:s
1477:s
1441:s
1430:3
1426:s
1414:s
1410:3
1394:n
1390:k
1386:k
1382:n
1378:n
1374:n
1370:n
1367:k
1356:p
1340:)
1337:p
1321:(
1318:O
1314:2
1307:p
1298:p
1284:p
1280:p
1276:p
1272:p
1268:p
1264:p
1260:p
1256:p
1244:p
1240:p
1236:p
1232:p
1230:(
1228:O
1224:s
1212:p
1208:p
1193:=
1185:2
1180:=
1171:2
1166:=
1157:2
1153:2
1148:=
1139:2
1134:=
1125:2
1121:2
1116:=
1106:=
1097:2
1092:=
1081:k
1077:n
1073:k
1069:k
1065:k
1061:n
1044:.
1040:)
1037:1
1029:n
1025:2
1017:(
1007:n
1003:2
998:/
994:k
988:+
985:)
980:n
976:2
963:k
960:(
954:k
920:p
916:M
912:p
901:p
897:p
893:p
873:8
869:)
866:3
863:+
860:p
857:(
854:)
851:1
848:+
845:p
842:(
836:)
832:1
826:(
814:)
811:p
805:,
802:4
799:(
793:=
790:)
787:p
781:,
775:(
759:p
752:p
748:p
728:2
724:1
718:p
712:)
708:1
702:(
699:=
696:)
693:p
687:,
682:3
679:2
674:(
658:p
651:p
647:0
644:s
639:p
635:M
629:p
625:s
620:p
616:M
610:p
606:s
579:M
575:p
571:0
568:s
564:p
560:p
553:p
544:p
540:M
535:p
531:M
524:0
521:s
516:p
512:M
507:p
503:M
489:0
486:s
470:p
428:p
423:p
419:M
407:p
403:M
397:p
393:s
389:1
386:s
382:p
373:p
369:M
363:p
359:s
342:.
338:)
333:p
329:M
321:(
316:0
308:2
302:p
298:s
283:p
279:M
238:2
230:2
225:1
219:i
215:s
207:;
204:0
201:=
198:i
188:4
182:{
177:=
172:i
168:s
154:i
140:}
135:i
131:s
127:{
116:p
112:M
108:p
100:p
92:p
87:p
83:M
53:(
42:.
32:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.