1373:
1586:
1961:
1126:
1793:
3566:
4521:
4277:
4379:
4064:
5215:
4175:
3462:
1385:
3194:
3630:
3258:
2701:
2957:
2029:
4678:
2132:
2453:
1368:{\displaystyle t_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}+(t_{1}-u_{1}{\sqrt {D}})^{n}}{2}},\qquad u_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}-(t_{1}-u_{1}{\sqrt {D}})^{n}}{2{\sqrt {D}}}}}
3321:
3066:
2882:
4569:
3687:
1801:
5219:
4614:
76:
2573:
2786:
1118:
772:
3833:
4727:
2292:
898:
721:
578:
425:
670:
625:
491:
383:
536:
3885:
2740:
1005:
845:
808:
3362:
3107:
3003:
2518:
2383:
263:
1665:
217:
163:
3726:
966:
2485:
4760:
304:
4414:
2818:
130:
2067:
937:
463:
355:
3939:
3912:
3780:
3753:
2350:
2319:
2217:
2186:
2159:
1059:
1032:
2629:
2246:
1656:
1623:
3388:
3133:
2596:
3467:
4419:
5084:
4720:
3005:
not 43, so we should not apply the algorithm at all. The reason why the algorithm is not applicable is that a=43 is a quadratic non residue for p=47.
4183:
4282:
3947:
4952:
5280:
4894:
4713:
4823:
4070:
5000:
4798:
1581:{\displaystyle t_{m+n}=t_{m}t_{n}+Du_{m}u_{n},\quad u_{m+n}=t_{m}u_{n}+t_{n}u_{m}\quad {\mbox{and}}\quad t_{n}^{2}-Du_{n}^{2}=N^{n}}
4909:
4947:
4884:
3393:
4828:
4791:
3138:
5089:
4980:
4899:
4889:
3571:
3199:
4765:
2634:
4917:
5170:
2890:
1969:
5165:
5094:
4995:
4619:
5132:
5046:
2072:
5275:
2392:
5211:
5201:
4936:
4930:
4904:
4775:
1956:{\displaystyle t_{1}\equiv t_{p-1}t_{1}+Du_{p-1}u_{1}\quad {\mbox{and}}\quad u_{1}\equiv t_{p-1}u_{1}+t_{1}u_{p-1}}
5196:
5137:
3274:
3019:
2835:
101:
4526:
3643:
5099:
4972:
4818:
4770:
4574:
29:
2527:
5114:
5005:
2745:
1064:
726:
3785:
2796:
The following are 4 examples, corresponding to the 3 different cases in which
Pocklington divided forms of
5225:
5175:
5155:
2251:
854:
675:
541:
388:
4876:
4851:
4780:
5235:
630:
585:
468:
360:
499:
5230:
5122:
5104:
5079:
5041:
4785:
3838:
2706:
971:
813:
1788:{\displaystyle t_{p}\equiv t_{1}^{p}\equiv t_{1},\quad u_{p}\equiv u_{1}^{p}D^{(p-1)/2}\equiv u_{1}}
777:
100:
The algorithm is one of the first efficient methods to solve such a congruence. It was described by
5240:
5206:
5127:
5031:
4990:
4985:
4962:
4866:
3329:
3074:
2962:
2490:
2355:
235:
20:
5071:
5018:
5015:
4856:
4755:
2821:
189:
135:
4812:
4805:
3692:
942:
4689:
Leonard Eugene
Dickson, "History Of The Theory Of Numbers" vol 1 p 222, Chelsea Publishing 1952
2458:
5191:
5147:
4861:
4838:
280:
94:
4386:
2803:
115:
5036:
4700:
H.C. Pocklington, Proceedings of the
Cambridge Philosophical Society, Volume 19, pages 57â58
2037:
907:
433:
325:
3917:
3890:
3758:
3731:
2487:
is congruent to a quadratic non-residue, which is a contradiction. So this loop stops when
2328:
2297:
2195:
2164:
2137:
1037:
1010:
5026:
4925:
3561:{\displaystyle x\equiv \pm y/2\equiv \pm (4a)^{2}/2\equiv \pm 800\equiv \pm 7{\pmod {13}}}
2605:
2222:
1632:
1599:
3367:
3112:
2578:
5056:
4957:
4942:
4846:
4747:
5269:
5051:
4736:
5061:
4516:{\displaystyle 0\equiv t_{4}^{2}+13u_{4}^{2}\equiv 7^{2}-13\cdot 3^{2}{\pmod {17}}}
178:
4705:
4739:
4272:{\displaystyle t_{4}=-299\equiv 7{\pmod {17}},u_{4}=156\equiv 3{\pmod {17}}}
4374:{\displaystyle t_{8}=-68\equiv 0{\pmod {17}},u_{8}=42\equiv 8{\pmod {17}}.}
4059:{\displaystyle t_{2}=t_{1}t_{1}+13u_{1}u_{1}=9-13=-4\equiv 13{\pmod {17}},}
4170:{\displaystyle u_{2}=t_{1}u_{1}+t_{1}u_{1}=3+3\equiv 6{\pmod {17}}.}
4709:
3457:{\displaystyle 10^{2m+1}\equiv 10^{3}\equiv -1{\pmod {13}}}
3189:{\displaystyle x\equiv \pm 18^{6}\equiv \pm 8{\pmod {23}}}
3625:{\displaystyle (\pm 7)^{2}\equiv 49\equiv 10{\pmod {13}}}
3253:{\displaystyle (\pm 8)^{2}\equiv 64\equiv 18{\pmod {23}}}
306:. So there is always a second solution when one is found.
2696:{\displaystyle 0\equiv t_{l}\equiv t_{k}^{2}+Du_{k}^{2}}
5256:
indicate that algorithm is for numbers of special forms
1878:
1522:
4622:
4577:
4529:
4422:
4389:
4285:
4186:
4073:
3950:
3920:
3893:
3841:
3788:
3761:
3734:
3695:
3646:
3574:
3470:
3396:
3370:
3332:
3277:
3202:
3141:
3115:
3077:
3022:
2965:
2952:{\displaystyle x\equiv 43^{(47+1)/2}=43^{12}\equiv 2}
2893:
2887:
This is the first case, according to the algorithm,
2838:
2806:
2748:
2709:
2637:
2608:
2581:
2530:
2493:
2461:
2395:
2358:
2331:
2300:
2254:
2225:
2198:
2167:
2140:
2075:
2040:
2024:{\displaystyle t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0}
1972:
1804:
1668:
1635:
1602:
1388:
1129:
1067:
1040:
1013:
974:
945:
910:
857:
816:
780:
729:
678:
633:
588:
544:
502:
471:
436:
391:
363:
328:
283:
238:
192:
138:
118:
32:
5184:
5146:
5113:
5070:
5014:
4971:
4875:
4837:
4746:
4673:{\displaystyle (\pm 8)^{2}=64\equiv 13{\pmod {17}}}
4672:
4608:
4563:
4515:
4408:
4373:
4271:
4169:
4058:
3933:
3906:
3879:
3827:
3774:
3747:
3720:
3681:
3624:
3560:
3456:
3382:
3356:
3315:
3252:
3188:
3127:
3101:
3060:
2997:
2951:
2876:
2812:
2780:
2734:
2695:
2623:
2590:
2567:
2512:
2479:
2447:
2377:
2344:
2313:
2286:
2240:
2211:
2180:
2153:
2126:
2061:
2023:
1955:
1787:
1650:
1617:
1580:
1367:
1112:
1053:
1026:
999:
960:
931:
892:
839:
802:
766:
715:
664:
619:
572:
530:
485:
457:
419:
377:
349:
298:
257:
211:
157:
124:
70:
2127:{\displaystyle 0\equiv u_{p-1}\equiv 2t_{r}u_{r}}
2448:{\displaystyle t_{m}^{2}-Du_{m}^{2}\equiv N^{m}}
4721:
1120:is a quadratic non-residue. Furthermore, let
8:
3835:is a quadratic nonresidue. Take for example
315:Pocklington separates 3 different cases for
3316:{\displaystyle x^{2}\equiv 10{\pmod {13}}.}
3061:{\displaystyle x^{2}\equiv 18{\pmod {23}}.}
2877:{\displaystyle x^{2}\equiv 43{\pmod {47}}.}
4728:
4714:
4706:
4564:{\displaystyle 3x\equiv \pm 7{\pmod {17}}}
3682:{\displaystyle x^{2}\equiv 13{\pmod {17}}}
186:, an integer which is a quadratic residue
4654:
4636:
4621:
4609:{\displaystyle x\equiv \pm 8{\pmod {17}}}
4590:
4576:
4545:
4528:
4497:
4491:
4472:
4459:
4454:
4438:
4433:
4421:
4394:
4388:
4352:
4334:
4311:
4290:
4284:
4253:
4235:
4212:
4191:
4185:
4148:
4124:
4114:
4101:
4091:
4078:
4072:
4037:
4004:
3994:
3978:
3968:
3955:
3949:
3925:
3919:
3898:
3892:
3865:
3846:
3840:
3819:
3814:
3798:
3793:
3787:
3766:
3760:
3739:
3733:
3700:
3694:
3663:
3651:
3645:
3606:
3588:
3573:
3542:
3516:
3510:
3483:
3469:
3438:
3423:
3401:
3395:
3369:
3331:
3294:
3282:
3276:
3234:
3216:
3201:
3170:
3155:
3140:
3114:
3076:
3039:
3027:
3021:
2983:
2970:
2964:
2937:
2920:
2904:
2892:
2855:
2843:
2837:
2805:
2772:
2753:
2747:
2714:
2708:
2687:
2682:
2666:
2661:
2648:
2636:
2607:
2580:
2559:
2546:
2541:
2529:
2498:
2492:
2471:
2466:
2460:
2439:
2426:
2421:
2405:
2400:
2394:
2363:
2357:
2336:
2330:
2305:
2299:
2278:
2268:
2253:
2224:
2203:
2197:
2172:
2166:
2145:
2139:
2118:
2108:
2086:
2074:
2039:
2003:
1977:
1971:
1941:
1931:
1918:
1902:
1889:
1877:
1870:
1854:
1838:
1822:
1809:
1803:
1779:
1762:
1746:
1736:
1731:
1718:
1704:
1691:
1686:
1673:
1667:
1634:
1601:
1572:
1559:
1554:
1538:
1533:
1521:
1514:
1504:
1491:
1481:
1462:
1448:
1438:
1422:
1412:
1393:
1387:
1355:
1344:
1333:
1327:
1314:
1298:
1287:
1281:
1268:
1258:
1249:
1229:
1218:
1212:
1199:
1183:
1172:
1166:
1153:
1143:
1134:
1128:
1104:
1099:
1083:
1078:
1066:
1045:
1039:
1018:
1012:
979:
973:
944:
909:
882:
856:
829:
815:
785:
779:
752:
728:
692:
677:
638:
632:
593:
587:
558:
543:
507:
501:
479:
478:
470:
435:
405:
390:
371:
370:
362:
327:
282:
243:
237:
193:
191:
139:
137:
117:
71:{\displaystyle x^{2}\equiv a{\pmod {p}},}
49:
37:
31:
2742:is got by solving the linear congruence
4693:
2568:{\displaystyle -Du_{l}^{2}\equiv N^{l}}
2781:{\displaystyle u_{k}x\equiv \pm t_{k}}
1113:{\displaystyle N=t_{1}^{2}-Du_{1}^{2}}
767:{\displaystyle y\equiv \pm (4a)^{m+1}}
3828:{\displaystyle t_{1}^{2}+13u_{1}^{2}}
7:
4523:which leads to solving the equation
627:, 2 is a (quadratic) non-residue so
4662:
4598:
4553:
4505:
4360:
4319:
4261:
4220:
4156:
4045:
3671:
3614:
3550:
3446:
3302:
3242:
3178:
3047:
2863:
2287:{\displaystyle 0\equiv 2t_{s}u_{s}}
1379:The following equalities now hold:
968:, so the equation to solve becomes
893:{\displaystyle x\equiv \pm (p+y)/2}
716:{\displaystyle (4a)^{2m+1}\equiv 1}
573:{\displaystyle x\equiv \pm a^{m+1}}
420:{\displaystyle x\equiv \pm a^{m+1}}
201:
147:
57:
14:
4937:Special number field sieve (SNFS)
4931:General number field sieve (GNFS)
665:{\displaystyle 4^{2m+1}\equiv -1}
620:{\displaystyle a^{2m+1}\equiv -1}
486:{\displaystyle m\in \mathbb {N} }
378:{\displaystyle m\in \mathbb {N} }
531:{\displaystyle a^{2m+1}\equiv 1}
273:is a solution as well and since
4655:
4591:
4546:
4498:
4353:
4312:
4254:
4213:
4149:
4038:
3880:{\displaystyle t_{1}=3,u_{1}=1}
3664:
3607:
3543:
3439:
3295:
3235:
3171:
3040:
2856:
2735:{\displaystyle x^{2}+D\equiv 0}
2455:holds and this would mean that
1998:
1884:
1876:
1713:
1528:
1520:
1457:
1244:
1000:{\displaystyle x^{2}+D\equiv 0}
840:{\displaystyle x\equiv \pm y/2}
194:
165:, unless indicated otherwise.)
140:
50:
4666:
4656:
4633:
4623:
4602:
4592:
4557:
4547:
4509:
4499:
4364:
4354:
4323:
4313:
4265:
4255:
4224:
4214:
4160:
4150:
4049:
4039:
3675:
3665:
3618:
3608:
3585:
3575:
3554:
3544:
3507:
3497:
3450:
3440:
3306:
3296:
3246:
3236:
3213:
3203:
3182:
3172:
3051:
3041:
2917:
2905:
2867:
2857:
1759:
1747:
1341:
1307:
1295:
1261:
1226:
1192:
1180:
1146:
1007:. Now find by trial and error
879:
867:
803:{\displaystyle y^{2}\equiv 4a}
749:
739:
689:
679:
205:
195:
151:
141:
61:
51:
1:
3357:{\displaystyle 13=8\cdot 1+5}
3102:{\displaystyle 23=4\cdot 5+3}
2998:{\displaystyle x^{2}=2^{2}=4}
2513:{\displaystyle t_{l}\equiv 0}
2378:{\displaystyle u_{m}\equiv 0}
258:{\displaystyle x^{2}\equiv a}
19:is a technique for solving a
4895:Lenstra elliptic curve (ECM)
5281:Number theoretic algorithms
3326:The modulus is 13. This is
3071:The modulus is 23. This is
2389:odd is impossible, because
2248:and proceed similarly with
1662:is a quadratic residue and
212:{\displaystyle {\pmod {p}}}
158:{\displaystyle {\pmod {p}}}
5297:
5202:Exponentiation by squaring
4885:Continued fraction (CFRAC)
3721:{\displaystyle x^{2}-13=0}
961:{\displaystyle D\equiv -a}
5249:
3135:. The solution should be
2480:{\displaystyle t_{m}^{2}}
2134:. This means that either
3196:, which is indeed true:
2598:is a quadratic residue,
299:{\displaystyle x\neq -x}
232:, an integer satisfying
5115:Greatest common divisor
4409:{\displaystyle t_{8}=0}
3568:. This is indeed true:
2813:{\displaystyle \equiv }
125:{\displaystyle \equiv }
17:Pocklington's algorithm
5226:Modular exponentiation
4674:
4610:
4565:
4517:
4410:
4375:
4273:
4171:
4060:
3935:
3908:
3881:
3829:
3776:
3749:
3722:
3683:
3626:
3562:
3458:
3384:
3358:
3317:
3254:
3190:
3129:
3103:
3062:
2999:
2953:
2878:
2814:
2782:
2736:
2697:
2625:
2592:
2569:
2514:
2481:
2449:
2379:
2346:
2315:
2288:
2242:
2213:
2182:
2155:
2128:
2063:
2062:{\displaystyle p-1=2r}
2025:
1957:
1789:
1652:
1619:
1582:
1369:
1114:
1055:
1028:
1001:
962:
933:
932:{\displaystyle p=8m+1}
894:
841:
804:
768:
717:
666:
621:
574:
532:
487:
459:
458:{\displaystyle p=8m+5}
421:
379:
351:
350:{\displaystyle p=4m+3}
300:
269:is a solution, −
259:
213:
159:
126:
72:
4953:Shanks's square forms
4877:Integer factorization
4852:Sieve of Eratosthenes
4675:
4611:
4566:
4518:
4411:
4376:
4274:
4172:
4061:
3936:
3934:{\displaystyle u_{8}}
3909:
3907:{\displaystyle t_{8}}
3882:
3830:
3777:
3775:{\displaystyle u_{1}}
3750:
3748:{\displaystyle t_{1}}
3723:
3684:
3640:Solve the congruence
3627:
3563:
3464:. So the solution is
3459:
3385:
3359:
3318:
3268:Solve the congruence
3255:
3191:
3130:
3104:
3063:
3013:Solve the congruence
3000:
2954:
2879:
2815:
2783:
2737:
2703:. So the solution of
2698:
2626:
2593:
2570:
2515:
2482:
2450:
2380:
2347:
2345:{\displaystyle u_{1}}
2316:
2314:{\displaystyle u_{i}}
2289:
2243:
2214:
2212:{\displaystyle u_{r}}
2183:
2181:{\displaystyle u_{r}}
2156:
2154:{\displaystyle t_{r}}
2129:
2064:
2026:
1958:
1790:
1653:
1620:
1583:
1370:
1115:
1056:
1054:{\displaystyle u_{1}}
1029:
1027:{\displaystyle t_{1}}
1002:
963:
934:
895:
842:
805:
769:
718:
667:
622:
575:
533:
488:
460:
422:
380:
352:
301:
260:
214:
160:
127:
73:
5231:Montgomery reduction
5105:Function field sieve
5080:Baby-step giant-step
4926:Quadratic sieve (QS)
4620:
4575:
4571:. This has solution
4527:
4420:
4387:
4283:
4184:
4071:
3948:
3918:
3891:
3839:
3786:
3759:
3732:
3693:
3644:
3572:
3468:
3394:
3368:
3330:
3275:
3200:
3139:
3113:
3075:
3020:
2963:
2891:
2836:
2804:
2746:
2707:
2635:
2624:{\displaystyle l=2k}
2606:
2579:
2528:
2491:
2459:
2393:
2356:
2329:
2298:
2252:
2241:{\displaystyle r=2s}
2223:
2196:
2165:
2138:
2073:
2038:
1970:
1802:
1795:. Now the equations
1666:
1651:{\displaystyle 8m+1}
1633:
1618:{\displaystyle 4m+1}
1600:
1386:
1127:
1065:
1038:
1011:
972:
943:
908:
855:
814:
778:
727:
676:
631:
586:
542:
500:
469:
434:
430:The second case, if
389:
361:
326:
281:
236:
190:
136:
116:
30:
5241:Trachtenberg system
5207:Integer square root
5148:Modular square root
4867:Wheel factorization
4819:Quadratic Frobenius
4799:LucasâLehmerâRiesel
4464:
4443:
3824:
3803:
3383:{\displaystyle m=1}
3128:{\displaystyle m=5}
2820:are taken with the
2692:
2671:
2551:
2476:
2431:
2410:
1741:
1696:
1564:
1543:
1109:
1088:
904:The third case, if
322:The first case, if
5276:Modular arithmetic
5133:Extended Euclidean
5072:Discrete logarithm
5001:SchönhageâStrassen
4857:Sieve of Pritchard
4670:
4606:
4561:
4513:
4450:
4429:
4406:
4371:
4269:
4167:
4056:
3931:
3904:
3877:
3825:
3810:
3789:
3772:
3745:
3718:
3689:. For this, write
3679:
3622:
3558:
3454:
3380:
3354:
3313:
3250:
3186:
3125:
3099:
3058:
2995:
2949:
2874:
2810:
2778:
2732:
2693:
2678:
2657:
2621:
2602:must be even. Put
2591:{\displaystyle -D}
2588:
2565:
2537:
2510:
2477:
2462:
2445:
2417:
2396:
2375:
2342:
2311:
2284:
2238:
2209:
2178:
2151:
2124:
2059:
2021:
1953:
1882:
1785:
1727:
1682:
1648:
1625:(which is true if
1615:
1578:
1550:
1529:
1526:
1365:
1110:
1095:
1074:
1051:
1024:
997:
958:
929:
890:
837:
800:
764:
713:
672:. This means that
662:
617:
570:
538:, the solution is
528:
483:
455:
417:
385:, the solution is
375:
347:
296:
255:
209:
155:
132:are taken to mean
122:
68:
5263:
5262:
4862:Sieve of Sundaram
2520:for a particular
2352:is not. The case
1881:
1525:
1363:
1360:
1338:
1292:
1239:
1223:
1177:
774:is a solution of
95:quadratic residue
89:are integers and
5288:
5212:Integer relation
5185:Other algorithms
5090:Pollard kangaroo
4981:Ancient Egyptian
4839:Prime-generating
4824:SolovayâStrassen
4737:Number-theoretic
4730:
4723:
4716:
4707:
4701:
4698:
4679:
4677:
4676:
4671:
4669:
4641:
4640:
4615:
4613:
4612:
4607:
4605:
4570:
4568:
4567:
4562:
4560:
4522:
4520:
4519:
4514:
4512:
4496:
4495:
4477:
4476:
4463:
4458:
4442:
4437:
4415:
4413:
4412:
4407:
4399:
4398:
4380:
4378:
4377:
4372:
4367:
4339:
4338:
4326:
4295:
4294:
4278:
4276:
4275:
4270:
4268:
4240:
4239:
4227:
4196:
4195:
4176:
4174:
4173:
4168:
4163:
4129:
4128:
4119:
4118:
4106:
4105:
4096:
4095:
4083:
4082:
4065:
4063:
4062:
4057:
4052:
4009:
4008:
3999:
3998:
3983:
3982:
3973:
3972:
3960:
3959:
3940:
3938:
3937:
3932:
3930:
3929:
3913:
3911:
3910:
3905:
3903:
3902:
3886:
3884:
3883:
3878:
3870:
3869:
3851:
3850:
3834:
3832:
3831:
3826:
3823:
3818:
3802:
3797:
3781:
3779:
3778:
3773:
3771:
3770:
3754:
3752:
3751:
3746:
3744:
3743:
3727:
3725:
3724:
3719:
3705:
3704:
3688:
3686:
3685:
3680:
3678:
3656:
3655:
3631:
3629:
3628:
3623:
3621:
3593:
3592:
3567:
3565:
3564:
3559:
3557:
3520:
3515:
3514:
3487:
3463:
3461:
3460:
3455:
3453:
3428:
3427:
3415:
3414:
3390:. Now verifying
3389:
3387:
3386:
3381:
3363:
3361:
3360:
3355:
3322:
3320:
3319:
3314:
3309:
3287:
3286:
3259:
3257:
3256:
3251:
3249:
3221:
3220:
3195:
3193:
3192:
3187:
3185:
3160:
3159:
3134:
3132:
3131:
3126:
3108:
3106:
3105:
3100:
3067:
3065:
3064:
3059:
3054:
3032:
3031:
3004:
3002:
3001:
2996:
2988:
2987:
2975:
2974:
2958:
2956:
2955:
2950:
2942:
2941:
2929:
2928:
2924:
2883:
2881:
2880:
2875:
2870:
2848:
2847:
2824:in the example.
2819:
2817:
2816:
2811:
2787:
2785:
2784:
2779:
2777:
2776:
2758:
2757:
2741:
2739:
2738:
2733:
2719:
2718:
2702:
2700:
2699:
2694:
2691:
2686:
2670:
2665:
2653:
2652:
2630:
2628:
2627:
2622:
2597:
2595:
2594:
2589:
2574:
2572:
2571:
2566:
2564:
2563:
2550:
2545:
2519:
2517:
2516:
2511:
2503:
2502:
2486:
2484:
2483:
2478:
2475:
2470:
2454:
2452:
2451:
2446:
2444:
2443:
2430:
2425:
2409:
2404:
2384:
2382:
2381:
2376:
2368:
2367:
2351:
2349:
2348:
2343:
2341:
2340:
2321:is divisible by
2320:
2318:
2317:
2312:
2310:
2309:
2293:
2291:
2290:
2285:
2283:
2282:
2273:
2272:
2247:
2245:
2244:
2239:
2218:
2216:
2215:
2210:
2208:
2207:
2188:is divisible by
2187:
2185:
2184:
2179:
2177:
2176:
2160:
2158:
2157:
2152:
2150:
2149:
2133:
2131:
2130:
2125:
2123:
2122:
2113:
2112:
2097:
2096:
2068:
2066:
2065:
2060:
2030:
2028:
2027:
2022:
2014:
2013:
1988:
1987:
1966:give a solution
1962:
1960:
1959:
1954:
1952:
1951:
1936:
1935:
1923:
1922:
1913:
1912:
1894:
1893:
1883:
1879:
1875:
1874:
1865:
1864:
1843:
1842:
1833:
1832:
1814:
1813:
1794:
1792:
1791:
1786:
1784:
1783:
1771:
1770:
1766:
1740:
1735:
1723:
1722:
1709:
1708:
1695:
1690:
1678:
1677:
1657:
1655:
1654:
1649:
1624:
1622:
1621:
1616:
1587:
1585:
1584:
1579:
1577:
1576:
1563:
1558:
1542:
1537:
1527:
1523:
1519:
1518:
1509:
1508:
1496:
1495:
1486:
1485:
1473:
1472:
1453:
1452:
1443:
1442:
1427:
1426:
1417:
1416:
1404:
1403:
1374:
1372:
1371:
1366:
1364:
1362:
1361:
1356:
1350:
1349:
1348:
1339:
1334:
1332:
1331:
1319:
1318:
1303:
1302:
1293:
1288:
1286:
1285:
1273:
1272:
1259:
1254:
1253:
1240:
1235:
1234:
1233:
1224:
1219:
1217:
1216:
1204:
1203:
1188:
1187:
1178:
1173:
1171:
1170:
1158:
1157:
1144:
1139:
1138:
1119:
1117:
1116:
1111:
1108:
1103:
1087:
1082:
1060:
1058:
1057:
1052:
1050:
1049:
1033:
1031:
1030:
1025:
1023:
1022:
1006:
1004:
1003:
998:
984:
983:
967:
965:
964:
959:
938:
936:
935:
930:
899:
897:
896:
891:
886:
846:
844:
843:
838:
833:
809:
807:
806:
801:
790:
789:
773:
771:
770:
765:
763:
762:
722:
720:
719:
714:
706:
705:
671:
669:
668:
663:
652:
651:
626:
624:
623:
618:
607:
606:
579:
577:
576:
571:
569:
568:
537:
535:
534:
529:
521:
520:
492:
490:
489:
484:
482:
464:
462:
461:
456:
426:
424:
423:
418:
416:
415:
384:
382:
381:
376:
374:
356:
354:
353:
348:
305:
303:
302:
297:
264:
262:
261:
256:
248:
247:
218:
216:
215:
210:
208:
164:
162:
161:
156:
154:
131:
129:
128:
123:
102:H.C. Pocklington
77:
75:
74:
69:
64:
42:
41:
5296:
5295:
5291:
5290:
5289:
5287:
5286:
5285:
5266:
5265:
5264:
5259:
5245:
5180:
5142:
5109:
5066:
5010:
4967:
4871:
4833:
4806:Proth's theorem
4748:Primality tests
4742:
4734:
4704:
4699:
4695:
4686:
4632:
4618:
4617:
4573:
4572:
4525:
4524:
4487:
4468:
4418:
4417:
4416:, the equation
4390:
4385:
4384:
4330:
4286:
4281:
4280:
4231:
4187:
4182:
4181:
4120:
4110:
4097:
4087:
4074:
4069:
4068:
4000:
3990:
3974:
3964:
3951:
3946:
3945:
3921:
3916:
3915:
3894:
3889:
3888:
3861:
3842:
3837:
3836:
3784:
3783:
3762:
3757:
3756:
3735:
3730:
3729:
3728:. First find a
3696:
3691:
3690:
3647:
3642:
3641:
3638:
3584:
3570:
3569:
3506:
3466:
3465:
3419:
3397:
3392:
3391:
3366:
3365:
3328:
3327:
3278:
3273:
3272:
3266:
3212:
3198:
3197:
3151:
3137:
3136:
3111:
3110:
3073:
3072:
3023:
3018:
3017:
3011:
2979:
2966:
2961:
2960:
2933:
2900:
2889:
2888:
2839:
2834:
2833:
2830:
2802:
2801:
2794:
2768:
2749:
2744:
2743:
2710:
2705:
2704:
2644:
2633:
2632:
2604:
2603:
2577:
2576:
2555:
2526:
2525:
2494:
2489:
2488:
2457:
2456:
2435:
2391:
2390:
2359:
2354:
2353:
2332:
2327:
2326:
2301:
2296:
2295:
2274:
2264:
2250:
2249:
2221:
2220:
2199:
2194:
2193:
2168:
2163:
2162:
2141:
2136:
2135:
2114:
2104:
2082:
2071:
2070:
2036:
2035:
1999:
1973:
1968:
1967:
1937:
1927:
1914:
1898:
1885:
1866:
1850:
1834:
1818:
1805:
1800:
1799:
1775:
1742:
1714:
1700:
1669:
1664:
1663:
1631:
1630:
1629:is of the form
1598:
1597:
1596:is of the form
1592:Supposing that
1568:
1510:
1500:
1487:
1477:
1458:
1444:
1434:
1418:
1408:
1389:
1384:
1383:
1351:
1340:
1323:
1310:
1294:
1277:
1264:
1260:
1245:
1225:
1208:
1195:
1179:
1162:
1149:
1145:
1130:
1125:
1124:
1063:
1062:
1041:
1036:
1035:
1014:
1009:
1008:
975:
970:
969:
941:
940:
906:
905:
853:
852:
812:
811:
781:
776:
775:
748:
725:
724:
688:
674:
673:
634:
629:
628:
589:
584:
583:
554:
540:
539:
503:
498:
497:
467:
466:
432:
431:
401:
387:
386:
359:
358:
324:
323:
313:
311:Solution method
279:
278:
265:. Note that if
239:
234:
233:
188:
187:
134:
133:
114:
113:
110:
33:
28:
27:
12:
11:
5:
5294:
5292:
5284:
5283:
5278:
5268:
5267:
5261:
5260:
5258:
5257:
5250:
5247:
5246:
5244:
5243:
5238:
5233:
5228:
5223:
5209:
5204:
5199:
5194:
5188:
5186:
5182:
5181:
5179:
5178:
5173:
5168:
5166:TonelliâShanks
5163:
5158:
5152:
5150:
5144:
5143:
5141:
5140:
5135:
5130:
5125:
5119:
5117:
5111:
5110:
5108:
5107:
5102:
5100:Index calculus
5097:
5095:PohligâHellman
5092:
5087:
5082:
5076:
5074:
5068:
5067:
5065:
5064:
5059:
5054:
5049:
5047:Newton-Raphson
5044:
5039:
5034:
5029:
5023:
5021:
5012:
5011:
5009:
5008:
5003:
4998:
4993:
4988:
4983:
4977:
4975:
4973:Multiplication
4969:
4968:
4966:
4965:
4960:
4958:Trial division
4955:
4950:
4945:
4943:Rational sieve
4940:
4933:
4928:
4923:
4915:
4907:
4902:
4897:
4892:
4887:
4881:
4879:
4873:
4872:
4870:
4869:
4864:
4859:
4854:
4849:
4847:Sieve of Atkin
4843:
4841:
4835:
4834:
4832:
4831:
4826:
4821:
4816:
4809:
4802:
4795:
4788:
4783:
4778:
4773:
4771:Elliptic curve
4768:
4763:
4758:
4752:
4750:
4744:
4743:
4735:
4733:
4732:
4725:
4718:
4710:
4703:
4702:
4692:
4691:
4690:
4685:
4682:
4668:
4665:
4661:
4658:
4653:
4650:
4647:
4644:
4639:
4635:
4631:
4628:
4625:
4604:
4601:
4597:
4594:
4589:
4586:
4583:
4580:
4559:
4556:
4552:
4549:
4544:
4541:
4538:
4535:
4532:
4511:
4508:
4504:
4501:
4494:
4490:
4486:
4483:
4480:
4475:
4471:
4467:
4462:
4457:
4453:
4449:
4446:
4441:
4436:
4432:
4428:
4425:
4405:
4402:
4397:
4393:
4370:
4366:
4363:
4359:
4356:
4351:
4348:
4345:
4342:
4337:
4333:
4329:
4325:
4322:
4318:
4315:
4310:
4307:
4304:
4301:
4298:
4293:
4289:
4267:
4264:
4260:
4257:
4252:
4249:
4246:
4243:
4238:
4234:
4230:
4226:
4223:
4219:
4216:
4211:
4208:
4205:
4202:
4199:
4194:
4190:
4180:And similarly
4178:
4177:
4166:
4162:
4159:
4155:
4152:
4147:
4144:
4141:
4138:
4135:
4132:
4127:
4123:
4117:
4113:
4109:
4104:
4100:
4094:
4090:
4086:
4081:
4077:
4066:
4055:
4051:
4048:
4044:
4041:
4036:
4033:
4030:
4027:
4024:
4021:
4018:
4015:
4012:
4007:
4003:
3997:
3993:
3989:
3986:
3981:
3977:
3971:
3967:
3963:
3958:
3954:
3928:
3924:
3901:
3897:
3876:
3873:
3868:
3864:
3860:
3857:
3854:
3849:
3845:
3822:
3817:
3813:
3809:
3806:
3801:
3796:
3792:
3769:
3765:
3742:
3738:
3717:
3714:
3711:
3708:
3703:
3699:
3677:
3674:
3670:
3667:
3662:
3659:
3654:
3650:
3637:
3634:
3620:
3617:
3613:
3610:
3605:
3602:
3599:
3596:
3591:
3587:
3583:
3580:
3577:
3556:
3553:
3549:
3546:
3541:
3538:
3535:
3532:
3529:
3526:
3523:
3519:
3513:
3509:
3505:
3502:
3499:
3496:
3493:
3490:
3486:
3482:
3479:
3476:
3473:
3452:
3449:
3445:
3442:
3437:
3434:
3431:
3426:
3422:
3418:
3413:
3410:
3407:
3404:
3400:
3379:
3376:
3373:
3353:
3350:
3347:
3344:
3341:
3338:
3335:
3324:
3323:
3312:
3308:
3305:
3301:
3298:
3293:
3290:
3285:
3281:
3265:
3262:
3248:
3245:
3241:
3238:
3233:
3230:
3227:
3224:
3219:
3215:
3211:
3208:
3205:
3184:
3181:
3177:
3174:
3169:
3166:
3163:
3158:
3154:
3150:
3147:
3144:
3124:
3121:
3118:
3098:
3095:
3092:
3089:
3086:
3083:
3080:
3069:
3068:
3057:
3053:
3050:
3046:
3043:
3038:
3035:
3030:
3026:
3010:
3007:
2994:
2991:
2986:
2982:
2978:
2973:
2969:
2948:
2945:
2940:
2936:
2932:
2927:
2923:
2919:
2916:
2913:
2910:
2907:
2903:
2899:
2896:
2885:
2884:
2873:
2869:
2866:
2862:
2859:
2854:
2851:
2846:
2842:
2829:
2826:
2809:
2793:
2790:
2775:
2771:
2767:
2764:
2761:
2756:
2752:
2731:
2728:
2725:
2722:
2717:
2713:
2690:
2685:
2681:
2677:
2674:
2669:
2664:
2660:
2656:
2651:
2647:
2643:
2640:
2620:
2617:
2614:
2611:
2587:
2584:
2575:, and because
2562:
2558:
2554:
2549:
2544:
2540:
2536:
2533:
2509:
2506:
2501:
2497:
2474:
2469:
2465:
2442:
2438:
2434:
2429:
2424:
2420:
2416:
2413:
2408:
2403:
2399:
2374:
2371:
2366:
2362:
2339:
2335:
2308:
2304:
2281:
2277:
2271:
2267:
2263:
2260:
2257:
2237:
2234:
2231:
2228:
2206:
2202:
2175:
2171:
2148:
2144:
2121:
2117:
2111:
2107:
2103:
2100:
2095:
2092:
2089:
2085:
2081:
2078:
2058:
2055:
2052:
2049:
2046:
2043:
2020:
2017:
2012:
2009:
2006:
2002:
1997:
1994:
1991:
1986:
1983:
1980:
1976:
1964:
1963:
1950:
1947:
1944:
1940:
1934:
1930:
1926:
1921:
1917:
1911:
1908:
1905:
1901:
1897:
1892:
1888:
1873:
1869:
1863:
1860:
1857:
1853:
1849:
1846:
1841:
1837:
1831:
1828:
1825:
1821:
1817:
1812:
1808:
1782:
1778:
1774:
1769:
1765:
1761:
1758:
1755:
1752:
1749:
1745:
1739:
1734:
1730:
1726:
1721:
1717:
1712:
1707:
1703:
1699:
1694:
1689:
1685:
1681:
1676:
1672:
1647:
1644:
1641:
1638:
1614:
1611:
1608:
1605:
1590:
1589:
1575:
1571:
1567:
1562:
1557:
1553:
1549:
1546:
1541:
1536:
1532:
1517:
1513:
1507:
1503:
1499:
1494:
1490:
1484:
1480:
1476:
1471:
1468:
1465:
1461:
1456:
1451:
1447:
1441:
1437:
1433:
1430:
1425:
1421:
1415:
1411:
1407:
1402:
1399:
1396:
1392:
1377:
1376:
1359:
1354:
1347:
1343:
1337:
1330:
1326:
1322:
1317:
1313:
1309:
1306:
1301:
1297:
1291:
1284:
1280:
1276:
1271:
1267:
1263:
1257:
1252:
1248:
1243:
1238:
1232:
1228:
1222:
1215:
1211:
1207:
1202:
1198:
1194:
1191:
1186:
1182:
1176:
1169:
1165:
1161:
1156:
1152:
1148:
1142:
1137:
1133:
1107:
1102:
1098:
1094:
1091:
1086:
1081:
1077:
1073:
1070:
1048:
1044:
1021:
1017:
996:
993:
990:
987:
982:
978:
957:
954:
951:
948:
928:
925:
922:
919:
916:
913:
902:
901:
889:
885:
881:
878:
875:
872:
869:
866:
863:
860:
836:
832:
828:
825:
822:
819:
799:
796:
793:
788:
784:
761:
758:
755:
751:
747:
744:
741:
738:
735:
732:
712:
709:
704:
701:
698:
695:
691:
687:
684:
681:
661:
658:
655:
650:
647:
644:
641:
637:
616:
613:
610:
605:
602:
599:
596:
592:
581:
567:
564:
561:
557:
553:
550:
547:
527:
524:
519:
516:
513:
510:
506:
481:
477:
474:
454:
451:
448:
445:
442:
439:
414:
411:
408:
404:
400:
397:
394:
373:
369:
366:
346:
343:
340:
337:
334:
331:
312:
309:
308:
307:
295:
292:
289:
286:
254:
251:
246:
242:
221:
220:
207:
204:
200:
197:
181:
153:
150:
146:
143:
121:
109:
106:
79:
78:
67:
63:
60:
56:
53:
48:
45:
40:
36:
13:
10:
9:
6:
4:
3:
2:
5293:
5282:
5279:
5277:
5274:
5273:
5271:
5255:
5252:
5251:
5248:
5242:
5239:
5237:
5234:
5232:
5229:
5227:
5224:
5221:
5217:
5213:
5210:
5208:
5205:
5203:
5200:
5198:
5195:
5193:
5190:
5189:
5187:
5183:
5177:
5174:
5172:
5169:
5167:
5164:
5162:
5161:Pocklington's
5159:
5157:
5154:
5153:
5151:
5149:
5145:
5139:
5136:
5134:
5131:
5129:
5126:
5124:
5121:
5120:
5118:
5116:
5112:
5106:
5103:
5101:
5098:
5096:
5093:
5091:
5088:
5086:
5083:
5081:
5078:
5077:
5075:
5073:
5069:
5063:
5060:
5058:
5055:
5053:
5050:
5048:
5045:
5043:
5040:
5038:
5035:
5033:
5030:
5028:
5025:
5024:
5022:
5020:
5017:
5013:
5007:
5004:
5002:
4999:
4997:
4994:
4992:
4989:
4987:
4984:
4982:
4979:
4978:
4976:
4974:
4970:
4964:
4961:
4959:
4956:
4954:
4951:
4949:
4946:
4944:
4941:
4939:
4938:
4934:
4932:
4929:
4927:
4924:
4922:
4920:
4916:
4914:
4912:
4908:
4906:
4905:Pollard's rho
4903:
4901:
4898:
4896:
4893:
4891:
4888:
4886:
4883:
4882:
4880:
4878:
4874:
4868:
4865:
4863:
4860:
4858:
4855:
4853:
4850:
4848:
4845:
4844:
4842:
4840:
4836:
4830:
4827:
4825:
4822:
4820:
4817:
4815:
4814:
4810:
4808:
4807:
4803:
4801:
4800:
4796:
4794:
4793:
4789:
4787:
4784:
4782:
4779:
4777:
4774:
4772:
4769:
4767:
4764:
4762:
4759:
4757:
4754:
4753:
4751:
4749:
4745:
4741:
4738:
4731:
4726:
4724:
4719:
4717:
4712:
4711:
4708:
4697:
4694:
4688:
4687:
4683:
4681:
4663:
4659:
4651:
4648:
4645:
4642:
4637:
4629:
4626:
4599:
4595:
4587:
4584:
4581:
4578:
4554:
4550:
4542:
4539:
4536:
4533:
4530:
4506:
4502:
4492:
4488:
4484:
4481:
4478:
4473:
4469:
4465:
4460:
4455:
4451:
4447:
4444:
4439:
4434:
4430:
4426:
4423:
4403:
4400:
4395:
4391:
4381:
4368:
4361:
4357:
4349:
4346:
4343:
4340:
4335:
4331:
4327:
4320:
4316:
4308:
4305:
4302:
4299:
4296:
4291:
4287:
4262:
4258:
4250:
4247:
4244:
4241:
4236:
4232:
4228:
4221:
4217:
4209:
4206:
4203:
4200:
4197:
4192:
4188:
4164:
4157:
4153:
4145:
4142:
4139:
4136:
4133:
4130:
4125:
4121:
4115:
4111:
4107:
4102:
4098:
4092:
4088:
4084:
4079:
4075:
4067:
4053:
4046:
4042:
4034:
4031:
4028:
4025:
4022:
4019:
4016:
4013:
4010:
4005:
4001:
3995:
3991:
3987:
3984:
3979:
3975:
3969:
3965:
3961:
3956:
3952:
3944:
3943:
3942:
3941:by computing
3926:
3922:
3899:
3895:
3874:
3871:
3866:
3862:
3858:
3855:
3852:
3847:
3843:
3820:
3815:
3811:
3807:
3804:
3799:
3794:
3790:
3767:
3763:
3740:
3736:
3715:
3712:
3709:
3706:
3701:
3697:
3672:
3668:
3660:
3657:
3652:
3648:
3635:
3633:
3615:
3611:
3603:
3600:
3597:
3594:
3589:
3581:
3578:
3551:
3547:
3539:
3536:
3533:
3530:
3527:
3524:
3521:
3517:
3511:
3503:
3500:
3494:
3491:
3488:
3484:
3480:
3477:
3474:
3471:
3447:
3443:
3435:
3432:
3429:
3424:
3420:
3416:
3411:
3408:
3405:
3402:
3398:
3377:
3374:
3371:
3351:
3348:
3345:
3342:
3339:
3336:
3333:
3310:
3303:
3299:
3291:
3288:
3283:
3279:
3271:
3270:
3269:
3263:
3261:
3243:
3239:
3231:
3228:
3225:
3222:
3217:
3209:
3206:
3179:
3175:
3167:
3164:
3161:
3156:
3152:
3148:
3145:
3142:
3122:
3119:
3116:
3096:
3093:
3090:
3087:
3084:
3081:
3078:
3055:
3048:
3044:
3036:
3033:
3028:
3024:
3016:
3015:
3014:
3008:
3006:
2992:
2989:
2984:
2980:
2976:
2971:
2967:
2946:
2943:
2938:
2934:
2930:
2925:
2921:
2914:
2911:
2908:
2901:
2897:
2894:
2871:
2864:
2860:
2852:
2849:
2844:
2840:
2832:
2831:
2827:
2825:
2823:
2807:
2799:
2791:
2789:
2773:
2769:
2765:
2762:
2759:
2754:
2750:
2729:
2726:
2723:
2720:
2715:
2711:
2688:
2683:
2679:
2675:
2672:
2667:
2662:
2658:
2654:
2649:
2645:
2641:
2638:
2618:
2615:
2612:
2609:
2601:
2585:
2582:
2560:
2556:
2552:
2547:
2542:
2538:
2534:
2531:
2524:. This gives
2523:
2507:
2504:
2499:
2495:
2472:
2467:
2463:
2440:
2436:
2432:
2427:
2422:
2418:
2414:
2411:
2406:
2401:
2397:
2388:
2372:
2369:
2364:
2360:
2337:
2333:
2324:
2306:
2302:
2279:
2275:
2269:
2265:
2261:
2258:
2255:
2235:
2232:
2229:
2226:
2204:
2200:
2191:
2173:
2169:
2146:
2142:
2119:
2115:
2109:
2105:
2101:
2098:
2093:
2090:
2087:
2083:
2079:
2076:
2056:
2053:
2050:
2047:
2044:
2041:
2032:
2018:
2015:
2010:
2007:
2004:
2000:
1995:
1992:
1989:
1984:
1981:
1978:
1974:
1948:
1945:
1942:
1938:
1932:
1928:
1924:
1919:
1915:
1909:
1906:
1903:
1899:
1895:
1890:
1886:
1871:
1867:
1861:
1858:
1855:
1851:
1847:
1844:
1839:
1835:
1829:
1826:
1823:
1819:
1815:
1810:
1806:
1798:
1797:
1796:
1780:
1776:
1772:
1767:
1763:
1756:
1753:
1750:
1743:
1737:
1732:
1728:
1724:
1719:
1715:
1710:
1705:
1701:
1697:
1692:
1687:
1683:
1679:
1674:
1670:
1661:
1645:
1642:
1639:
1636:
1628:
1612:
1609:
1606:
1603:
1595:
1573:
1569:
1565:
1560:
1555:
1551:
1547:
1544:
1539:
1534:
1530:
1515:
1511:
1505:
1501:
1497:
1492:
1488:
1482:
1478:
1474:
1469:
1466:
1463:
1459:
1454:
1449:
1445:
1439:
1435:
1431:
1428:
1423:
1419:
1413:
1409:
1405:
1400:
1397:
1394:
1390:
1382:
1381:
1380:
1357:
1352:
1345:
1335:
1328:
1324:
1320:
1315:
1311:
1304:
1299:
1289:
1282:
1278:
1274:
1269:
1265:
1255:
1250:
1246:
1241:
1236:
1230:
1220:
1213:
1209:
1205:
1200:
1196:
1189:
1184:
1174:
1167:
1163:
1159:
1154:
1150:
1140:
1135:
1131:
1123:
1122:
1121:
1105:
1100:
1096:
1092:
1089:
1084:
1079:
1075:
1071:
1068:
1046:
1042:
1019:
1015:
994:
991:
988:
985:
980:
976:
955:
952:
949:
946:
926:
923:
920:
917:
914:
911:
887:
883:
876:
873:
870:
864:
861:
858:
850:
834:
830:
826:
823:
820:
817:
797:
794:
791:
786:
782:
759:
756:
753:
745:
742:
736:
733:
730:
710:
707:
702:
699:
696:
693:
685:
682:
659:
656:
653:
648:
645:
642:
639:
635:
614:
611:
608:
603:
600:
597:
594:
590:
582:
565:
562:
559:
555:
551:
548:
545:
525:
522:
517:
514:
511:
508:
504:
496:
495:
494:
475:
472:
452:
449:
446:
443:
440:
437:
428:
412:
409:
406:
402:
398:
395:
392:
367:
364:
344:
341:
338:
335:
332:
329:
320:
318:
310:
293:
290:
287:
284:
276:
272:
268:
252:
249:
244:
240:
231:
228:
227:
226:
225:
202:
198:
185:
182:
180:
176:
173:
172:
171:
170:
166:
148:
144:
119:
108:The algorithm
107:
105:
103:
98:
96:
92:
88:
84:
65:
58:
54:
46:
43:
38:
34:
26:
25:
24:
22:
18:
5253:
5160:
4935:
4918:
4910:
4829:MillerâRabin
4811:
4804:
4797:
4792:LucasâLehmer
4790:
4696:
4382:
4179:
3639:
3325:
3267:
3070:
3012:
2886:
2797:
2795:
2599:
2521:
2386:
2322:
2294:. Not every
2189:
2033:
1965:
1659:
1626:
1593:
1591:
1378:
903:
848:
429:
321:
316:
314:
274:
270:
266:
229:
223:
222:
183:
174:
168:
167:
111:
99:
90:
86:
82:
80:
23:of the form
16:
15:
5085:Pollard rho
5042:Goldschmidt
4776:Pocklington
4766:BaillieâPSW
3887:. Now find
2959:, but then
2192:. If it is
112:(Note: all
5270:Categories
5197:Cornacchia
5192:Chakravala
4740:algorithms
4684:References
4616:. Indeed,
4279:such that
3782:such that
21:congruence
5171:Berlekamp
5128:Euclidean
5016:Euclidean
4996:ToomâCook
4991:Karatsuba
4649:≡
4627:±
4585:±
4582:≡
4540:±
4537:≡
4485:⋅
4479:−
4466:≡
4427:≡
4347:≡
4306:≡
4300:−
4248:≡
4207:≡
4201:−
4143:≡
4032:≡
4026:−
4017:−
3707:−
3658:≡
3636:Example 3
3601:≡
3595:≡
3579:±
3537:±
3534:≡
3528:±
3525:≡
3495:±
3492:≡
3478:±
3475:≡
3433:−
3430:≡
3417:≡
3343:⋅
3289:≡
3264:Example 2
3229:≡
3223:≡
3207:±
3165:±
3162:≡
3149:±
3146:≡
3088:⋅
3034:≡
3009:Example 1
2944:≡
2898:≡
2850:≡
2828:Example 0
2808:≡
2766:±
2763:≡
2727:≡
2655:≡
2642:≡
2583:−
2553:≡
2532:−
2505:≡
2433:≡
2412:−
2370:≡
2259:≡
2099:≡
2091:−
2080:≡
2045:−
2016:≡
2008:−
1990:≡
1982:−
1946:−
1907:−
1896:≡
1859:−
1827:−
1816:≡
1773:≡
1754:−
1725:≡
1698:≡
1680:≡
1545:−
1321:−
1305:−
1206:−
1090:−
992:≡
953:−
950:≡
865:±
862:≡
824:±
821:≡
792:≡
737:±
734:≡
708:≡
657:−
654:≡
612:−
609:≡
552:±
549:≡
523:≡
476:∈
399:±
396:≡
368:∈
291:−
288:≠
250:≡
177:, an odd
120:≡
104:in 1917.
44:≡
5138:Lehmer's
5032:Chunking
5019:division
4948:Fermat's
2792:Examples
1061:so that
851:is odd,
810:. Hence
277:is odd,
224:Outputs:
5254:Italics
5176:Kunerth
5156:Cipolla
5037:Fourier
5006:FĂŒrer's
4900:Euler's
4890:Dixon's
4813:PĂ©pin's
2822:modulus
2631:. Then
2069:. Then
847:or, if
465:, with
357:, with
169:Inputs:
5236:Schoof
5123:Binary
5027:Binary
4963:Shor's
4781:Fermat
4383:Since
2800:. All
2325:, for
2219:, put
939:, put
81:where
5057:Short
4786:Lucas
3364:, so
3109:, so
2385:with
179:prime
93:is a
5052:Long
4986:Long
3755:and
2034:Let
1034:and
493:and
85:and
5216:LLL
5062:SRT
4921:+ 1
4913:â 1
4761:APR
4756:AKS
4660:mod
4596:mod
4551:mod
4503:mod
4358:mod
4317:mod
4259:mod
4245:156
4218:mod
4204:299
4154:mod
4043:mod
3669:mod
3612:mod
3548:mod
3531:800
3444:mod
3300:mod
3240:mod
3176:mod
3045:mod
2861:mod
2161:or
1880:and
1658:),
1524:and
723:so
199:mod
145:mod
55:mod
5272::
5220:KZ
5218:;
4680:.
4664:17
4652:13
4646:64
4600:17
4555:17
4507:17
4482:13
4448:13
4362:17
4344:42
4321:17
4303:68
4263:17
4222:17
4158:17
4047:17
4035:13
4020:13
3988:13
3914:,
3808:13
3710:13
3673:17
3661:13
3632:.
3616:13
3604:10
3598:49
3552:13
3448:13
3421:10
3399:10
3334:13
3304:13
3292:10
3260:.
3244:23
3232:18
3226:64
3180:23
3153:18
3079:23
3049:23
3037:18
2939:12
2935:43
2909:47
2902:43
2865:47
2853:43
2788:.
2031:.
427:.
319::
97:.
5222:)
5214:(
4919:p
4911:p
4729:e
4722:t
4715:v
4667:)
4657:(
4643:=
4638:2
4634:)
4630:8
4624:(
4603:)
4593:(
4588:8
4579:x
4558:)
4548:(
4543:7
4534:x
4531:3
4510:)
4500:(
4493:2
4489:3
4474:2
4470:7
4461:2
4456:4
4452:u
4445:+
4440:2
4435:4
4431:t
4424:0
4404:0
4401:=
4396:8
4392:t
4369:.
4365:)
4355:(
4350:8
4341:=
4336:8
4332:u
4328:,
4324:)
4314:(
4309:0
4297:=
4292:8
4288:t
4266:)
4256:(
4251:3
4242:=
4237:4
4233:u
4229:,
4225:)
4215:(
4210:7
4198:=
4193:4
4189:t
4165:.
4161:)
4151:(
4146:6
4140:3
4137:+
4134:3
4131:=
4126:1
4122:u
4116:1
4112:t
4108:+
4103:1
4099:u
4093:1
4089:t
4085:=
4080:2
4076:u
4054:,
4050:)
4040:(
4029:4
4023:=
4014:9
4011:=
4006:1
4002:u
3996:1
3992:u
3985:+
3980:1
3976:t
3970:1
3966:t
3962:=
3957:2
3953:t
3927:8
3923:u
3900:8
3896:t
3875:1
3872:=
3867:1
3863:u
3859:,
3856:3
3853:=
3848:1
3844:t
3821:2
3816:1
3812:u
3805:+
3800:2
3795:1
3791:t
3768:1
3764:u
3741:1
3737:t
3716:0
3713:=
3702:2
3698:x
3676:)
3666:(
3653:2
3649:x
3619:)
3609:(
3590:2
3586:)
3582:7
3576:(
3555:)
3545:(
3540:7
3522:2
3518:/
3512:2
3508:)
3504:a
3501:4
3498:(
3489:2
3485:/
3481:y
3472:x
3451:)
3441:(
3436:1
3425:3
3412:1
3409:+
3406:m
3403:2
3378:1
3375:=
3372:m
3352:5
3349:+
3346:1
3340:8
3337:=
3311:.
3307:)
3297:(
3284:2
3280:x
3247:)
3237:(
3218:2
3214:)
3210:8
3204:(
3183:)
3173:(
3168:8
3157:6
3143:x
3123:5
3120:=
3117:m
3097:3
3094:+
3091:5
3085:4
3082:=
3056:.
3052:)
3042:(
3029:2
3025:x
2993:4
2990:=
2985:2
2981:2
2977:=
2972:2
2968:x
2947:2
2931:=
2926:2
2922:/
2918:)
2915:1
2912:+
2906:(
2895:x
2872:.
2868:)
2858:(
2845:2
2841:x
2798:p
2774:k
2770:t
2760:x
2755:k
2751:u
2730:0
2724:D
2721:+
2716:2
2712:x
2689:2
2684:k
2680:u
2676:D
2673:+
2668:2
2663:k
2659:t
2650:l
2646:t
2639:0
2619:k
2616:2
2613:=
2610:l
2600:l
2586:D
2561:l
2557:N
2548:2
2543:l
2539:u
2535:D
2522:l
2508:0
2500:l
2496:t
2473:2
2468:m
2464:t
2441:m
2437:N
2428:2
2423:m
2419:u
2415:D
2407:2
2402:m
2398:t
2387:m
2373:0
2365:m
2361:u
2338:1
2334:u
2323:p
2307:i
2303:u
2280:s
2276:u
2270:s
2266:t
2262:2
2256:0
2236:s
2233:2
2230:=
2227:r
2205:r
2201:u
2190:p
2174:r
2170:u
2147:r
2143:t
2120:r
2116:u
2110:r
2106:t
2102:2
2094:1
2088:p
2084:u
2077:0
2057:r
2054:2
2051:=
2048:1
2042:p
2019:0
2011:1
2005:p
2001:u
1996:,
1993:1
1985:1
1979:p
1975:t
1949:1
1943:p
1939:u
1933:1
1929:t
1925:+
1920:1
1916:u
1910:1
1904:p
1900:t
1891:1
1887:u
1872:1
1868:u
1862:1
1856:p
1852:u
1848:D
1845:+
1840:1
1836:t
1830:1
1824:p
1820:t
1811:1
1807:t
1781:1
1777:u
1768:2
1764:/
1760:)
1757:1
1751:p
1748:(
1744:D
1738:p
1733:1
1729:u
1720:p
1716:u
1711:,
1706:1
1702:t
1693:p
1688:1
1684:t
1675:p
1671:t
1660:D
1646:1
1643:+
1640:m
1637:8
1627:p
1613:1
1610:+
1607:m
1604:4
1594:p
1588:.
1574:n
1570:N
1566:=
1561:2
1556:n
1552:u
1548:D
1540:2
1535:n
1531:t
1516:m
1512:u
1506:n
1502:t
1498:+
1493:n
1489:u
1483:m
1479:t
1475:=
1470:n
1467:+
1464:m
1460:u
1455:,
1450:n
1446:u
1440:m
1436:u
1432:D
1429:+
1424:n
1420:t
1414:m
1410:t
1406:=
1401:n
1398:+
1395:m
1391:t
1375:.
1358:D
1353:2
1346:n
1342:)
1336:D
1329:1
1325:u
1316:1
1312:t
1308:(
1300:n
1296:)
1290:D
1283:1
1279:u
1275:+
1270:1
1266:t
1262:(
1256:=
1251:n
1247:u
1242:,
1237:2
1231:n
1227:)
1221:D
1214:1
1210:u
1201:1
1197:t
1193:(
1190:+
1185:n
1181:)
1175:D
1168:1
1164:u
1160:+
1155:1
1151:t
1147:(
1141:=
1136:n
1132:t
1106:2
1101:1
1097:u
1093:D
1085:2
1080:1
1076:t
1072:=
1069:N
1047:1
1043:u
1020:1
1016:t
995:0
989:D
986:+
981:2
977:x
956:a
947:D
927:1
924:+
921:m
918:8
915:=
912:p
900:.
888:2
884:/
880:)
877:y
874:+
871:p
868:(
859:x
849:y
835:2
831:/
827:y
818:x
798:a
795:4
787:2
783:y
760:1
757:+
754:m
750:)
746:a
743:4
740:(
731:y
711:1
703:1
700:+
697:m
694:2
690:)
686:a
683:4
680:(
660:1
649:1
646:+
643:m
640:2
636:4
615:1
604:1
601:+
598:m
595:2
591:a
580:.
566:1
563:+
560:m
556:a
546:x
526:1
518:1
515:+
512:m
509:2
505:a
480:N
473:m
453:5
450:+
447:m
444:8
441:=
438:p
413:1
410:+
407:m
403:a
393:x
372:N
365:m
345:3
342:+
339:m
336:4
333:=
330:p
317:p
294:x
285:x
275:p
271:x
267:x
253:a
245:2
241:x
230:x
219:.
206:)
203:p
196:(
184:a
175:p
152:)
149:p
142:(
91:a
87:a
83:x
66:,
62:)
59:p
52:(
47:a
39:2
35:x
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.