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