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