3449:
5461:
1607:
The sieving step of the algorithm consists of finding doubly-smooth pairs of functions. In the subsequent step we use them to find linear relations including the logarithms of the functions in the decompositions. By solving a linear system we then calculate the logarithms. In the reduction step we
4249:
3165:
3941:
1326:
3607:
5278:
3717:
248:
2118:
6473:
1166:
The
Function Field Sieve algorithm consists of a precomputation where the discrete logarithms of irreducible polynomials of small degree are found and a reduction step where they are combined to the logarithm of
5257:
2331:
2817:
2013:
3157:
4823:
4081:
4426:
690:
5786:. It is not surprising that there exist two similar algorithms, one with number fields and the other one with function fields. In fact there is an extensive analogy between these two kinds of
5797:
is much easier to state than the
Function Field Sieve and the Number Field Sieve since it does not involve any advanced algebraic structures. It is asymptotically slower with a complexity of
4598:
3008:
3444:{\displaystyle {\text{div}}((ry+s)^{h})=\sum ha_{i}v_{i}=\sum ha_{i}v_{i}-\sum ha_{i}f_{v_{i}}v+hv\sum a_{i}f_{v_{i}}=\sum a_{i}h(v_{i}-f_{v_{i}}v))={\text{div}}(\prod \alpha _{i}^{a_{i}})}
1846:
1156:
5083:
2674:
1046:
961:
125:
6477:
5031:
460:
5784:
4073:
1742:
1553:
5631:
5592:
2154:
1902:
5985:
4038:
2549:
and divisors as defined above. The goal is to use the doubly-smooth pairs of functions to find linear relations involving the discrete logarithms of elements in the factor base.
43:
developed it in 1994 and then elaborated it together with M. D. Huang in 1999. Previous work includes the work of D. Coppersmith about the DLP in fields of characteristic two.
4980:
4708:
2200:
649:
3066:
276:
3773:
2939:
2707:
2535:
1509:
1460:
926:
565:
383:
4358:
2602:
2396:
3834:
5528:
4934:
4504:
4465:
3983:
1645:
887:
5948:
D. Gordon. "Discrete
Logarithm in GF(P) Using the Number Field Sieve". In: Siam Journal on Discrete Mathematics - SIAMDM 6 (Feb. 1993), pp. 124-138. DOI: 10.1137/0406010.
4672:
5921:
L. Adleman, M.D. Huang. "Function Field Sieve Method for
Discrete Logarithms over Finite Fields". In: Inf. Comput. 151 (May 1999), pp. 5-16. DOI: 10.1006/inco.1998.2761.
6018:
501:
3505:
2910:
1425:
800:
77:
4907:
4861:
4734:
4530:
3826:
2442:
1777:
987:
862:
536:
350:
5849:
5725:
5110:
4645:
4279:
3800:
2734:
1358:
1073:
1582:
1387:
1237:
5869:
5154:
5134:
4881:
4618:
4299:
3472:
2877:
2857:
2837:
2622:
2482:
2462:
2416:
2243:
2223:
2018:
1942:
1922:
1866:
1797:
1698:
1678:
1602:
1480:
1228:
1208:
1185:
1093:
730:
710:
589:
165:
145:
5957:
R. Barbulescu, P. Gaudry, T. Kleinjung. "The Tower Number Field Sieve". In: Advances in
Cryptology â Asiacrypt 2015. Vol. 9453. Springer, May 2015. pp. 31-58
5456:{\displaystyle \exp \left(\left({\sqrt{\frac {32}{9}}}+o(1)\right)(\ln p)^{\frac {1}{3}}(\ln \ln p)^{\frac {2}{3}}\right)=L_{p}\left{\frac {32}{9}}}\right]}
3513:
5930:
D. Coppersmith. (1984), "Fast evaluation of discrete logarithms in fields of characteristic two". In: IEEE Trans. Inform. Theory IT-39 (1984), pp. 587-594.
3615:
6342:
5978:
5851:. The main reason why the Number Field Sieve and the Function Field Sieve are faster is that these algorithms can run with a smaller smoothness bound
170:
5727:
and is therefore slightly slower than the best performance of the
Function Field Sieve. However, it is faster than the Function Field Sieve when
6210:
5909:
L. Adleman. "The function field sieve". In: Algorithmic Number Theory (ANTS-I). Lecture Notes in
Computer Science. Springer (1994), pp.108-121.
6152:
5971:
6081:
6258:
5162:
2256:
6056:
2739:
1950:
6167:
6205:
6142:
6086:
6049:
3071:
6347:
6238:
6157:
6147:
6023:
4244:{\displaystyle \sum _{g\in S}e_{g}\log _{*}g\equiv \sum a_{i}h_{1}\log _{*}(\phi (\alpha _{i})){\text{ mod }}(p^{n}-1)/(p-1),}
6175:
6428:
4739:
6423:
6352:
6253:
6533:
6390:
4366:
654:
6304:
3946:
Here we can take the discrete logarithm of the equation up to a unit. This is called the restricted discrete logarithm
4535:
295:
287:
2947:
6469:
6459:
6418:
6194:
6188:
6162:
6033:
5885:
5539:
1802:
1234:
and such functions are useful because their decomposition can be found relatively fast. The set of those functions
6454:
6395:
5036:
2627:
1098:
931:
82:
992:
6357:
6230:
6076:
6028:
5890:
5880:
5794:
5547:
4985:
2546:
2496:
599:
392:
312:
5730:
2537:
but those functions can be factored into irreducible polynomials just as numbers can be factored into primes.
6372:
6263:
4043:
1703:
1514:
6483:
6433:
6413:
5600:
5561:
2123:
1871:
3988:
6134:
6109:
6038:
4939:
4677:
2159:
617:
6493:
3936:{\displaystyle \prod _{g\in S}g^{he_{g}}\equiv \phi (c)\prod \phi (\alpha _{i})^{a_{i}}{\text{ mod }}f}
3013:
253:
5939:
M. Fried and M. Jarden. In: "Field
Arithmetic". vol. 11. (Jan. 2005). Chap. 2.1. DOI: 10.1007/b138352.
3725:
2915:
2679:
2502:
1485:
1430:
541:
359:
6488:
6380:
6337:
6299:
6043:
5543:
4304:
3507:. Then, using the fact that the divisor of a surrogate function is unique up to a constant, one gets
2555:
2339:
892:
568:
6498:
6464:
6385:
6289:
6248:
6243:
6220:
6124:
5477:
5269:
603:
36:
4912:
4470:
4431:
3949:
1611:
870:
6329:
6276:
6273:
6114:
6013:
5551:
5113:
4650:
4467:
are unknown. Once enough equations of this form are found, a linear system can be solved to find
2492:
386:
25:
6070:
6063:
4736:
the unit corresponding to the restricted discrete logarithm can be calculated which then gives
6449:
6405:
6119:
6096:
465:
3477:
2882:
1392:
735:
538:. This is a special case of an algebraic function field. It is defined over the finite field
49:
6294:
4886:
4836:
4713:
4509:
3805:
2421:
1747:
966:
805:
506:
320:
279:
5800:
5636:
5088:
4623:
4257:
3778:
2712:
1331:
1321:{\displaystyle S=\{g(x)\in \mathbb {F} _{p}\mid {\text{ irreductible with }}\deg(g)<B\}}
1051:
6284:
6183:
1558:
1363:
353:
40:
2491:
This is completely analogous to the sieving step in other sieving algorithms such as the
6314:
6215:
6200:
6104:
6005:
5854:
5139:
5119:
4866:
4603:
4284:
3457:
2862:
2842:
2822:
2607:
2467:
2447:
2401:
2228:
2208:
1927:
1907:
1851:
1782:
1683:
1663:
1587:
1465:
1213:
1193:
1170:
1078:
715:
695:
595:
574:
150:
130:
3602:{\displaystyle (ry+s)^{h}=c\prod \alpha _{i}^{a_{i}}{\text{ for some }}c\in F_{p}^{*}}
6527:
6309:
5994:
1231:
1190:
Functions that decompose into irreducible function of degree smaller than some bound
6319:
5787:
5555:
3712:{\displaystyle \implies \phi ((ry+s)^{h})=\phi (c)\prod \phi (\alpha _{i})^{a_{i}}}
963:
and only finitely many elements of the sum are non-zero. The divisor of an element
283:
46:
The discrete logarithm problem in a finite field consists of solving the equation
29:
3775:
and the known decomposition of this expression into irreducible polynomials. Let
5474:
assumptions. For example in the sieving step we assume that numbers of the form
606:. This correspondence is frequently used in the Function Field Sieve algorithm.
17:
5963:
5467:
5112:
can be reduced to polynomials of smaller degree using a generalization of the
2545:
This is the most difficult part of the algorithm, involving function fields,
243:{\displaystyle f:\mathbb {F} _{p^{n}}\to \mathbb {F} _{p^{n}},a\mapsto a^{x}}
5997:
5471:
2485:
33:
2113:{\displaystyle \phi :\mathbb {F} _{p}/C\to \mathbb {F} _{p}/f,y\mapsto m.}
1647:
as a combination of the logarithm we found before and thus solve the DLP.
2488:
can be used to efficiently step through multiples of a given polynomial.
1660:
The algorithm requires the following parameters: an irreducible function
291:
5470:. There is no rigorous proof of this complexity since it relies on some
5252:{\displaystyle \log _{a}(b)=\sum _{g_{i}\in S}\log _{a}(g_{i})-l}
286:. Several cryptographic methods are based on the DLP such as the
5871:, so most of the computations can be done with smaller numbers.
2552:
For each irreducible function in the factor base we find places
2326:{\displaystyle (r,s)\in \mathbb {F} _{p}\times \mathbb {F} _{p}}
602:, as well as between valuation rings and equivalence classes of
5967:
2912:. The function defined this way is unique up to a constant in
2812:{\displaystyle {\text{div}}(\alpha _{i})=h(v_{i}-f_{v_{i}}u)}
2008:{\displaystyle \mathbb {F} _{p^{n}}\simeq \mathbb {F} _{p}/f}
5558:
of prime order but they can be expanded to solve the DLP in
5136:-smooth polynomials. Then, taking the logarithm to the base
3152:{\textstyle \sum a_{i}f_{v_{i}}=\deg({\text{div}}(ry+s))=0}
5538:
There are two other well known algorithms that solve the
6514:
indicate that algorithm is for numbers of special forms
4818:{\displaystyle \log _{a}(g)=\log _{*}(g)-\log _{a}(u)}
3074:
2950:
1101:
995:
895:
5857:
5803:
5733:
5639:
5603:
5564:
5480:
5281:
5165:
5142:
5122:
5116:. We can reduce the degree until we get a product of
5091:
5039:
4988:
4942:
4915:
4889:
4869:
4839:
4742:
4716:
4680:
4653:
4626:
4606:
4538:
4512:
4473:
4434:
4369:
4307:
4287:
4260:
4084:
4046:
3991:
3952:
3837:
3808:
3781:
3728:
3618:
3516:
3480:
3460:
3168:
3016:
2918:
2885:
2865:
2845:
2825:
2742:
2715:
2682:
2630:
2610:
2558:
2505:
2499:. Instead of numbers one sieves through functions in
2470:
2450:
2424:
2404:
2342:
2259:
2231:
2211:
2162:
2126:
2021:
1953:
1930:
1910:
1874:
1854:
1805:
1785:
1750:
1706:
1686:
1666:
1614:
1590:
1561:
1517:
1488:
1468:
1433:
1395:
1366:
1334:
1240:
1216:
1196:
1173:
1081:
1054:
969:
934:
873:
808:
738:
718:
698:
657:
620:
577:
544:
509:
468:
395:
362:
323:
256:
173:
153:
133:
85:
52:
24:
is one of the most efficient algorithms to solve the
2676:
that correspond to the places. A surrogate function
712:
called a prime of the function field. The degree of
6442:
6404:
6371:
6328:
6272:
6229:
6133:
6095:
6004:
5863:
5843:
5778:
5719:
5625:
5586:
5522:
5455:
5251:
5148:
5128:
5104:
5077:
5025:
4974:
4928:
4901:
4875:
4855:
4817:
4728:
4702:
4666:
4639:
4612:
4592:
4524:
4498:
4459:
4421:{\displaystyle h_{1}\log _{*}(\phi (\alpha _{i}))}
4420:
4352:
4293:
4273:
4243:
4067:
4032:
3977:
3935:
3820:
3794:
3767:
3711:
3601:
3499:
3466:
3443:
3151:
3060:
3002:
2933:
2904:
2871:
2851:
2831:
2811:
2728:
2701:
2668:
2616:
2596:
2529:
2476:
2456:
2436:
2410:
2390:
2325:
2237:
2217:
2194:
2148:
2112:
2007:
1936:
1916:
1896:
1860:
1840:
1791:
1771:
1736:
1692:
1672:
1639:
1596:
1584:is viewed as an element of the function field of
1576:
1547:
1503:
1474:
1454:
1419:
1381:
1352:
1320:
1230:-smooth. This is analogous to the definition of a
1222:
1202:
1179:
1150:
1087:
1067:
1040:
981:
955:
920:
881:
856:
794:
724:
704:
685:{\displaystyle \mathbb {F} _{p}\subset O\subset K}
684:
643:
583:
559:
530:
495:
454:
377:
344:
270:
242:
159:
139:
119:
71:
5554:. In their easiest forms both solve the DLP in a
571:one. The transcendent element will be denoted by
4593:{\displaystyle h_{1}log_{*}(\phi (\alpha _{i}))}
4710:don't have to be computed. Eventually for each
3003:{\textstyle {\text{div}}(ry+s)=\sum a_{i}v_{i}}
1328:is called the factor base. A pair of functions
5268:The Function Field Sieve is thought to run in
2253:In this step doubly-smooth pairs of functions
598:in function fields and equivalence classes of
5979:
5530:behave like random numbers in a given range.
4909:. With sufficiently high probability this is
1841:{\displaystyle C(x,m)\equiv 0{\text{ mod }}f}
8:
1868:is the power in the order of the base field
1315:
1247:
1151:{\textstyle \deg(d)=\sum \alpha _{P}\deg(P)}
1075:is the valuation corresponding to the prime
5078:{\displaystyle \deg(b_{i})<{\sqrt {nB}}}
2669:{\displaystyle \alpha _{1},\alpha _{2},...}
2624:that lie over them and surrogate functions
1041:{\textstyle {\text{div}}(x)=\sum v_{P}(x)P}
956:{\displaystyle \alpha _{P}\in \mathbb {Z} }
614:A discrete valuation of the function field
120:{\displaystyle a,b\in \mathbb {F} _{p^{n}}}
5986:
5972:
5964:
3623:
3619:
2464:that is reduced to one in this process is
5917:
5915:
5856:
5831:
5820:
5808:
5802:
5766:
5762:
5732:
5689:
5685:
5673:
5656:
5644:
5638:
5615:
5610:
5606:
5605:
5602:
5576:
5571:
5567:
5566:
5563:
5479:
5441:
5431:
5418:
5407:
5384:
5351:
5308:
5298:
5280:
5234:
5218:
5200:
5195:
5170:
5164:
5141:
5121:
5096:
5090:
5065:
5053:
5038:
5026:{\displaystyle b_{i}\in \mathbb {F} _{p}}
5008:
5004:
5003:
4993:
4987:
4966:
4947:
4941:
4916:
4914:
4888:
4868:
4844:
4838:
4797:
4772:
4747:
4741:
4715:
4691:
4679:
4658:
4652:
4631:
4625:
4605:
4578:
4559:
4543:
4537:
4511:
4478:
4472:
4439:
4433:
4406:
4384:
4374:
4368:
4330:
4315:
4306:
4286:
4265:
4259:
4218:
4203:
4191:
4179:
4157:
4147:
4137:
4115:
4105:
4089:
4083:
4059:
4055:
4054:
4045:
4001:
3996:
3990:
3957:
3951:
3925:
3917:
3912:
3902:
3866:
3858:
3842:
3836:
3807:
3786:
3780:
3727:
3701:
3696:
3686:
3649:
3617:
3593:
3588:
3573:
3565:
3560:
3555:
3536:
3515:
3485:
3479:
3459:
3430:
3425:
3420:
3405:
3385:
3380:
3367:
3351:
3333:
3328:
3318:
3291:
3286:
3276:
3257:
3247:
3228:
3218:
3196:
3169:
3167:
3117:
3097:
3092:
3082:
3073:
3034:
3021:
3015:
2994:
2984:
2951:
2949:
2925:
2921:
2920:
2917:
2890:
2884:
2864:
2844:
2824:
2795:
2790:
2777:
2755:
2743:
2741:
2720:
2714:
2687:
2681:
2648:
2635:
2629:
2609:
2576:
2563:
2557:
2512:
2508:
2507:
2504:
2469:
2449:
2423:
2403:
2341:
2308:
2304:
2303:
2284:
2280:
2279:
2258:
2230:
2210:
2205:One also needs to set a smoothness bound
2184:
2169:
2165:
2164:
2161:
2138:
2133:
2129:
2128:
2125:
2087:
2072:
2068:
2067:
2055:
2034:
2030:
2029:
2020:
1997:
1982:
1978:
1977:
1965:
1960:
1956:
1955:
1952:
1929:
1909:
1886:
1881:
1877:
1876:
1873:
1853:
1830:
1804:
1784:
1749:
1719:
1715:
1714:
1705:
1685:
1665:
1619:
1613:
1589:
1560:
1530:
1526:
1525:
1516:
1495:
1491:
1490:
1487:
1467:
1432:
1394:
1365:
1333:
1289:
1271:
1267:
1266:
1239:
1215:
1195:
1172:
1127:
1100:
1080:
1059:
1053:
1020:
996:
994:
968:
949:
948:
939:
933:
909:
894:
875:
874:
872:
845:
841:
840:
828:
813:
807:
783:
779:
778:
766:
737:
717:
697:
664:
660:
659:
656:
635:
631:
630:
624:
619:
576:
551:
547:
546:
543:
508:
467:
455:{\displaystyle \mathbb {F} _{p}/(C(x,y))}
423:
402:
398:
397:
394:
369:
365:
364:
361:
322:
264:
263:
255:
234:
213:
208:
204:
203:
191:
186:
182:
181:
172:
152:
132:
109:
104:
100:
99:
84:
57:
51:
5779:{\displaystyle n<<(\log(p))^{1/2}}
4600:as an unknown helps to gain time, since
889:-linear combination over all primes, so
385:. A function field may be viewed as the
5902:
5597:The Number Field Sieve for the DLP in
2120:Using the isomorphism each element of
4068:{\displaystyle u\in \mathbb {F} _{p}}
2879:is any fixed discrete valuation with
2156:can be considered as a polynomial in
1924:denote the function field defined by
1737:{\displaystyle m\in \mathbb {F} _{p}}
1548:{\displaystyle m\in \mathbb {F} _{p}}
7:
5626:{\displaystyle \mathbb {F} _{p^{n}}}
5587:{\displaystyle \mathbb {F} _{p^{n}}}
2336:One considers functions of the form
2149:{\displaystyle \mathbb {F} _{p^{n}}}
1897:{\displaystyle \mathbb {F} _{p^{n}}}
4033:{\displaystyle a^{\log _{*}(x)}=ux}
651:, namely a discrete valuation ring
4975:{\displaystyle a^{l}b=\prod b_{i}}
4703:{\displaystyle \phi (\alpha _{i})}
3159:we get the following expression:
2195:{\displaystyle \mathbb {F} _{p}/f}
644:{\displaystyle K/\mathbb {F} _{p}}
14:
6195:Special number field sieve (SNFS)
6189:General number field sieve (GNFS)
4936:-smooth, so one can factor it as
3061:{\displaystyle a_{i}=v_{i}(ry+s)}
271:{\displaystyle x\in \mathbb {N} }
3985:. It is defined by the equation
3768:{\displaystyle \phi (ry+s)=rm+s}
2934:{\displaystyle \mathbb {F} _{p}}
2702:{\displaystyle \alpha _{i}\in K}
2530:{\displaystyle \mathbb {F} _{p}}
1504:{\displaystyle \mathbb {F} _{p}}
1455:{\displaystyle N(\cdot ,\cdot )}
921:{\textstyle d=\sum \alpha _{P}P}
560:{\displaystyle \mathbb {F} _{p}}
378:{\displaystyle \mathbb {F} _{p}}
4353:{\displaystyle (p^{n}-1)/(p-1)}
3068:. Using this and the fact that
2944:By the definition of a divisor
2597:{\displaystyle v_{1},v_{2},...}
2444:as many times as possible. Any
2391:{\displaystyle f=(rm+s)N(ry+s)}
594:There exist bijections between
503:denotes the ideal generated by
5838:
5814:
5759:
5755:
5749:
5740:
5714:
5711:
5705:
5682:
5667:
5650:
5517:
5502:
5496:
5481:
5381:
5362:
5348:
5335:
5327:
5321:
5240:
5227:
5185:
5179:
5059:
5046:
5020:
5014:
4812:
4806:
4787:
4781:
4762:
4756:
4697:
4684:
4587:
4584:
4571:
4565:
4532:. Taking the whole expression
4493:
4487:
4454:
4448:
4415:
4412:
4399:
4393:
4347:
4335:
4327:
4308:
4235:
4223:
4215:
4196:
4188:
4185:
4172:
4166:
4016:
4010:
3972:
3966:
3909:
3895:
3886:
3880:
3747:
3732:
3693:
3679:
3670:
3664:
3655:
3646:
3630:
3627:
3620:
3533:
3517:
3438:
3410:
3399:
3396:
3360:
3202:
3193:
3177:
3174:
3140:
3137:
3122:
3114:
3055:
3040:
2971:
2956:
2806:
2770:
2761:
2748:
2524:
2518:
2385:
2370:
2364:
2349:
2320:
2314:
2296:
2290:
2272:
2260:
2181:
2175:
2101:
2084:
2078:
2063:
2052:
2040:
1994:
1988:
1821:
1809:
1766:
1754:
1731:
1725:
1634:
1628:
1542:
1536:
1449:
1437:
1414:
1399:
1347:
1335:
1306:
1300:
1283:
1277:
1259:
1253:
1145:
1139:
1114:
1108:
1095:. The degree of a divisor is
1032:
1026:
1007:
1001:
851:
822:
789:
760:
754:
748:
525:
513:
490:
487:
475:
469:
449:
446:
434:
428:
420:
408:
389:of the affine coordinate ring
339:
327:
227:
199:
1:
5534:Comparison with other methods
5523:{\displaystyle (rm+s)N(ry+s)}
2484:-smooth. To implement this,
1947:This leads to an isomorphism
1462:is the norm of an element of
1291: irreductible with
692:, has a unique maximal ideal
302:Number theoretical background
6153:Lenstra elliptic curve (ECM)
5156:, we can eventually compute
5085:. Each of these polynomials
4929:{\displaystyle {\sqrt {nB}}}
4499:{\displaystyle \log _{*}(g)}
4460:{\displaystyle \log _{*}(g)}
3978:{\displaystyle \log _{*}(x)}
3828:in this decomposition. Then
1640:{\displaystyle \log _{a}(b)}
882:{\displaystyle \mathbb {Z} }
352:be a polynomial defining an
4667:{\displaystyle \alpha _{i}}
296:Digital Signature Algorithm
288:Diffie-Hellman key exchange
6550:
6460:Exponentiation by squaring
6143:Continued fraction (CFRAC)
5540:discrete logarithm problem
4883:are computed for a random
310:
6507:
3722:We now use the fact that
2709:corresponding to a place
167:an integer. The function
5891:Index calculus algorithm
5881:Algebraic function field
5795:index calculus algorithm
5548:index calculus algorithm
2541:Finding linear relations
2497:index calculus algorithm
496:{\displaystyle (C(x,y))}
313:Algebraic function field
6373:Greatest common divisor
5259:, which solves the DLP.
3500:{\displaystyle f_{v}=1}
2905:{\displaystyle f_{u}=1}
2839:is the class number of
1427:are both smooth, where
1420:{\displaystyle N(ry+s)}
795:{\displaystyle deg(P)=}
72:{\displaystyle a^{x}=b}
6484:Modular exponentiation
5865:
5845:
5780:
5721:
5627:
5588:
5524:
5457:
5253:
5150:
5130:
5106:
5079:
5027:
4976:
4930:
4903:
4902:{\displaystyle l<n}
4877:
4857:
4856:{\displaystyle a^{l}b}
4819:
4730:
4729:{\displaystyle g\in S}
4704:
4668:
4641:
4614:
4594:
4526:
4525:{\displaystyle g\in S}
4500:
4461:
4422:
4354:
4295:
4275:
4245:
4069:
4034:
3979:
3937:
3822:
3821:{\displaystyle g\in S}
3796:
3769:
3713:
3603:
3501:
3474:is any valuation with
3468:
3445:
3153:
3062:
3004:
2935:
2906:
2873:
2853:
2833:
2813:
2730:
2703:
2670:
2618:
2598:
2531:
2478:
2458:
2438:
2437:{\displaystyle g\in S}
2412:
2392:
2327:
2239:
2219:
2196:
2150:
2114:
2009:
1938:
1918:
1898:
1862:
1842:
1793:
1773:
1772:{\displaystyle C(x,y)}
1738:
1694:
1674:
1641:
1598:
1578:
1555:is some parameter and
1549:
1505:
1476:
1456:
1421:
1383:
1354:
1322:
1224:
1204:
1181:
1152:
1089:
1069:
1042:
983:
982:{\displaystyle x\in K}
957:
922:
883:
858:
857:{\displaystyle f_{O}=}
796:
726:
706:
686:
645:
585:
561:
532:
531:{\displaystyle C(x,y)}
497:
456:
379:
346:
345:{\displaystyle C(x,y)}
272:
244:
161:
141:
121:
73:
6211:Shanks's square forms
6135:Integer factorization
6110:Sieve of Eratosthenes
5866:
5846:
5844:{\displaystyle L_{p}}
5781:
5722:
5720:{\displaystyle L_{p}}
5628:
5589:
5550:and a version of the
5525:
5458:
5254:
5151:
5131:
5107:
5105:{\displaystyle b_{i}}
5080:
5028:
4977:
4931:
4904:
4878:
4858:
4820:
4731:
4705:
4669:
4642:
4640:{\displaystyle h_{1}}
4615:
4595:
4527:
4501:
4462:
4423:
4355:
4296:
4276:
4274:{\displaystyle h_{1}}
4246:
4070:
4035:
3980:
3938:
3823:
3797:
3795:{\displaystyle e_{g}}
3770:
3714:
3604:
3502:
3469:
3446:
3154:
3063:
3005:
2936:
2907:
2874:
2854:
2834:
2814:
2731:
2729:{\displaystyle v_{i}}
2704:
2671:
2619:
2599:
2532:
2479:
2459:
2439:
2413:
2393:
2328:
2240:
2220:
2197:
2151:
2115:
2010:
1939:
1919:
1899:
1863:
1843:
1794:
1774:
1739:
1695:
1675:
1642:
1599:
1579:
1550:
1506:
1477:
1457:
1422:
1384:
1355:
1353:{\displaystyle (r,s)}
1323:
1225:
1205:
1182:
1153:
1090:
1070:
1068:{\displaystyle v_{P}}
1043:
984:
958:
923:
884:
859:
797:
727:
707:
687:
646:
586:
562:
533:
498:
457:
380:
347:
294:cryptosystem and the
273:
245:
162:
142:
122:
74:
6489:Montgomery reduction
6363:Function field sieve
6338:Baby-step giant-step
6184:Quadratic sieve (QS)
5855:
5801:
5731:
5637:
5633:has a complexity of
5601:
5562:
5544:sub-exponential time
5478:
5279:
5163:
5140:
5120:
5089:
5037:
4986:
4940:
4913:
4887:
4867:
4837:
4740:
4714:
4678:
4651:
4624:
4604:
4536:
4510:
4471:
4432:
4367:
4305:
4285:
4258:
4082:
4044:
3989:
3950:
3835:
3806:
3779:
3726:
3616:
3575: for some
3514:
3478:
3458:
3166:
3072:
3014:
2948:
2916:
2883:
2863:
2843:
2823:
2740:
2713:
2680:
2628:
2608:
2556:
2503:
2468:
2448:
2422:
2402:
2340:
2257:
2229:
2225:for the factor base
2209:
2160:
2124:
2019:
1951:
1928:
1908:
1872:
1852:
1803:
1783:
1748:
1704:
1684:
1664:
1612:
1588:
1577:{\displaystyle ry+s}
1559:
1515:
1486:
1466:
1431:
1393:
1382:{\displaystyle rm+s}
1364:
1360:is doubly-smooth if
1332:
1238:
1214:
1194:
1171:
1099:
1079:
1052:
993:
967:
932:
893:
871:
806:
736:
716:
696:
655:
618:
575:
569:transcendence degree
542:
507:
466:
393:
360:
356:over a finite field
321:
254:
171:
151:
131:
83:
50:
22:Function Field Sieve
6534:Field (mathematics)
6499:Trachtenberg system
6465:Integer square root
6406:Modular square root
6125:Wheel factorization
6077:Quadratic Frobenius
6057:LucasâLehmerâRiesel
5270:subexponential time
4428:and the logarithms
3598:
3572:
3437:
2015:and a homomorphism
1656:Parameter selection
802:and we also define
147:a prime number and
28:Problem (DLP) in a
6391:Extended Euclidean
6330:Discrete logarithm
6259:SchönhageâStrassen
6115:Sieve of Pritchard
5886:Number field sieve
5861:
5841:
5776:
5717:
5623:
5584:
5552:Number Field Sieve
5520:
5453:
5249:
5213:
5146:
5126:
5114:Coppersmith method
5102:
5075:
5023:
4972:
4926:
4899:
4873:
4853:
4815:
4726:
4700:
4664:
4637:
4610:
4590:
4522:
4496:
4457:
4418:
4350:
4291:
4281:is the inverse of
4271:
4241:
4100:
4065:
4030:
3975:
3933:
3853:
3818:
3792:
3765:
3709:
3599:
3584:
3551:
3497:
3464:
3441:
3416:
3149:
3058:
3000:
2931:
2902:
2869:
2849:
2829:
2809:
2726:
2699:
2666:
2614:
2594:
2527:
2493:Number Field Sieve
2474:
2454:
2434:
2408:
2388:
2323:
2235:
2215:
2192:
2146:
2110:
2005:
1934:
1914:
1894:
1858:
1838:
1789:
1769:
1734:
1690:
1670:
1637:
1594:
1574:
1545:
1501:
1472:
1452:
1417:
1379:
1350:
1318:
1220:
1200:
1177:
1148:
1085:
1065:
1038:
979:
953:
918:
879:
854:
792:
722:
702:
682:
641:
581:
557:
528:
493:
452:
387:field of fractions
375:
342:
268:
240:
157:
137:
117:
69:
26:Discrete Logarithm
6521:
6520:
6120:Sieve of Sundaram
5864:{\displaystyle B}
5836:
5446:
5440:
5426:
5392:
5359:
5313:
5307:
5191:
5149:{\displaystyle a}
5129:{\displaystyle B}
5073:
4924:
4876:{\displaystyle f}
4613:{\displaystyle h}
4294:{\displaystyle h}
4194:
4085:
3928:
3838:
3576:
3467:{\displaystyle v}
3408:
3172:
3120:
2954:
2872:{\displaystyle u}
2852:{\displaystyle K}
2832:{\displaystyle h}
2746:
2617:{\displaystyle K}
2477:{\displaystyle B}
2457:{\displaystyle f}
2411:{\displaystyle f}
2238:{\displaystyle S}
2218:{\displaystyle B}
1937:{\displaystyle C}
1917:{\displaystyle K}
1861:{\displaystyle n}
1833:
1792:{\displaystyle d}
1693:{\displaystyle n}
1673:{\displaystyle f}
1597:{\displaystyle C}
1475:{\displaystyle K}
1292:
1223:{\displaystyle B}
1203:{\displaystyle B}
1180:{\displaystyle b}
1088:{\displaystyle P}
999:
725:{\displaystyle P}
705:{\displaystyle P}
584:{\displaystyle x}
160:{\displaystyle n}
140:{\displaystyle p}
6541:
6470:Integer relation
6443:Other algorithms
6348:Pollard kangaroo
6239:Ancient Egyptian
6097:Prime-generating
6082:SolovayâStrassen
5995:Number-theoretic
5988:
5981:
5974:
5965:
5958:
5955:
5949:
5946:
5940:
5937:
5931:
5928:
5922:
5919:
5910:
5907:
5870:
5868:
5867:
5862:
5850:
5848:
5847:
5842:
5837:
5832:
5824:
5813:
5812:
5785:
5783:
5782:
5777:
5775:
5774:
5770:
5726:
5724:
5723:
5718:
5698:
5697:
5693:
5677:
5660:
5649:
5648:
5632:
5630:
5629:
5624:
5622:
5621:
5620:
5619:
5609:
5593:
5591:
5590:
5585:
5583:
5582:
5581:
5580:
5570:
5529:
5527:
5526:
5521:
5462:
5460:
5459:
5454:
5452:
5448:
5447:
5445:
5433:
5432:
5427:
5419:
5412:
5411:
5399:
5395:
5394:
5393:
5385:
5361:
5360:
5352:
5334:
5330:
5314:
5312:
5300:
5299:
5258:
5256:
5255:
5250:
5239:
5238:
5223:
5222:
5212:
5205:
5204:
5175:
5174:
5155:
5153:
5152:
5147:
5135:
5133:
5132:
5127:
5111:
5109:
5108:
5103:
5101:
5100:
5084:
5082:
5081:
5076:
5074:
5066:
5058:
5057:
5032:
5030:
5029:
5024:
5013:
5012:
5007:
4998:
4997:
4981:
4979:
4978:
4973:
4971:
4970:
4952:
4951:
4935:
4933:
4932:
4927:
4925:
4917:
4908:
4906:
4905:
4900:
4882:
4880:
4879:
4874:
4862:
4860:
4859:
4854:
4849:
4848:
4824:
4822:
4821:
4816:
4802:
4801:
4777:
4776:
4752:
4751:
4735:
4733:
4732:
4727:
4709:
4707:
4706:
4701:
4696:
4695:
4673:
4671:
4670:
4665:
4663:
4662:
4646:
4644:
4643:
4638:
4636:
4635:
4619:
4617:
4616:
4611:
4599:
4597:
4596:
4591:
4583:
4582:
4564:
4563:
4548:
4547:
4531:
4529:
4528:
4523:
4505:
4503:
4502:
4497:
4483:
4482:
4466:
4464:
4463:
4458:
4444:
4443:
4427:
4425:
4424:
4419:
4411:
4410:
4389:
4388:
4379:
4378:
4363:The expressions
4359:
4357:
4356:
4351:
4334:
4320:
4319:
4300:
4298:
4297:
4292:
4280:
4278:
4277:
4272:
4270:
4269:
4250:
4248:
4247:
4242:
4222:
4208:
4207:
4195:
4192:
4184:
4183:
4162:
4161:
4152:
4151:
4142:
4141:
4120:
4119:
4110:
4109:
4099:
4074:
4072:
4071:
4066:
4064:
4063:
4058:
4039:
4037:
4036:
4031:
4020:
4019:
4006:
4005:
3984:
3982:
3981:
3976:
3962:
3961:
3942:
3940:
3939:
3934:
3929:
3926:
3924:
3923:
3922:
3921:
3907:
3906:
3873:
3872:
3871:
3870:
3852:
3827:
3825:
3824:
3819:
3802:be the power of
3801:
3799:
3798:
3793:
3791:
3790:
3774:
3772:
3771:
3766:
3718:
3716:
3715:
3710:
3708:
3707:
3706:
3705:
3691:
3690:
3654:
3653:
3608:
3606:
3605:
3600:
3597:
3592:
3577:
3574:
3571:
3570:
3569:
3559:
3541:
3540:
3506:
3504:
3503:
3498:
3490:
3489:
3473:
3471:
3470:
3465:
3450:
3448:
3447:
3442:
3436:
3435:
3434:
3424:
3409:
3406:
3392:
3391:
3390:
3389:
3372:
3371:
3356:
3355:
3340:
3339:
3338:
3337:
3323:
3322:
3298:
3297:
3296:
3295:
3281:
3280:
3262:
3261:
3252:
3251:
3233:
3232:
3223:
3222:
3201:
3200:
3173:
3170:
3158:
3156:
3155:
3150:
3121:
3118:
3104:
3103:
3102:
3101:
3087:
3086:
3067:
3065:
3064:
3059:
3039:
3038:
3026:
3025:
3009:
3007:
3006:
3001:
2999:
2998:
2989:
2988:
2955:
2952:
2940:
2938:
2937:
2932:
2930:
2929:
2924:
2911:
2909:
2908:
2903:
2895:
2894:
2878:
2876:
2875:
2870:
2858:
2856:
2855:
2850:
2838:
2836:
2835:
2830:
2818:
2816:
2815:
2810:
2802:
2801:
2800:
2799:
2782:
2781:
2760:
2759:
2747:
2744:
2735:
2733:
2732:
2727:
2725:
2724:
2708:
2706:
2705:
2700:
2692:
2691:
2675:
2673:
2672:
2667:
2653:
2652:
2640:
2639:
2623:
2621:
2620:
2615:
2603:
2601:
2600:
2595:
2581:
2580:
2568:
2567:
2536:
2534:
2533:
2528:
2517:
2516:
2511:
2483:
2481:
2480:
2475:
2463:
2461:
2460:
2455:
2443:
2441:
2440:
2435:
2417:
2415:
2414:
2409:
2397:
2395:
2394:
2389:
2332:
2330:
2329:
2324:
2313:
2312:
2307:
2289:
2288:
2283:
2244:
2242:
2241:
2236:
2224:
2222:
2221:
2216:
2201:
2199:
2198:
2193:
2188:
2174:
2173:
2168:
2155:
2153:
2152:
2147:
2145:
2144:
2143:
2142:
2132:
2119:
2117:
2116:
2111:
2091:
2077:
2076:
2071:
2059:
2039:
2038:
2033:
2014:
2012:
2011:
2006:
2001:
1987:
1986:
1981:
1972:
1971:
1970:
1969:
1959:
1943:
1941:
1940:
1935:
1923:
1921:
1920:
1915:
1903:
1901:
1900:
1895:
1893:
1892:
1891:
1890:
1880:
1867:
1865:
1864:
1859:
1847:
1845:
1844:
1839:
1834:
1831:
1798:
1796:
1795:
1790:
1779:of given degree
1778:
1776:
1775:
1770:
1743:
1741:
1740:
1735:
1724:
1723:
1718:
1699:
1697:
1696:
1691:
1679:
1677:
1676:
1671:
1646:
1644:
1643:
1638:
1624:
1623:
1603:
1601:
1600:
1595:
1583:
1581:
1580:
1575:
1554:
1552:
1551:
1546:
1535:
1534:
1529:
1510:
1508:
1507:
1502:
1500:
1499:
1494:
1481:
1479:
1478:
1473:
1461:
1459:
1458:
1453:
1426:
1424:
1423:
1418:
1388:
1386:
1385:
1380:
1359:
1357:
1356:
1351:
1327:
1325:
1324:
1319:
1293:
1290:
1276:
1275:
1270:
1229:
1227:
1226:
1221:
1209:
1207:
1206:
1201:
1186:
1184:
1183:
1178:
1157:
1155:
1154:
1149:
1132:
1131:
1094:
1092:
1091:
1086:
1074:
1072:
1071:
1066:
1064:
1063:
1047:
1045:
1044:
1039:
1025:
1024:
1000:
997:
988:
986:
985:
980:
962:
960:
959:
954:
952:
944:
943:
927:
925:
924:
919:
914:
913:
888:
886:
885:
880:
878:
863:
861:
860:
855:
850:
849:
844:
832:
818:
817:
801:
799:
798:
793:
788:
787:
782:
770:
731:
729:
728:
723:
711:
709:
708:
703:
691:
689:
688:
683:
669:
668:
663:
650:
648:
647:
642:
640:
639:
634:
628:
590:
588:
587:
582:
566:
564:
563:
558:
556:
555:
550:
537:
535:
534:
529:
502:
500:
499:
494:
461:
459:
458:
453:
427:
407:
406:
401:
384:
382:
381:
376:
374:
373:
368:
351:
349:
348:
343:
280:one-way function
277:
275:
274:
269:
267:
249:
247:
246:
241:
239:
238:
220:
219:
218:
217:
207:
198:
197:
196:
195:
185:
166:
164:
163:
158:
146:
144:
143:
138:
126:
124:
123:
118:
116:
115:
114:
113:
103:
78:
76:
75:
70:
62:
61:
6549:
6548:
6544:
6543:
6542:
6540:
6539:
6538:
6524:
6523:
6522:
6517:
6503:
6438:
6400:
6367:
6324:
6268:
6225:
6129:
6091:
6064:Proth's theorem
6006:Primality tests
6000:
5992:
5962:
5961:
5956:
5952:
5947:
5943:
5938:
5934:
5929:
5925:
5920:
5913:
5908:
5904:
5899:
5877:
5853:
5852:
5804:
5799:
5798:
5758:
5729:
5728:
5681:
5640:
5635:
5634:
5611:
5604:
5599:
5598:
5572:
5565:
5560:
5559:
5536:
5476:
5475:
5417:
5413:
5403:
5380:
5347:
5297:
5293:
5292:
5288:
5277:
5276:
5266:
5230:
5214:
5196:
5166:
5161:
5160:
5138:
5137:
5118:
5117:
5092:
5087:
5086:
5049:
5035:
5034:
5002:
4989:
4984:
4983:
4962:
4943:
4938:
4937:
4911:
4910:
4885:
4884:
4865:
4864:
4840:
4835:
4834:
4831:
4793:
4768:
4743:
4738:
4737:
4712:
4711:
4687:
4676:
4675:
4654:
4649:
4648:
4627:
4622:
4621:
4602:
4601:
4574:
4555:
4539:
4534:
4533:
4508:
4507:
4474:
4469:
4468:
4435:
4430:
4429:
4402:
4380:
4370:
4365:
4364:
4311:
4303:
4302:
4283:
4282:
4261:
4256:
4255:
4199:
4193: mod
4175:
4153:
4143:
4133:
4111:
4101:
4080:
4079:
4053:
4042:
4041:
3997:
3992:
3987:
3986:
3953:
3948:
3947:
3927: mod
3913:
3908:
3898:
3862:
3854:
3833:
3832:
3804:
3803:
3782:
3777:
3776:
3724:
3723:
3697:
3692:
3682:
3645:
3614:
3613:
3561:
3532:
3512:
3511:
3481:
3476:
3475:
3456:
3455:
3426:
3381:
3376:
3363:
3347:
3329:
3324:
3314:
3287:
3282:
3272:
3253:
3243:
3224:
3214:
3192:
3164:
3163:
3093:
3088:
3078:
3070:
3069:
3030:
3017:
3012:
3011:
2990:
2980:
2946:
2945:
2919:
2914:
2913:
2886:
2881:
2880:
2861:
2860:
2841:
2840:
2821:
2820:
2791:
2786:
2773:
2751:
2738:
2737:
2716:
2711:
2710:
2683:
2678:
2677:
2644:
2631:
2626:
2625:
2606:
2605:
2572:
2559:
2554:
2553:
2543:
2506:
2501:
2500:
2466:
2465:
2446:
2445:
2420:
2419:
2400:
2399:
2398:, then divides
2338:
2337:
2302:
2278:
2255:
2254:
2251:
2227:
2226:
2207:
2206:
2163:
2158:
2157:
2134:
2127:
2122:
2121:
2066:
2028:
2017:
2016:
1976:
1961:
1954:
1949:
1948:
1926:
1925:
1906:
1905:
1882:
1875:
1870:
1869:
1850:
1849:
1832: mod
1801:
1800:
1781:
1780:
1746:
1745:
1713:
1702:
1701:
1682:
1681:
1662:
1661:
1658:
1653:
1615:
1610:
1609:
1586:
1585:
1557:
1556:
1524:
1513:
1512:
1489:
1484:
1483:
1464:
1463:
1429:
1428:
1391:
1390:
1362:
1361:
1330:
1329:
1265:
1236:
1235:
1212:
1211:
1192:
1191:
1169:
1168:
1164:
1123:
1097:
1096:
1077:
1076:
1055:
1050:
1049:
1016:
991:
990:
965:
964:
935:
930:
929:
905:
891:
890:
869:
868:
867:A divisor is a
839:
809:
804:
803:
777:
734:
733:
714:
713:
694:
693:
658:
653:
652:
629:
616:
615:
612:
596:valuation rings
573:
572:
545:
540:
539:
505:
504:
464:
463:
396:
391:
390:
363:
358:
357:
354:algebraic curve
319:
318:
315:
309:
307:Function Fields
304:
252:
251:
230:
209:
202:
187:
180:
169:
168:
149:
148:
129:
128:
105:
98:
81:
80:
53:
48:
47:
41:Leonard Adleman
12:
11:
5:
6547:
6545:
6537:
6536:
6526:
6525:
6519:
6518:
6516:
6515:
6508:
6505:
6504:
6502:
6501:
6496:
6491:
6486:
6481:
6467:
6462:
6457:
6452:
6446:
6444:
6440:
6439:
6437:
6436:
6431:
6426:
6424:TonelliâShanks
6421:
6416:
6410:
6408:
6402:
6401:
6399:
6398:
6393:
6388:
6383:
6377:
6375:
6369:
6368:
6366:
6365:
6360:
6358:Index calculus
6355:
6353:PohligâHellman
6350:
6345:
6340:
6334:
6332:
6326:
6325:
6323:
6322:
6317:
6312:
6307:
6305:Newton-Raphson
6302:
6297:
6292:
6287:
6281:
6279:
6270:
6269:
6267:
6266:
6261:
6256:
6251:
6246:
6241:
6235:
6233:
6231:Multiplication
6227:
6226:
6224:
6223:
6218:
6216:Trial division
6213:
6208:
6203:
6201:Rational sieve
6198:
6191:
6186:
6181:
6173:
6165:
6160:
6155:
6150:
6145:
6139:
6137:
6131:
6130:
6128:
6127:
6122:
6117:
6112:
6107:
6105:Sieve of Atkin
6101:
6099:
6093:
6092:
6090:
6089:
6084:
6079:
6074:
6067:
6060:
6053:
6046:
6041:
6036:
6031:
6029:Elliptic curve
6026:
6021:
6016:
6010:
6008:
6002:
6001:
5993:
5991:
5990:
5983:
5976:
5968:
5960:
5959:
5950:
5941:
5932:
5923:
5911:
5901:
5900:
5898:
5895:
5894:
5893:
5888:
5883:
5876:
5873:
5860:
5840:
5835:
5830:
5827:
5823:
5819:
5816:
5811:
5807:
5773:
5769:
5765:
5761:
5757:
5754:
5751:
5748:
5745:
5742:
5739:
5736:
5716:
5713:
5710:
5707:
5704:
5701:
5696:
5692:
5688:
5684:
5680:
5676:
5672:
5669:
5666:
5663:
5659:
5655:
5652:
5647:
5643:
5618:
5614:
5608:
5579:
5575:
5569:
5535:
5532:
5519:
5516:
5513:
5510:
5507:
5504:
5501:
5498:
5495:
5492:
5489:
5486:
5483:
5464:
5463:
5451:
5444:
5439:
5436:
5430:
5425:
5422:
5416:
5410:
5406:
5402:
5398:
5391:
5388:
5383:
5379:
5376:
5373:
5370:
5367:
5364:
5358:
5355:
5350:
5346:
5343:
5340:
5337:
5333:
5329:
5326:
5323:
5320:
5317:
5311:
5306:
5303:
5296:
5291:
5287:
5284:
5265:
5262:
5261:
5260:
5248:
5245:
5242:
5237:
5233:
5229:
5226:
5221:
5217:
5211:
5208:
5203:
5199:
5194:
5190:
5187:
5184:
5181:
5178:
5173:
5169:
5145:
5125:
5099:
5095:
5072:
5069:
5064:
5061:
5056:
5052:
5048:
5045:
5042:
5022:
5019:
5016:
5011:
5006:
5001:
4996:
4992:
4969:
4965:
4961:
4958:
4955:
4950:
4946:
4923:
4920:
4898:
4895:
4892:
4872:
4852:
4847:
4843:
4830:
4829:Reduction step
4827:
4814:
4811:
4808:
4805:
4800:
4796:
4792:
4789:
4786:
4783:
4780:
4775:
4771:
4767:
4764:
4761:
4758:
4755:
4750:
4746:
4725:
4722:
4719:
4699:
4694:
4690:
4686:
4683:
4661:
4657:
4634:
4630:
4609:
4589:
4586:
4581:
4577:
4573:
4570:
4567:
4562:
4558:
4554:
4551:
4546:
4542:
4521:
4518:
4515:
4495:
4492:
4489:
4486:
4481:
4477:
4456:
4453:
4450:
4447:
4442:
4438:
4417:
4414:
4409:
4405:
4401:
4398:
4395:
4392:
4387:
4383:
4377:
4373:
4349:
4346:
4343:
4340:
4337:
4333:
4329:
4326:
4323:
4318:
4314:
4310:
4290:
4268:
4264:
4252:
4251:
4240:
4237:
4234:
4231:
4228:
4225:
4221:
4217:
4214:
4211:
4206:
4202:
4198:
4190:
4187:
4182:
4178:
4174:
4171:
4168:
4165:
4160:
4156:
4150:
4146:
4140:
4136:
4132:
4129:
4126:
4123:
4118:
4114:
4108:
4104:
4098:
4095:
4092:
4088:
4062:
4057:
4052:
4049:
4040:for some unit
4029:
4026:
4023:
4018:
4015:
4012:
4009:
4004:
4000:
3995:
3974:
3971:
3968:
3965:
3960:
3956:
3944:
3943:
3932:
3920:
3916:
3911:
3905:
3901:
3897:
3894:
3891:
3888:
3885:
3882:
3879:
3876:
3869:
3865:
3861:
3857:
3851:
3848:
3845:
3841:
3817:
3814:
3811:
3789:
3785:
3764:
3761:
3758:
3755:
3752:
3749:
3746:
3743:
3740:
3737:
3734:
3731:
3720:
3719:
3704:
3700:
3695:
3689:
3685:
3681:
3678:
3675:
3672:
3669:
3666:
3663:
3660:
3657:
3652:
3648:
3644:
3641:
3638:
3635:
3632:
3629:
3626:
3622:
3610:
3609:
3596:
3591:
3587:
3583:
3580:
3568:
3564:
3558:
3554:
3550:
3547:
3544:
3539:
3535:
3531:
3528:
3525:
3522:
3519:
3496:
3493:
3488:
3484:
3463:
3452:
3451:
3440:
3433:
3429:
3423:
3419:
3415:
3412:
3404:
3401:
3398:
3395:
3388:
3384:
3379:
3375:
3370:
3366:
3362:
3359:
3354:
3350:
3346:
3343:
3336:
3332:
3327:
3321:
3317:
3313:
3310:
3307:
3304:
3301:
3294:
3290:
3285:
3279:
3275:
3271:
3268:
3265:
3260:
3256:
3250:
3246:
3242:
3239:
3236:
3231:
3227:
3221:
3217:
3213:
3210:
3207:
3204:
3199:
3195:
3191:
3188:
3185:
3182:
3179:
3176:
3148:
3145:
3142:
3139:
3136:
3133:
3130:
3127:
3124:
3116:
3113:
3110:
3107:
3100:
3096:
3091:
3085:
3081:
3077:
3057:
3054:
3051:
3048:
3045:
3042:
3037:
3033:
3029:
3024:
3020:
2997:
2993:
2987:
2983:
2979:
2976:
2973:
2970:
2967:
2964:
2961:
2958:
2928:
2923:
2901:
2898:
2893:
2889:
2868:
2848:
2828:
2808:
2805:
2798:
2794:
2789:
2785:
2780:
2776:
2772:
2769:
2766:
2763:
2758:
2754:
2750:
2723:
2719:
2698:
2695:
2690:
2686:
2665:
2662:
2659:
2656:
2651:
2647:
2643:
2638:
2634:
2613:
2593:
2590:
2587:
2584:
2579:
2575:
2571:
2566:
2562:
2542:
2539:
2526:
2523:
2520:
2515:
2510:
2473:
2453:
2433:
2430:
2427:
2407:
2387:
2384:
2381:
2378:
2375:
2372:
2369:
2366:
2363:
2360:
2357:
2354:
2351:
2348:
2345:
2322:
2319:
2316:
2311:
2306:
2301:
2298:
2295:
2292:
2287:
2282:
2277:
2274:
2271:
2268:
2265:
2262:
2250:
2247:
2234:
2214:
2191:
2187:
2183:
2180:
2177:
2172:
2167:
2141:
2137:
2131:
2109:
2106:
2103:
2100:
2097:
2094:
2090:
2086:
2083:
2080:
2075:
2070:
2065:
2062:
2058:
2054:
2051:
2048:
2045:
2042:
2037:
2032:
2027:
2024:
2004:
2000:
1996:
1993:
1990:
1985:
1980:
1975:
1968:
1964:
1958:
1933:
1913:
1889:
1885:
1879:
1857:
1837:
1829:
1826:
1823:
1820:
1817:
1814:
1811:
1808:
1788:
1768:
1765:
1762:
1759:
1756:
1753:
1733:
1730:
1727:
1722:
1717:
1712:
1709:
1689:
1669:
1657:
1654:
1652:
1651:Precomputation
1649:
1636:
1633:
1630:
1627:
1622:
1618:
1593:
1573:
1570:
1567:
1564:
1544:
1541:
1538:
1533:
1528:
1523:
1520:
1498:
1493:
1471:
1451:
1448:
1445:
1442:
1439:
1436:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1378:
1375:
1372:
1369:
1349:
1346:
1343:
1340:
1337:
1317:
1314:
1311:
1308:
1305:
1302:
1299:
1296:
1288:
1285:
1282:
1279:
1274:
1269:
1264:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1219:
1199:
1176:
1163:
1160:
1147:
1144:
1141:
1138:
1135:
1130:
1126:
1122:
1119:
1116:
1113:
1110:
1107:
1104:
1084:
1062:
1058:
1037:
1034:
1031:
1028:
1023:
1019:
1015:
1012:
1009:
1006:
1003:
989:is defined as
978:
975:
972:
951:
947:
942:
938:
917:
912:
908:
904:
901:
898:
877:
853:
848:
843:
838:
835:
831:
827:
824:
821:
816:
812:
791:
786:
781:
776:
773:
769:
765:
762:
759:
756:
753:
750:
747:
744:
741:
721:
701:
681:
678:
675:
672:
667:
662:
638:
633:
627:
623:
611:
608:
580:
554:
549:
527:
524:
521:
518:
515:
512:
492:
489:
486:
483:
480:
477:
474:
471:
451:
448:
445:
442:
439:
436:
433:
430:
426:
422:
419:
416:
413:
410:
405:
400:
372:
367:
341:
338:
335:
332:
329:
326:
311:Main article:
308:
305:
303:
300:
266:
262:
259:
237:
233:
229:
226:
223:
216:
212:
206:
201:
194:
190:
184:
179:
176:
156:
136:
112:
108:
102:
97:
94:
91:
88:
68:
65:
60:
56:
37:subexponential
13:
10:
9:
6:
4:
3:
2:
6546:
6535:
6532:
6531:
6529:
6513:
6510:
6509:
6506:
6500:
6497:
6495:
6492:
6490:
6487:
6485:
6482:
6479:
6475:
6471:
6468:
6466:
6463:
6461:
6458:
6456:
6453:
6451:
6448:
6447:
6445:
6441:
6435:
6432:
6430:
6427:
6425:
6422:
6420:
6419:Pocklington's
6417:
6415:
6412:
6411:
6409:
6407:
6403:
6397:
6394:
6392:
6389:
6387:
6384:
6382:
6379:
6378:
6376:
6374:
6370:
6364:
6361:
6359:
6356:
6354:
6351:
6349:
6346:
6344:
6341:
6339:
6336:
6335:
6333:
6331:
6327:
6321:
6318:
6316:
6313:
6311:
6308:
6306:
6303:
6301:
6298:
6296:
6293:
6291:
6288:
6286:
6283:
6282:
6280:
6278:
6275:
6271:
6265:
6262:
6260:
6257:
6255:
6252:
6250:
6247:
6245:
6242:
6240:
6237:
6236:
6234:
6232:
6228:
6222:
6219:
6217:
6214:
6212:
6209:
6207:
6204:
6202:
6199:
6197:
6196:
6192:
6190:
6187:
6185:
6182:
6180:
6178:
6174:
6172:
6170:
6166:
6164:
6163:Pollard's rho
6161:
6159:
6156:
6154:
6151:
6149:
6146:
6144:
6141:
6140:
6138:
6136:
6132:
6126:
6123:
6121:
6118:
6116:
6113:
6111:
6108:
6106:
6103:
6102:
6100:
6098:
6094:
6088:
6085:
6083:
6080:
6078:
6075:
6073:
6072:
6068:
6066:
6065:
6061:
6059:
6058:
6054:
6052:
6051:
6047:
6045:
6042:
6040:
6037:
6035:
6032:
6030:
6027:
6025:
6022:
6020:
6017:
6015:
6012:
6011:
6009:
6007:
6003:
5999:
5996:
5989:
5984:
5982:
5977:
5975:
5970:
5969:
5966:
5954:
5951:
5945:
5942:
5936:
5933:
5927:
5924:
5918:
5916:
5912:
5906:
5903:
5896:
5892:
5889:
5887:
5884:
5882:
5879:
5878:
5874:
5872:
5858:
5833:
5828:
5825:
5821:
5817:
5809:
5805:
5796:
5791:
5789:
5788:global fields
5771:
5767:
5763:
5752:
5746:
5743:
5737:
5734:
5708:
5702:
5699:
5694:
5690:
5686:
5678:
5674:
5670:
5664:
5661:
5657:
5653:
5645:
5641:
5616:
5612:
5595:
5577:
5573:
5557:
5553:
5549:
5545:
5541:
5533:
5531:
5514:
5511:
5508:
5505:
5499:
5493:
5490:
5487:
5484:
5473:
5469:
5449:
5442:
5437:
5434:
5428:
5423:
5420:
5414:
5408:
5404:
5400:
5396:
5389:
5386:
5377:
5374:
5371:
5368:
5365:
5356:
5353:
5344:
5341:
5338:
5331:
5324:
5318:
5315:
5309:
5304:
5301:
5294:
5289:
5285:
5282:
5275:
5274:
5273:
5271:
5263:
5246:
5243:
5235:
5231:
5224:
5219:
5215:
5209:
5206:
5201:
5197:
5192:
5188:
5182:
5176:
5171:
5167:
5159:
5158:
5157:
5143:
5123:
5115:
5097:
5093:
5070:
5067:
5062:
5054:
5050:
5043:
5040:
5017:
5009:
4999:
4994:
4990:
4967:
4963:
4959:
4956:
4953:
4948:
4944:
4921:
4918:
4896:
4893:
4890:
4870:
4850:
4845:
4841:
4828:
4826:
4809:
4803:
4798:
4794:
4790:
4784:
4778:
4773:
4769:
4765:
4759:
4753:
4748:
4744:
4723:
4720:
4717:
4692:
4688:
4681:
4659:
4655:
4632:
4628:
4607:
4579:
4575:
4568:
4560:
4556:
4552:
4549:
4544:
4540:
4519:
4516:
4513:
4490:
4484:
4479:
4475:
4451:
4445:
4440:
4436:
4407:
4403:
4396:
4390:
4385:
4381:
4375:
4371:
4361:
4344:
4341:
4338:
4331:
4324:
4321:
4316:
4312:
4288:
4266:
4262:
4238:
4232:
4229:
4226:
4219:
4212:
4209:
4204:
4200:
4180:
4176:
4169:
4163:
4158:
4154:
4148:
4144:
4138:
4134:
4130:
4127:
4124:
4121:
4116:
4112:
4106:
4102:
4096:
4093:
4090:
4086:
4078:
4077:
4076:
4060:
4050:
4047:
4027:
4024:
4021:
4013:
4007:
4002:
3998:
3993:
3969:
3963:
3958:
3954:
3930:
3918:
3914:
3903:
3899:
3892:
3889:
3883:
3877:
3874:
3867:
3863:
3859:
3855:
3849:
3846:
3843:
3839:
3831:
3830:
3829:
3815:
3812:
3809:
3787:
3783:
3762:
3759:
3756:
3753:
3750:
3744:
3741:
3738:
3735:
3729:
3702:
3698:
3687:
3683:
3676:
3673:
3667:
3661:
3658:
3650:
3642:
3639:
3636:
3633:
3624:
3612:
3611:
3594:
3589:
3585:
3581:
3578:
3566:
3562:
3556:
3552:
3548:
3545:
3542:
3537:
3529:
3526:
3523:
3520:
3510:
3509:
3508:
3494:
3491:
3486:
3482:
3461:
3431:
3427:
3421:
3417:
3413:
3402:
3393:
3386:
3382:
3377:
3373:
3368:
3364:
3357:
3352:
3348:
3344:
3341:
3334:
3330:
3325:
3319:
3315:
3311:
3308:
3305:
3302:
3299:
3292:
3288:
3283:
3277:
3273:
3269:
3266:
3263:
3258:
3254:
3248:
3244:
3240:
3237:
3234:
3229:
3225:
3219:
3215:
3211:
3208:
3205:
3197:
3189:
3186:
3183:
3180:
3162:
3161:
3160:
3146:
3143:
3134:
3131:
3128:
3125:
3111:
3108:
3105:
3098:
3094:
3089:
3083:
3079:
3075:
3052:
3049:
3046:
3043:
3035:
3031:
3027:
3022:
3018:
2995:
2991:
2985:
2981:
2977:
2974:
2968:
2965:
2962:
2959:
2942:
2926:
2899:
2896:
2891:
2887:
2866:
2846:
2826:
2803:
2796:
2792:
2787:
2783:
2778:
2774:
2767:
2764:
2756:
2752:
2721:
2717:
2696:
2693:
2688:
2684:
2663:
2660:
2657:
2654:
2649:
2645:
2641:
2636:
2632:
2611:
2591:
2588:
2585:
2582:
2577:
2573:
2569:
2564:
2560:
2550:
2548:
2540:
2538:
2521:
2513:
2498:
2494:
2489:
2487:
2471:
2451:
2431:
2428:
2425:
2405:
2382:
2379:
2376:
2373:
2367:
2361:
2358:
2355:
2352:
2346:
2343:
2334:
2317:
2309:
2299:
2293:
2285:
2275:
2269:
2266:
2263:
2248:
2246:
2232:
2212:
2203:
2189:
2185:
2178:
2170:
2139:
2135:
2107:
2104:
2098:
2095:
2092:
2088:
2081:
2073:
2060:
2056:
2049:
2046:
2043:
2035:
2025:
2022:
2002:
1998:
1991:
1983:
1973:
1966:
1962:
1945:
1931:
1911:
1887:
1883:
1855:
1835:
1827:
1824:
1818:
1815:
1812:
1806:
1786:
1763:
1760:
1757:
1751:
1728:
1720:
1710:
1707:
1700:, a function
1687:
1667:
1655:
1650:
1648:
1631:
1625:
1620:
1616:
1605:
1591:
1571:
1568:
1565:
1562:
1539:
1531:
1521:
1518:
1496:
1469:
1446:
1443:
1440:
1434:
1411:
1408:
1405:
1402:
1396:
1376:
1373:
1370:
1367:
1344:
1341:
1338:
1312:
1309:
1303:
1297:
1294:
1286:
1280:
1272:
1262:
1256:
1250:
1244:
1241:
1233:
1232:smooth number
1217:
1197:
1188:
1174:
1161:
1159:
1142:
1136:
1133:
1128:
1124:
1120:
1117:
1111:
1105:
1102:
1082:
1060:
1056:
1035:
1029:
1021:
1017:
1013:
1010:
1004:
976:
973:
970:
945:
940:
936:
915:
910:
906:
902:
899:
896:
865:
846:
836:
833:
829:
825:
819:
814:
810:
784:
774:
771:
767:
763:
757:
751:
745:
742:
739:
719:
699:
679:
676:
673:
670:
665:
636:
625:
621:
609:
607:
605:
601:
597:
592:
578:
570:
552:
522:
519:
516:
510:
484:
481:
478:
472:
443:
440:
437:
431:
424:
417:
414:
411:
403:
388:
370:
355:
336:
333:
330:
324:
314:
306:
301:
299:
297:
293:
289:
285:
281:
260:
257:
235:
231:
224:
221:
214:
210:
192:
188:
177:
174:
154:
134:
110:
106:
95:
92:
89:
86:
66:
63:
58:
54:
44:
42:
38:
35:
31:
27:
23:
19:
6511:
6362:
6193:
6176:
6168:
6087:MillerâRabin
6069:
6062:
6055:
6050:LucasâLehmer
6048:
5953:
5944:
5935:
5926:
5905:
5792:
5596:
5556:finite field
5537:
5465:
5267:
4832:
4362:
4253:
3945:
3721:
3453:
2943:
2551:
2544:
2490:
2335:
2252:
2204:
1946:
1744:and a curve
1659:
1606:
1189:
1165:
866:
613:
593:
316:
284:cryptography
250:for a fixed
45:
39:complexity.
30:finite field
21:
15:
6343:Pollard rho
6300:Goldschmidt
6034:Pocklington
6024:BaillieâPSW
2333:are found.
1210:are called
18:mathematics
6455:Cornacchia
6450:Chakravala
5998:algorithms
5897:References
5468:L-notation
5466:using the
5264:Complexity
2736:satisfies
1799:such that
1680:of degree
604:valuations
6429:Berlekamp
6386:Euclidean
6274:Euclidean
6254:ToomâCook
6249:Karatsuba
5747:
5594:as well.
5472:heuristic
5375:
5369:
5342:
5286:
5244:−
5225:
5207:∈
5193:∑
5177:
5044:
5000:∈
4960:∏
4804:
4791:−
4779:
4774:∗
4754:
4721:∈
4689:α
4682:ϕ
4656:α
4576:α
4569:ϕ
4561:∗
4517:∈
4485:
4480:∗
4446:
4441:∗
4404:α
4397:ϕ
4391:
4386:∗
4342:−
4322:−
4230:−
4210:−
4177:α
4170:ϕ
4164:
4159:∗
4131:∑
4128:≡
4122:
4117:∗
4094:∈
4087:∑
4051:∈
4008:
4003:∗
3964:
3959:∗
3900:α
3893:ϕ
3890:∏
3878:ϕ
3875:≡
3847:∈
3840:∏
3813:∈
3730:ϕ
3684:α
3677:ϕ
3674:∏
3662:ϕ
3625:ϕ
3621:⟹
3595:∗
3582:∈
3553:α
3549:∏
3418:α
3414:∏
3374:−
3345:∑
3312:∑
3267:∑
3264:−
3238:∑
3209:∑
3112:
3076:∑
2978:∑
2784:−
2753:α
2694:∈
2685:α
2646:α
2633:α
2486:Gray code
2429:∈
2300:×
2276:∈
2102:↦
2064:→
2023:ϕ
1974:≃
1825:≡
1711:∈
1626:
1522:∈
1447:⋅
1441:⋅
1298:
1287:∣
1263:∈
1137:
1125:α
1121:∑
1106:
1014:∑
974:∈
946:∈
937:α
907:α
903:∑
677:⊂
671:⊂
261:∈
228:↦
200:→
96:∈
34:heuristic
32:. It has
6528:Category
6396:Lehmer's
6290:Chunking
6277:division
6206:Fermat's
5875:See also
5738:<<
4506:for all
1608:express
1048:, where
610:Divisors
567:and has
462:, where
292:El Gamal
282:used in
6512:Italics
6434:Kunerth
6414:Cipolla
6295:Fourier
6264:FĂŒrer's
6158:Euler's
6148:Dixon's
6071:PĂ©pin's
4301:modulo
2495:or the
2418:by any
2249:Sieving
1848:. Here
6494:Schoof
6381:Binary
6285:Binary
6221:Shor's
6039:Fermat
5546:: the
4833:First
4254:where
3454:where
2819:where
2547:places
1904:. Let
1162:Method
928:where
600:places
290:, the
6315:Short
6044:Lucas
5033:with
1482:over
278:is a
6310:Long
6244:Long
5793:The
5063:<
4982:for
4894:<
4863:mod
3010:for
2859:and
1389:and
1310:<
317:Let
79:for
20:the
6474:LLL
6320:SRT
6179:+ 1
6171:â 1
6019:APR
6014:AKS
5744:log
5542:in
5283:exp
5272:in
5216:log
5168:log
5041:deg
4795:log
4770:log
4745:log
4674:or
4476:log
4437:log
4382:log
4155:log
4113:log
3999:log
3955:log
3407:div
3171:div
3119:div
3109:deg
2953:div
2745:div
2604:of
1617:log
1295:deg
1134:deg
1103:deg
998:div
732:is
127:,
16:In
6530::
6478:KZ
6476:;
5914:^
5790:.
5671:64
5435:32
5372:ln
5366:ln
5339:ln
5302:32
4825:.
4647:,
4620:,
4360:.
4075:.
2941:.
2245:.
2202:.
1944:.
1604:.
1511:,
1187:.
1158:.
864:.
591:.
298:.
6480:)
6472:(
6177:p
6169:p
5987:e
5980:t
5973:v
5859:B
5839:]
5834:2
5829:,
5826:2
5822:/
5818:1
5815:[
5810:p
5806:L
5772:2
5768:/
5764:1
5760:)
5756:)
5753:p
5750:(
5741:(
5735:n
5715:]
5712:)
5709:1
5706:(
5703:o
5700:+
5695:3
5691:/
5687:1
5683:)
5679:9
5675:/
5668:(
5665:,
5662:3
5658:/
5654:1
5651:[
5646:p
5642:L
5617:n
5613:p
5607:F
5578:n
5574:p
5568:F
5518:)
5515:s
5512:+
5509:y
5506:r
5503:(
5500:N
5497:)
5494:s
5491:+
5488:m
5485:r
5482:(
5450:]
5443:3
5438:9
5429:,
5424:3
5421:1
5415:[
5409:p
5405:L
5401:=
5397:)
5390:3
5387:2
5382:)
5378:p
5363:(
5357:3
5354:1
5349:)
5345:p
5336:(
5332:)
5328:)
5325:1
5322:(
5319:o
5316:+
5310:3
5305:9
5295:(
5290:(
5247:l
5241:)
5236:i
5232:g
5228:(
5220:a
5210:S
5202:i
5198:g
5189:=
5186:)
5183:b
5180:(
5172:a
5144:a
5124:B
5098:i
5094:b
5071:B
5068:n
5060:)
5055:i
5051:b
5047:(
5021:]
5018:x
5015:[
5010:p
5005:F
4995:i
4991:b
4968:i
4964:b
4957:=
4954:b
4949:l
4945:a
4922:B
4919:n
4897:n
4891:l
4871:f
4851:b
4846:l
4842:a
4813:)
4810:u
4807:(
4799:a
4788:)
4785:g
4782:(
4766:=
4763:)
4760:g
4757:(
4749:a
4724:S
4718:g
4698:)
4693:i
4685:(
4660:i
4633:1
4629:h
4608:h
4588:)
4585:)
4580:i
4572:(
4566:(
4557:g
4553:o
4550:l
4545:1
4541:h
4520:S
4514:g
4494:)
4491:g
4488:(
4455:)
4452:g
4449:(
4416:)
4413:)
4408:i
4400:(
4394:(
4376:1
4372:h
4348:)
4345:1
4339:p
4336:(
4332:/
4328:)
4325:1
4317:n
4313:p
4309:(
4289:h
4267:1
4263:h
4239:,
4236:)
4233:1
4227:p
4224:(
4220:/
4216:)
4213:1
4205:n
4201:p
4197:(
4189:)
4186:)
4181:i
4173:(
4167:(
4149:1
4145:h
4139:i
4135:a
4125:g
4107:g
4103:e
4097:S
4091:g
4061:p
4056:F
4048:u
4028:x
4025:u
4022:=
4017:)
4014:x
4011:(
3994:a
3973:)
3970:x
3967:(
3931:f
3919:i
3915:a
3910:)
3904:i
3896:(
3887:)
3884:c
3881:(
3868:g
3864:e
3860:h
3856:g
3850:S
3844:g
3816:S
3810:g
3788:g
3784:e
3763:s
3760:+
3757:m
3754:r
3751:=
3748:)
3745:s
3742:+
3739:y
3736:r
3733:(
3703:i
3699:a
3694:)
3688:i
3680:(
3671:)
3668:c
3665:(
3659:=
3656:)
3651:h
3647:)
3643:s
3640:+
3637:y
3634:r
3631:(
3628:(
3590:p
3586:F
3579:c
3567:i
3563:a
3557:i
3546:c
3543:=
3538:h
3534:)
3530:s
3527:+
3524:y
3521:r
3518:(
3495:1
3492:=
3487:v
3483:f
3462:v
3439:)
3432:i
3428:a
3422:i
3411:(
3403:=
3400:)
3397:)
3394:v
3387:i
3383:v
3378:f
3369:i
3365:v
3361:(
3358:h
3353:i
3349:a
3342:=
3335:i
3331:v
3326:f
3320:i
3316:a
3309:v
3306:h
3303:+
3300:v
3293:i
3289:v
3284:f
3278:i
3274:a
3270:h
3259:i
3255:v
3249:i
3245:a
3241:h
3235:=
3230:i
3226:v
3220:i
3216:a
3212:h
3206:=
3203:)
3198:h
3194:)
3190:s
3187:+
3184:y
3181:r
3178:(
3175:(
3147:0
3144:=
3141:)
3138:)
3135:s
3132:+
3129:y
3126:r
3123:(
3115:(
3106:=
3099:i
3095:v
3090:f
3084:i
3080:a
3056:)
3053:s
3050:+
3047:y
3044:r
3041:(
3036:i
3032:v
3028:=
3023:i
3019:a
2996:i
2992:v
2986:i
2982:a
2975:=
2972:)
2969:s
2966:+
2963:y
2960:r
2957:(
2927:p
2922:F
2900:1
2897:=
2892:u
2888:f
2867:u
2847:K
2827:h
2807:)
2804:u
2797:i
2793:v
2788:f
2779:i
2775:v
2771:(
2768:h
2765:=
2762:)
2757:i
2749:(
2722:i
2718:v
2697:K
2689:i
2664:.
2661:.
2658:.
2655:,
2650:2
2642:,
2637:1
2612:K
2592:.
2589:.
2586:.
2583:,
2578:2
2574:v
2570:,
2565:1
2561:v
2525:]
2522:x
2519:[
2514:p
2509:F
2472:B
2452:f
2432:S
2426:g
2406:f
2386:)
2383:s
2380:+
2377:y
2374:r
2371:(
2368:N
2365:)
2362:s
2359:+
2356:m
2353:r
2350:(
2347:=
2344:f
2321:]
2318:x
2315:[
2310:p
2305:F
2297:]
2294:x
2291:[
2286:p
2281:F
2273:)
2270:s
2267:,
2264:r
2261:(
2233:S
2213:B
2190:f
2186:/
2182:]
2179:x
2176:[
2171:p
2166:F
2140:n
2136:p
2130:F
2108:.
2105:m
2099:y
2096:,
2093:f
2089:/
2085:]
2082:x
2079:[
2074:p
2069:F
2061:C
2057:/
2053:]
2050:y
2047:,
2044:x
2041:[
2036:p
2031:F
2026::
2003:f
1999:/
1995:]
1992:x
1989:[
1984:p
1979:F
1967:n
1963:p
1957:F
1932:C
1912:K
1888:n
1884:p
1878:F
1856:n
1836:f
1828:0
1822:)
1819:m
1816:,
1813:x
1810:(
1807:C
1787:d
1767:)
1764:y
1761:,
1758:x
1755:(
1752:C
1732:]
1729:x
1726:[
1721:p
1716:F
1708:m
1688:n
1668:f
1635:)
1632:b
1629:(
1621:a
1592:C
1572:s
1569:+
1566:y
1563:r
1543:]
1540:x
1537:[
1532:p
1527:F
1519:m
1497:p
1492:F
1470:K
1450:)
1444:,
1438:(
1435:N
1415:)
1412:s
1409:+
1406:y
1403:r
1400:(
1397:N
1377:s
1374:+
1371:m
1368:r
1348:)
1345:s
1342:,
1339:r
1336:(
1316:}
1313:B
1307:)
1304:g
1301:(
1284:]
1281:x
1278:[
1273:p
1268:F
1260:)
1257:x
1254:(
1251:g
1248:{
1245:=
1242:S
1218:B
1198:B
1175:b
1146:)
1143:P
1140:(
1129:P
1118:=
1115:)
1112:d
1109:(
1083:P
1061:P
1057:v
1036:P
1033:)
1030:x
1027:(
1022:P
1018:v
1011:=
1008:)
1005:x
1002:(
977:K
971:x
950:Z
941:P
916:P
911:P
900:=
897:d
876:Z
852:]
847:p
842:F
837::
834:P
830:/
826:O
823:[
820:=
815:O
811:f
790:]
785:p
780:F
775::
772:P
768:/
764:O
761:[
758:=
755:)
752:P
749:(
746:g
743:e
740:d
720:P
700:P
680:K
674:O
666:p
661:F
637:p
632:F
626:/
622:K
579:x
553:p
548:F
526:)
523:y
520:,
517:x
514:(
511:C
491:)
488:)
485:y
482:,
479:x
476:(
473:C
470:(
450:)
447:)
444:y
441:,
438:x
435:(
432:C
429:(
425:/
421:]
418:y
415:,
412:x
409:[
404:p
399:F
371:p
366:F
340:)
337:y
334:,
331:x
328:(
325:C
265:N
258:x
236:x
232:a
225:a
222:,
215:n
211:p
205:F
193:n
189:p
183:F
178::
175:f
155:n
135:p
111:n
107:p
101:F
93:b
90:,
87:a
67:b
64:=
59:x
55:a
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.