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