20:
1844:
2259:
66:, who credit Silver with its earlier independent but unpublished discovery. Pohlig and Hellman also list Richard Schroeppel and H. Block as having found the same algorithm, later than Silver, but again without publishing it.
1041:
In this section, we present the general case of the Pohlig–Hellman algorithm. The core ingredients are the algorithm from the previous section (to compute a logarithm modulo each prime power in the group order) and the
2929:
1683:
672:
613:
1571:
1206:
2102:
1525:
1412:
2933:
890:
736:
2151:
1745:
1894:
1607:
1262:
783:
525:
331:
448:
2441:
1735:
1342:
1010:
149:
2014:
965:
817:
2053:
1455:
2176:
400:
2474:
1295:
1049:(Again, we assume the group to be cyclic, with the understanding that a non-cyclic group must be replaced by the subgroup generated by the logarithm's base element.)
364:
229:
1140:
275:
922:
2171:
1967:
1947:
1917:
1114:
1094:
1074:
1031:
633:
472:
249:
196:
169:
123:
100:
2798:
2434:
102:-adic digits of the logarithm by repeatedly "shifting out" all but one unknown digit in the exponent, and computing that digit by elementary methods.
2666:
2333:
2989:
2608:
2427:
2537:
1415:
451:
74:
As an important special case, which is used as a subroutine in the general algorithm (see below), the Pohlig–Hellman algorithm applies to
2714:
2512:
2410:
2623:
2661:
2598:
2542:
2505:
2803:
2694:
2613:
2603:
2479:
2631:
2884:
1612:
2879:
2709:
2846:
2760:
2325:
638:
533:
1530:
2925:
2915:
2874:
2650:
2644:
2618:
2489:
2063:
The worst-case input for the Pohlig–Hellman algorithm is a group of prime order: In that case, it degrades to the
2910:
2851:
2070:
1145:
1043:
1463:
1350:
2813:
2686:
2532:
2484:
826:
684:
2319:
2107:
2828:
2719:
1849:
1579:
1217:
741:
480:
286:
2939:
2889:
2869:
407:
1688:
1303:
2590:
2565:
2494:
975:
2949:
128:
2944:
2836:
2818:
2793:
2755:
2499:
2064:
1972:
969:
934:
678:
48:
789:
2954:
2920:
2841:
2745:
2704:
2699:
2676:
2580:
2019:
1421:
75:
2785:
2732:
2729:
2570:
2469:
44:
2526:
2519:
2402:
2391:
1839:{\displaystyle x\equiv x_{i}{\pmod {p_{i}^{e_{i}}}}\quad \forall i\in \{1,\dots ,r\}{\text{.}}}
372:
2905:
2861:
2575:
2552:
2406:
2375:
2349:"An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance"
2329:
1267:
336:
201:
2750:
2359:
1119:
254:
900:
2740:
2639:
2348:
2383:
2770:
2671:
2656:
2560:
2461:
2379:
2371:
2344:
2156:
1952:
1932:
1902:
1099:
1079:
1059:
1016:
972:
931:
786:
618:
457:
234:
181:
154:
108:
85:
63:
59:
52:
19:
2983:
2765:
2450:
1926:
105:(Note that for readability, the algorithm is stated for cyclic groups — in general,
2775:
2254:{\displaystyle {\mathcal {O}}\left(\sum _{i}{e_{i}(\log n+{\sqrt {p_{i}}})}\right)}
28:
79:
2419:
2104:. However, it is much more efficient if the order is smooth: Specifically, if
2363:
2453:
2398:
40:
1846:
The
Chinese remainder theorem guarantees there exists a unique solution
58:
The algorithm was introduced by Roland Silver, but first published by
2016:
can be understood as the projection to the factor group of order
82:. The basic idea of this algorithm is to iteratively compute the
2423:
930:
The algorithm computes discrete logarithms in time complexity
2182:
2076:
1925:
The correctness of this algorithm can be verified via the
615:. By construction, the order of this element must divide
2970:
indicate that algorithm is for numbers of special forms
1148:
2179:
2159:
2110:
2073:
2022:
1975:
1955:
1935:
1905:
1852:
1748:
1691:
1678:{\displaystyle x_{i}\in \{0,\dots ,p_{i}^{e_{i}}-1\}}
1615:
1582:
1533:
1466:
1424:
1353:
1306:
1270:
1220:
1122:
1102:
1082:
1062:
1046:(to combine these to a logarithm in the full group).
1019:
978:
937:
903:
829:
792:
744:
687:
641:
621:
536:
483:
460:
410:
375:
339:
289:
257:
237:
204:
184:
157:
131:
111:
88:
2898:
2860:
2827:
2784:
2728:
2685:
2589:
2551:
2460:
2390:
2253:
2165:
2145:
2096:
2047:
2008:
1961:
1941:
1911:
1888:
1838:
1729:
1677:
1601:
1565:
1519:
1449:
1406:
1336:
1289:
1256:
1200:
1134:
1108:
1088:
1068:
1025:
1004:
959:
916:
884:
811:
777:
730:
666:
627:
607:
519:
466:
442:
394:
358:
325:
269:
243:
223:
190:
163:
143:
117:
94:
667:{\displaystyle h_{k}\in \langle \gamma \rangle }
608:{\displaystyle h_{k}:=(g^{-x_{k}}h)^{p^{e-1-k}}}
2324:(2nd ed.). Chapman and Hall/CRC. p.
1566:{\displaystyle h_{i}\in \langle g_{i}\rangle }
2435:
2289:
8:
1883:
1859:
1828:
1810:
1672:
1629:
1596:
1583:
1560:
1547:
1331:
1313:
1251:
1227:
1201:{\textstyle n=\prod _{i=1}^{r}p_{i}^{e_{i}}}
725:
701:
661:
655:
514:
490:
320:
296:
138:
132:
2097:{\displaystyle {\mathcal {O}}({\sqrt {n}})}
2442:
2428:
2420:
2067:, hence the worst-case time complexity is
1520:{\displaystyle h_{i}:=h^{n/p_{i}^{e_{i}}}}
1407:{\displaystyle g_{i}:=g^{n/p_{i}^{e_{i}}}}
2234:
2228:
2207:
2202:
2196:
2181:
2180:
2178:
2158:
2135:
2130:
2125:
2115:
2109:
2084:
2075:
2074:
2072:
2037:
2032:
2027:
2021:
1998:
1993:
1988:
1979:
1974:
1954:
1934:
1904:
1851:
1831:
1788:
1783:
1778:
1765:
1759:
1747:
1721:
1706:
1701:
1696:
1690:
1658:
1653:
1648:
1620:
1614:
1590:
1581:
1554:
1538:
1532:
1507:
1502:
1497:
1488:
1484:
1471:
1465:
1439:
1434:
1429:
1423:
1394:
1389:
1384:
1375:
1371:
1358:
1352:
1305:
1275:
1269:
1219:
1190:
1185:
1180:
1170:
1159:
1147:
1121:
1101:
1081:
1061:
1018:
991:
985:
977:
947:
936:
908:
902:
885:{\displaystyle x_{k+1}:=x_{k}+p^{k}d_{k}}
876:
866:
853:
834:
828:
799:
791:
769:
754:
749:
743:
731:{\displaystyle d_{k}\in \{0,\dots ,p-1\}}
692:
686:
646:
640:
620:
585:
580:
565:
557:
541:
535:
482:
459:
426:
421:
409:
380:
374:
344:
338:
288:
256:
236:
215:
203:
183:
156:
130:
110:
87:
18:
2356:IEEE Transactions on Information Theory
2270:
2146:{\displaystyle \prod _{i}p_{i}^{e_{i}}}
1927:classification of finite abelian groups
1576:Using the algorithm above in the group
23:Steps of the Pohlig–Hellman algorithm.
2384:"Number-Theoretic Reference Problems"
2173:, then the algorithm's complexity is
1889:{\displaystyle x\in \{0,\dots ,n-1\}}
1602:{\displaystyle \langle g_{i}\rangle }
1257:{\displaystyle x\in \{0,\dots ,n-1\}}
778:{\displaystyle \gamma ^{d_{k}}=h_{k}}
520:{\displaystyle k\in \{0,\dots ,e-1\}}
326:{\displaystyle x\in \{0,\dots ,n-1\}}
7:
443:{\displaystyle \gamma :=g^{p^{e-1}}}
1773:
1730:{\displaystyle g_{i}^{x_{i}}=h_{i}}
1337:{\displaystyle i\in \{1,\dots ,r\}}
1801:
1742:Solve the simultaneous congruence
1005:{\displaystyle O({\sqrt {p^{e}}})}
16:Algorithm for computing logarithms
14:
2651:Special number field sieve (SNFS)
2645:General number field sieve (GNFS)
144:{\displaystyle \langle g\rangle }
125:must be replaced by the subgroup
2393:Handbook of Applied Cryptography
970:baby-step giant-step algorithm's
2321:An Introduction To Cryptography
2009:{\displaystyle n/p_{i}^{e_{i}}}
1800:
1766:
960:{\displaystyle O(e{\sqrt {p}})}
37:Silver–Pohlig–Hellman algorithm
2318:Mollin, Richard (2006-09-18).
2301:
2242:
2213:
2153:is the prime factorization of
2091:
2081:
2065:baby-step giant-step algorithm
1796:
1767:
999:
982:
954:
941:
812:{\displaystyle O({\sqrt {p}})}
806:
796:
679:baby-step giant-step algorithm
577:
550:
1:
2277:
2048:{\displaystyle p_{i}^{e_{i}}}
1450:{\displaystyle p_{i}^{e_{i}}}
2609:Lenstra elliptic curve (ECM)
1142:, and a prime factorization
35:, sometimes credited as the
2990:Number theoretic algorithms
171:, which is always cyclic.)
70:Groups of prime-power order
3006:
2916:Exponentiation by squaring
2599:Continued fraction (CFRAC)
2963:
2290:Pohlig & Hellman 1978
1418:, this element has order
1044:Chinese remainder theorem
454:, this element has order
395:{\displaystyle x_{0}:=0.}
2364:10.1109/TIT.1978.1055817
33:Pohlig–Hellman algorithm
2829:Greatest common divisor
1290:{\displaystyle g^{x}=h}
359:{\displaystyle g^{x}=h}
224:{\displaystyle n=p^{e}}
39:, is a special-purpose
2940:Modular exponentiation
2255:
2167:
2147:
2098:
2049:
2010:
1963:
1943:
1913:
1890:
1840:
1731:
1679:
1603:
1567:
1521:
1451:
1408:
1338:
1291:
1258:
1202:
1175:
1136:
1135:{\displaystyle h\in G}
1110:
1090:
1070:
1027:
1006:
968:, far better than the
961:
918:
886:
813:
779:
732:
668:
629:
609:
521:
468:
444:
396:
360:
327:
271:
270:{\displaystyle h\in G}
245:
225:
192:
165:
145:
119:
96:
24:
2667:Shanks's square forms
2591:Integer factorization
2566:Sieve of Eratosthenes
2376:van Oorschot, Paul C.
2256:
2168:
2148:
2099:
2050:
2011:
1964:
1944:
1914:
1891:
1841:
1732:
1680:
1604:
1568:
1522:
1452:
1409:
1339:
1292:
1259:
1203:
1155:
1137:
1111:
1091:
1071:
1037:The general algorithm
1028:
1007:
962:
919:
917:{\displaystyle x_{e}}
887:
814:
780:
733:
669:
630:
610:
522:
469:
445:
397:
361:
328:
272:
246:
226:
193:
166:
146:
120:
97:
22:
2945:Montgomery reduction
2819:Function field sieve
2794:Baby-step giant-step
2640:Quadratic sieve (QS)
2302:Menezes, et al. 1997
2177:
2157:
2108:
2071:
2020:
1973:
1953:
1933:
1903:
1850:
1746:
1689:
1613:
1580:
1531:
1464:
1422:
1351:
1304:
1268:
1218:
1146:
1120:
1100:
1080:
1060:
1017:
976:
935:
901:
827:
790:
742:
685:
639:
619:
534:
481:
458:
408:
373:
337:
287:
255:
235:
202:
182:
155:
129:
109:
86:
49:finite abelian group
2955:Trachtenberg system
2921:Integer square root
2862:Modular square root
2581:Wheel factorization
2533:Quadratic Frobenius
2513:Lucas–Lehmer–Riesel
2142:
2044:
2005:
1795:
1713:
1665:
1527:. By construction,
1514:
1446:
1401:
1214:The unique integer
1197:
283:The unique integer
45:discrete logarithms
2847:Extended Euclidean
2786:Discrete logarithm
2715:Schönhage–Strassen
2571:Sieve of Pritchard
2380:Vanstone, Scott A.
2372:Menezes, Alfred J.
2261:group operations.
2251:
2201:
2163:
2143:
2121:
2120:
2094:
2045:
2023:
2006:
1984:
1959:
1939:
1909:
1886:
1836:
1774:
1727:
1692:
1675:
1644:
1599:
1563:
1517:
1493:
1447:
1425:
1416:Lagrange's theorem
1404:
1380:
1334:
1287:
1254:
1198:
1176:
1132:
1106:
1086:
1066:
1023:
1002:
957:
914:
882:
809:
775:
728:
664:
625:
605:
517:
464:
452:Lagrange's theorem
440:
392:
356:
323:
267:
241:
221:
188:
161:
141:
115:
92:
25:
2977:
2976:
2576:Sieve of Sundaram
2335:978-1-58488-618-1
2240:
2192:
2166:{\displaystyle n}
2111:
2089:
1962:{\displaystyle h}
1942:{\displaystyle g}
1912:{\displaystyle x}
1834:
1109:{\displaystyle g}
1089:{\displaystyle n}
1069:{\displaystyle G}
1026:{\displaystyle e}
997:
952:
804:
628:{\displaystyle p}
467:{\displaystyle p}
244:{\displaystyle g}
191:{\displaystyle G}
164:{\displaystyle g}
118:{\displaystyle G}
95:{\displaystyle p}
78:whose order is a
51:whose order is a
2997:
2926:Integer relation
2899:Other algorithms
2804:Pollard kangaroo
2695:Ancient Egyptian
2553:Prime-generating
2538:Solovay–Strassen
2451:Number-theoretic
2444:
2437:
2430:
2421:
2416:
2396:
2388:
2367:
2353:
2339:
2305:
2299:
2293:
2287:
2281:
2275:
2260:
2258:
2257:
2252:
2250:
2246:
2245:
2241:
2239:
2238:
2229:
2212:
2211:
2200:
2186:
2185:
2172:
2170:
2169:
2164:
2152:
2150:
2149:
2144:
2141:
2140:
2139:
2129:
2119:
2103:
2101:
2100:
2095:
2090:
2085:
2080:
2079:
2054:
2052:
2051:
2046:
2043:
2042:
2041:
2031:
2015:
2013:
2012:
2007:
2004:
2003:
2002:
1992:
1983:
1969:to the power of
1968:
1966:
1965:
1960:
1948:
1946:
1945:
1940:
1918:
1916:
1915:
1910:
1895:
1893:
1892:
1887:
1845:
1843:
1842:
1837:
1835:
1832:
1799:
1794:
1793:
1792:
1782:
1764:
1763:
1736:
1734:
1733:
1728:
1726:
1725:
1712:
1711:
1710:
1700:
1684:
1682:
1681:
1676:
1664:
1663:
1662:
1652:
1625:
1624:
1608:
1606:
1605:
1600:
1595:
1594:
1572:
1570:
1569:
1564:
1559:
1558:
1543:
1542:
1526:
1524:
1523:
1518:
1516:
1515:
1513:
1512:
1511:
1501:
1492:
1476:
1475:
1456:
1454:
1453:
1448:
1445:
1444:
1443:
1433:
1413:
1411:
1410:
1405:
1403:
1402:
1400:
1399:
1398:
1388:
1379:
1363:
1362:
1343:
1341:
1340:
1335:
1296:
1294:
1293:
1288:
1280:
1279:
1263:
1261:
1260:
1255:
1207:
1205:
1204:
1199:
1196:
1195:
1194:
1184:
1174:
1169:
1141:
1139:
1138:
1133:
1115:
1113:
1112:
1107:
1095:
1093:
1092:
1087:
1075:
1073:
1072:
1067:
1032:
1030:
1029:
1024:
1011:
1009:
1008:
1003:
998:
996:
995:
986:
966:
964:
963:
958:
953:
948:
923:
921:
920:
915:
913:
912:
891:
889:
888:
883:
881:
880:
871:
870:
858:
857:
845:
844:
818:
816:
815:
810:
805:
800:
785:. It takes time
784:
782:
781:
776:
774:
773:
761:
760:
759:
758:
737:
735:
734:
729:
697:
696:
673:
671:
670:
665:
651:
650:
634:
632:
631:
626:
614:
612:
611:
606:
604:
603:
602:
601:
572:
571:
570:
569:
546:
545:
526:
524:
523:
518:
473:
471:
470:
465:
449:
447:
446:
441:
439:
438:
437:
436:
401:
399:
398:
393:
385:
384:
365:
363:
362:
357:
349:
348:
332:
330:
329:
324:
276:
274:
273:
268:
250:
248:
247:
242:
230:
228:
227:
222:
220:
219:
197:
195:
194:
189:
170:
168:
167:
162:
150:
148:
147:
142:
124:
122:
121:
116:
101:
99:
98:
93:
3005:
3004:
3000:
2999:
2998:
2996:
2995:
2994:
2980:
2979:
2978:
2973:
2959:
2894:
2856:
2823:
2780:
2724:
2681:
2585:
2547:
2520:Proth's theorem
2462:Primality tests
2456:
2448:
2413:
2386:
2370:
2358:(24): 106–110.
2351:
2342:
2336:
2317:
2314:
2309:
2308:
2300:
2296:
2288:
2284:
2276:
2272:
2267:
2230:
2203:
2191:
2187:
2175:
2174:
2155:
2154:
2131:
2106:
2105:
2069:
2068:
2061:
2033:
2018:
2017:
1994:
1971:
1970:
1951:
1950:
1931:
1930:
1901:
1900:
1848:
1847:
1784:
1755:
1744:
1743:
1717:
1702:
1687:
1686:
1654:
1616:
1611:
1610:
1586:
1578:
1577:
1550:
1534:
1529:
1528:
1503:
1480:
1467:
1462:
1461:
1435:
1420:
1419:
1390:
1367:
1354:
1349:
1348:
1302:
1301:
1271:
1266:
1265:
1216:
1215:
1186:
1144:
1143:
1118:
1117:
1098:
1097:
1096:with generator
1078:
1077:
1058:
1057:
1056:A cyclic group
1039:
1015:
1014:
987:
974:
973:
933:
932:
904:
899:
898:
872:
862:
849:
830:
825:
824:
788:
787:
765:
750:
745:
740:
739:
688:
683:
682:
642:
637:
636:
617:
616:
581:
576:
561:
553:
537:
532:
531:
479:
478:
456:
455:
422:
417:
406:
405:
376:
371:
370:
340:
335:
334:
285:
284:
253:
252:
251:and an element
233:
232:
231:with generator
211:
200:
199:
180:
179:
178:A cyclic group
153:
152:
127:
126:
107:
106:
84:
83:
72:
17:
12:
11:
5:
3003:
3001:
2993:
2992:
2982:
2981:
2975:
2974:
2972:
2971:
2964:
2961:
2960:
2958:
2957:
2952:
2947:
2942:
2937:
2923:
2918:
2913:
2908:
2902:
2900:
2896:
2895:
2893:
2892:
2887:
2882:
2880:Tonelli–Shanks
2877:
2872:
2866:
2864:
2858:
2857:
2855:
2854:
2849:
2844:
2839:
2833:
2831:
2825:
2824:
2822:
2821:
2816:
2814:Index calculus
2811:
2809:Pohlig–Hellman
2806:
2801:
2796:
2790:
2788:
2782:
2781:
2779:
2778:
2773:
2768:
2763:
2761:Newton-Raphson
2758:
2753:
2748:
2743:
2737:
2735:
2726:
2725:
2723:
2722:
2717:
2712:
2707:
2702:
2697:
2691:
2689:
2687:Multiplication
2683:
2682:
2680:
2679:
2674:
2672:Trial division
2669:
2664:
2659:
2657:Rational sieve
2654:
2647:
2642:
2637:
2629:
2621:
2616:
2611:
2606:
2601:
2595:
2593:
2587:
2586:
2584:
2583:
2578:
2573:
2568:
2563:
2561:Sieve of Atkin
2557:
2555:
2549:
2548:
2546:
2545:
2540:
2535:
2530:
2523:
2516:
2509:
2502:
2497:
2492:
2487:
2485:Elliptic curve
2482:
2477:
2472:
2466:
2464:
2458:
2457:
2449:
2447:
2446:
2439:
2432:
2424:
2418:
2417:
2411:
2368:
2340:
2334:
2313:
2310:
2307:
2306:
2294:
2282:
2269:
2268:
2266:
2263:
2249:
2244:
2237:
2233:
2227:
2224:
2221:
2218:
2215:
2210:
2206:
2199:
2195:
2190:
2184:
2162:
2138:
2134:
2128:
2124:
2118:
2114:
2093:
2088:
2083:
2078:
2060:
2057:
2040:
2036:
2030:
2026:
2001:
1997:
1991:
1987:
1982:
1978:
1958:
1938:
1923:
1922:
1921:
1920:
1908:
1897:
1885:
1882:
1879:
1876:
1873:
1870:
1867:
1864:
1861:
1858:
1855:
1830:
1827:
1824:
1821:
1818:
1815:
1812:
1809:
1806:
1803:
1798:
1791:
1787:
1781:
1777:
1772:
1769:
1762:
1758:
1754:
1751:
1740:
1739:
1738:
1724:
1720:
1716:
1709:
1705:
1699:
1695:
1674:
1671:
1668:
1661:
1657:
1651:
1647:
1643:
1640:
1637:
1634:
1631:
1628:
1623:
1619:
1598:
1593:
1589:
1585:
1574:
1562:
1557:
1553:
1549:
1546:
1541:
1537:
1510:
1506:
1500:
1496:
1491:
1487:
1483:
1479:
1474:
1470:
1458:
1442:
1438:
1432:
1428:
1397:
1393:
1387:
1383:
1378:
1374:
1370:
1366:
1361:
1357:
1333:
1330:
1327:
1324:
1321:
1318:
1315:
1312:
1309:
1286:
1283:
1278:
1274:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1209:
1193:
1189:
1183:
1179:
1173:
1168:
1165:
1162:
1158:
1154:
1151:
1131:
1128:
1125:
1105:
1085:
1065:
1038:
1035:
1022:
1001:
994:
990:
984:
981:
956:
951:
946:
943:
940:
928:
927:
926:
925:
911:
907:
895:
894:
893:
879:
875:
869:
865:
861:
856:
852:
848:
843:
840:
837:
833:
821:
808:
803:
798:
795:
772:
768:
764:
757:
753:
748:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
695:
691:
675:
663:
660:
657:
654:
649:
645:
624:
600:
597:
594:
591:
588:
584:
579:
575:
568:
564:
560:
556:
552:
549:
544:
540:
516:
513:
510:
507:
504:
501:
498:
495:
492:
489:
486:
475:
463:
435:
432:
429:
425:
420:
416:
413:
402:
391:
388:
383:
379:
355:
352:
347:
343:
322:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
278:
266:
263:
260:
240:
218:
214:
210:
207:
187:
160:
140:
137:
134:
114:
91:
71:
68:
64:Martin Hellman
60:Stephen Pohlig
53:smooth integer
43:for computing
15:
13:
10:
9:
6:
4:
3:
2:
3002:
2991:
2988:
2987:
2985:
2969:
2966:
2965:
2962:
2956:
2953:
2951:
2948:
2946:
2943:
2941:
2938:
2935:
2931:
2927:
2924:
2922:
2919:
2917:
2914:
2912:
2909:
2907:
2904:
2903:
2901:
2897:
2891:
2888:
2886:
2883:
2881:
2878:
2876:
2875:Pocklington's
2873:
2871:
2868:
2867:
2865:
2863:
2859:
2853:
2850:
2848:
2845:
2843:
2840:
2838:
2835:
2834:
2832:
2830:
2826:
2820:
2817:
2815:
2812:
2810:
2807:
2805:
2802:
2800:
2797:
2795:
2792:
2791:
2789:
2787:
2783:
2777:
2774:
2772:
2769:
2767:
2764:
2762:
2759:
2757:
2754:
2752:
2749:
2747:
2744:
2742:
2739:
2738:
2736:
2734:
2731:
2727:
2721:
2718:
2716:
2713:
2711:
2708:
2706:
2703:
2701:
2698:
2696:
2693:
2692:
2690:
2688:
2684:
2678:
2675:
2673:
2670:
2668:
2665:
2663:
2660:
2658:
2655:
2653:
2652:
2648:
2646:
2643:
2641:
2638:
2636:
2634:
2630:
2628:
2626:
2622:
2620:
2619:Pollard's rho
2617:
2615:
2612:
2610:
2607:
2605:
2602:
2600:
2597:
2596:
2594:
2592:
2588:
2582:
2579:
2577:
2574:
2572:
2569:
2567:
2564:
2562:
2559:
2558:
2556:
2554:
2550:
2544:
2541:
2539:
2536:
2534:
2531:
2529:
2528:
2524:
2522:
2521:
2517:
2515:
2514:
2510:
2508:
2507:
2503:
2501:
2498:
2496:
2493:
2491:
2488:
2486:
2483:
2481:
2478:
2476:
2473:
2471:
2468:
2467:
2465:
2463:
2459:
2455:
2452:
2445:
2440:
2438:
2433:
2431:
2426:
2425:
2422:
2414:
2412:0-8493-8523-7
2408:
2404:
2400:
2395:
2394:
2385:
2381:
2377:
2373:
2369:
2365:
2361:
2357:
2350:
2346:
2341:
2337:
2331:
2327:
2323:
2322:
2316:
2315:
2311:
2303:
2298:
2295:
2291:
2286:
2283:
2279:
2274:
2271:
2264:
2262:
2247:
2235:
2231:
2225:
2222:
2219:
2216:
2208:
2204:
2197:
2193:
2188:
2160:
2136:
2132:
2126:
2122:
2116:
2112:
2086:
2066:
2058:
2056:
2038:
2034:
2028:
2024:
1999:
1995:
1989:
1985:
1980:
1976:
1956:
1936:
1928:
1906:
1898:
1880:
1877:
1874:
1871:
1868:
1865:
1862:
1856:
1853:
1825:
1822:
1819:
1816:
1813:
1807:
1804:
1789:
1785:
1779:
1775:
1770:
1760:
1756:
1752:
1749:
1741:
1722:
1718:
1714:
1707:
1703:
1697:
1693:
1669:
1666:
1659:
1655:
1649:
1645:
1641:
1638:
1635:
1632:
1626:
1621:
1617:
1591:
1587:
1575:
1555:
1551:
1544:
1539:
1535:
1508:
1504:
1498:
1494:
1489:
1485:
1481:
1477:
1472:
1468:
1459:
1440:
1436:
1430:
1426:
1417:
1395:
1391:
1385:
1381:
1376:
1372:
1368:
1364:
1359:
1355:
1346:
1345:
1328:
1325:
1322:
1319:
1316:
1310:
1307:
1299:
1298:
1284:
1281:
1276:
1272:
1248:
1245:
1242:
1239:
1236:
1233:
1230:
1224:
1221:
1213:
1210:
1191:
1187:
1181:
1177:
1171:
1166:
1163:
1160:
1156:
1152:
1149:
1129:
1126:
1123:
1116:, an element
1103:
1083:
1063:
1055:
1052:
1051:
1050:
1047:
1045:
1036:
1034:
1020:
1012:
992:
988:
979:
971:
967:
949:
944:
938:
909:
905:
896:
877:
873:
867:
863:
859:
854:
850:
846:
841:
838:
835:
831:
822:
819:
801:
793:
770:
766:
762:
755:
751:
746:
722:
719:
716:
713:
710:
707:
704:
698:
693:
689:
680:
676:
658:
652:
647:
643:
622:
598:
595:
592:
589:
586:
582:
573:
566:
562:
558:
554:
547:
542:
538:
529:
528:
511:
508:
505:
502:
499:
496:
493:
487:
484:
476:
461:
453:
433:
430:
427:
423:
418:
414:
411:
403:
389:
386:
381:
377:
368:
367:
353:
350:
345:
341:
317:
314:
311:
308:
305:
302:
299:
293:
290:
282:
279:
264:
261:
258:
238:
216:
212:
208:
205:
185:
177:
174:
173:
172:
158:
151:generated by
135:
112:
103:
89:
81:
77:
69:
67:
65:
61:
56:
54:
50:
46:
42:
38:
34:
30:
21:
2967:
2808:
2649:
2632:
2624:
2543:Miller–Rabin
2525:
2518:
2511:
2506:Lucas–Lehmer
2504:
2392:
2355:
2343:Pohlig, S.;
2320:
2297:
2285:
2273:
2062:
1924:
1211:
1053:
1048:
1040:
929:
280:
175:
104:
73:
57:
36:
32:
29:group theory
26:
2799:Pollard rho
2756:Goldschmidt
2490:Pocklington
2480:Baillie–PSW
2401:. pp.
2345:Hellman, M.
2278:Mollin 2006
369:Initialize
80:prime power
2911:Cornacchia
2906:Chakravala
2454:algorithms
2312:References
2059:Complexity
1929:: Raising
1685:such that
1609:, compute
1264:such that
1033:is large.
738:such that
681:, compute
677:Using the
333:such that
2885:Berlekamp
2842:Euclidean
2730:Euclidean
2710:Toom–Cook
2705:Karatsuba
2399:CRC Press
2304:, pg. 108
2280:, pg. 344
2220:
2194:∑
2113:∏
1878:−
1869:…
1857:∈
1820:…
1808:∈
1802:∀
1753:≡
1667:−
1639:…
1627:∈
1597:⟩
1584:⟨
1561:⟩
1548:⟨
1545:∈
1323:…
1311:∈
1300:For each
1246:−
1237:…
1225:∈
1157:∏
1127:∈
1076:of order
747:γ
720:−
711:…
699:∈
662:⟩
659:γ
656:⟨
653:∈
596:−
590:−
559:−
509:−
500:…
488:∈
431:−
412:γ
315:−
306:…
294:∈
262:∈
198:of order
139:⟩
133:⟨
41:algorithm
2984:Category
2852:Lehmer's
2746:Chunking
2733:division
2662:Fermat's
2382:(1997).
2347:(1978).
1460:Compute
1347:Compute
635:, hence
530:Compute
477:For all
404:Compute
2968:Italics
2890:Kunerth
2870:Cipolla
2751:Fourier
2720:Fürer's
2614:Euler's
2604:Dixon's
2527:Pépin's
2403:107–109
1899:Return
1212:Output.
897:Return
281:Output.
2950:Schoof
2837:Binary
2741:Binary
2677:Shor's
2495:Fermat
2409:
2332:
1344:, do:
1054:Input.
527:, do:
176:Input.
76:groups
31:, the
2771:Short
2500:Lucas
2387:(PDF)
2352:(PDF)
2265:Notes
1414:. By
1013:when
450:. By
47:in a
2766:Long
2700:Long
2407:ISBN
2330:ISBN
1949:and
823:Set
62:and
2930:LLL
2776:SRT
2635:+ 1
2627:− 1
2475:APR
2470:AKS
2360:doi
2326:344
2217:log
1771:mod
27:In
2986::
2934:KZ
2932:;
2405:.
2397:.
2389:.
2378:;
2374:;
2354:.
2328:.
2055:.
1478::=
1365::=
1297:.
847::=
548::=
415::=
390:0.
387::=
366:.
55:.
2936:)
2928:(
2633:p
2625:p
2443:e
2436:t
2429:v
2415:.
2366:.
2362::
2338:.
2292:.
2248:)
2243:)
2236:i
2232:p
2226:+
2223:n
2214:(
2209:i
2205:e
2198:i
2189:(
2183:O
2161:n
2137:i
2133:e
2127:i
2123:p
2117:i
2092:)
2087:n
2082:(
2077:O
2039:i
2035:e
2029:i
2025:p
2000:i
1996:e
1990:i
1986:p
1981:/
1977:n
1957:h
1937:g
1919:.
1907:x
1896:.
1884:}
1881:1
1875:n
1872:,
1866:,
1863:0
1860:{
1854:x
1833:.
1829:}
1826:r
1823:,
1817:,
1814:1
1811:{
1805:i
1797:)
1790:i
1786:e
1780:i
1776:p
1768:(
1761:i
1757:x
1750:x
1737:.
1723:i
1719:h
1715:=
1708:i
1704:x
1698:i
1694:g
1673:}
1670:1
1660:i
1656:e
1650:i
1646:p
1642:,
1636:,
1633:0
1630:{
1622:i
1618:x
1592:i
1588:g
1573:.
1556:i
1552:g
1540:i
1536:h
1509:i
1505:e
1499:i
1495:p
1490:/
1486:n
1482:h
1473:i
1469:h
1457:.
1441:i
1437:e
1431:i
1427:p
1396:i
1392:e
1386:i
1382:p
1377:/
1373:n
1369:g
1360:i
1356:g
1332:}
1329:r
1326:,
1320:,
1317:1
1314:{
1308:i
1285:h
1282:=
1277:x
1273:g
1252:}
1249:1
1243:n
1240:,
1234:,
1231:0
1228:{
1222:x
1208:.
1192:i
1188:e
1182:i
1178:p
1172:r
1167:1
1164:=
1161:i
1153:=
1150:n
1130:G
1124:h
1104:g
1084:n
1064:G
1021:e
1000:)
993:e
989:p
983:(
980:O
955:)
950:p
945:e
942:(
939:O
924:.
910:e
906:x
892:.
878:k
874:d
868:k
864:p
860:+
855:k
851:x
842:1
839:+
836:k
832:x
820:.
807:)
802:p
797:(
794:O
771:k
767:h
763:=
756:k
752:d
726:}
723:1
717:p
714:,
708:,
705:0
702:{
694:k
690:d
674:.
648:k
644:h
623:p
599:k
593:1
587:e
583:p
578:)
574:h
567:k
563:x
555:g
551:(
543:k
539:h
515:}
512:1
506:e
503:,
497:,
494:0
491:{
485:k
474:.
462:p
434:1
428:e
424:p
419:g
382:0
378:x
354:h
351:=
346:x
342:g
321:}
318:1
312:n
309:,
303:,
300:0
297:{
291:x
277:.
265:G
259:h
239:g
217:e
213:p
209:=
206:n
186:G
159:g
136:g
113:G
90:p
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
