186:
Discrete logarithms are quickly computable in a few special cases. However, no efficient method is known for computing them in general. In cryptography, the computational complexity of the discrete logarithm problem, along with its application, was first proposed in the
328:
2428:
536: 53 = 1.724276⊠means that 10 = 53. While integer exponents can be defined in any group using products and inverses, arbitrary real exponents, such as this 1.724276âŠ, require other concepts such as the
504:
1190:
1086:
3007:
1545:
The authors of the Logjam attack estimate that the much more difficult precomputation needed to solve the discrete log problem for a 1024-bit prime would be within the budget of a large national
997:
1527:
these three steps for a specific group, one need only carry out the last step, which is much less computationally expensive than the first three, to obtain a specific logarithm in that group.
2432:
841:
1940:
1222:
The discrete logarithm problem is considered to be computationally intractable. That is, no efficient classical algorithm is known for computing discrete logarithms in general.
2790:
1554:
532:
Other base-10 logarithms in the real numbers are not instances of the discrete logarithm problem, because they involve non-integer exponents. For example, the equation log
2500:
3000:
1973:
3240:
2918:
1216:
257:
2913:
1538:
attack used this vulnerability to compromise a variety of internet services that allowed the use of groups whose order was a 512-bit prime number, so called
3091:
3235:
3055:
2993:
1534:
traffic uses one of a handful of groups that are of order 1024 bits or less, e.g. cyclic groups with order of the Oakley primes specified in RFC 2409. The
2642:
1461:, for example). This asymmetry is analogous to the one between integer factorization and integer multiplication. Both asymmetries (and other possibly
2297:
1933:
1782:; Springall, Drew; Thomé, Emmanuel; Valenta, Luke; VanderSloot, Benjamin; Wustrow, Eric; Zanella-Béguelin, Santiago; Zimmermann, Paul (October 2015).
1318:
644:
3086:
2821:
2815:
721:
The discrete logarithm is just the inverse operation. For example, consider the equation 3 ⥠13 (mod 17). From the example above, one solution is
741:
satisfying 3 ⥠1 (mod 17), these are the only solutions. Equivalently, the set of all possible solutions can be expressed by the constraint that
1437:
There exist groups for which computing discrete logarithms is apparently difficult. In some cases (e.g. large prime order subgroups of groups
2165:
2939:
2493:
1909:
1655:
673:, and the group product of two elements may be obtained by ordinary integer multiplication of the elements followed by reduction modulo
2107:
1926:
2036:
2213:
2557:
1844:
2625:
2582:
2547:
3016:
2011:
1285:
of the size of the group, and thus exponential in half the number of digits in the size of the group. However, none of them runs in
204:
2537:
438:
2122:
1270:
in the number of digits in the size of the group. Therefore, it is an exponential-time algorithm, practical only for small groups
2486:
2160:
2097:
2615:
2562:
2041:
2004:
1486:
1369:
2701:
2302:
2193:
2112:
2102:
1511:
While there is no publicly known algorithm for solving the discrete logarithm problem in general, the first three steps of the
1323:
1978:
711:. To compute 3 in this group, compute 3 = 81, and then divide 81 by 17, obtaining a remainder of 13. Thus 3 = 13 in the group
3163:
2726:
2130:
2610:
2383:
1121:
1040:
3050:
1376:
is used, allowing an efficient computation of the discrete logarithm with PohligâHellman if the order of the group (being
733:
is an integer then 3 ⥠3 à (3) ⥠13 à 1 ⥠13 (mod 17). Hence the equation has infinitely many solutions of the form 4 + 16
2378:
2307:
2208:
1313:
2867:
2800:
2345:
1679:
Shor, Peter (1997). "Polynomial-Time
Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer".
1457:
At the same time, the inverse problem of discrete exponentiation is not difficult (it can be computed efficiently using
1358:
958:
2542:
2259:
3210:
3179:
2964:
2857:
2706:
2620:
2605:
1505:
1490:
3081:
1341:
Efficient classical algorithms also exist in certain special cases. For example, in the group of the integers modulo
188:
3117:
3060:
2716:
2587:
2424:
2414:
2373:
2149:
2143:
2117:
1988:
1535:
1512:
1458:
1308:
1201:
726:
3158:
2969:
2949:
2409:
2350:
1553:(NSA). The Logjam authors speculate that precomputation against widely reused 1024 DH primes is behind claims in
1396:
While computing discrete logarithms and integer factorization are distinct problems, they share some properties:
881:
2908:
2679:
2312:
2185:
2031:
1983:
1778:
Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex;
1550:
1451:
1303:
812:
1624:
Lam; Shparlinski; Wang; Xing (2001). Lam, Kwok-Yan; Shparlinski, Igor; Wang, Huaxiong; Xing, Chaoping (eds.).
3184:
2862:
2509:
2327:
2218:
1447:
1401:
196:
172:
164:
700:
multiple times during the computation. Regardless of the specific algorithm used, this operation is called
3230:
2944:
2795:
2734:
2669:
2438:
2388:
2368:
1539:
804:
701:
3220:
3215:
3045:
3035:
3030:
2810:
2567:
2524:
2089:
2064:
1993:
1566:
1278:
2448:
1631:
3153:
2721:
2532:
2443:
2335:
2317:
2292:
2254:
1998:
1405:
1298:
1293:
537:
200:
3225:
2827:
2453:
2419:
2340:
2244:
2203:
2198:
2175:
2079:
1546:
1331:
63:
207:
that the discrete logarithm problem (DLP) over carefully chosen groups has no efficient solution.
2674:
2577:
2572:
2552:
2231:
2228:
2069:
1968:
1714:
1688:
1643:
1482:
1028:
859:
666:
655:
141:
2025:
2018:
2934:
2877:
2805:
2691:
2404:
2360:
2074:
2051:
1905:
1840:
1817:
1755:
1661:
1651:
950:
3112:
2780:
2249:
1881:
1809:
1745:
1698:
1635:
1462:
1412:
1267:
1011:
907:
224:
1710:
1625:
3147:
3143:
3137:
3133:
2239:
2138:
1706:
1575:
1286:
544:
220:
1281:. These algorithms run faster than the naĂŻve algorithm, some of them proportional to the
323:{\displaystyle b^{k}=\underbrace {b\cdot b\cdot \ldots \cdot b} _{k\;{\text{factors}}}.}
3189:
3107:
2269:
2170:
2155:
2059:
1960:
1885:
1779:
1494:
936:
685:
1855:
725: = 4, but it is not the only solution. Since 3 ⥠1 (mod 17)âas follows from
3204:
2985:
2264:
1949:
1571:
1425:
1381:
109:
2974:
2954:
2274:
1783:
1718:
1524:
1498:
1385:
1256:
1007:
659:
555:
548:
1213:
Can the discrete logarithm be computed in polynomial time on a classical computer?
1740:. Festschrift for Harald Niederreiter, Special Issue on Coding and Cryptography.
3040:
2872:
2749:
1596:
1282:
1277:
More sophisticated algorithms exist, usually inspired by similar algorithms for
1259:
429:
24:
20:
2898:
2630:
1918:
1750:
1733:
1702:
1639:
1411:
both problems seem to be difficult (no efficient algorithms are known for non-
1335:
867:
1821:
1759:
1665:
1647:
1446:) there is not only no efficient algorithm known for the worst case, but the
696:. When the numbers involved are large, it is more efficient to reduce modulo
1952:
1901:
1607:
1205:
192:
35:
1107:
The familiar base change formula for ordinary logarithms remains valid: If
2478:
529: 0.001 = â3. These are instances of the discrete logarithm problem.
2959:
2893:
2764:
2759:
2754:
2635:
1801:
1734:"On the complexity of the discrete logarithm and DiffieâHellman problems"
1693:
1531:
871:
587:
692:
th power as an integer and then finding the remainder after division by
2785:
2744:
74:
1418:
for both problems efficient algorithms on quantum computers are known,
2903:
1813:
1465:) have been exploited in the construction of cryptographic systems.
1424:
the difficulty of both problems has been used to construct various
688:
of one of the numbers in this group may be computed by finding its
2739:
2696:
2664:
2657:
2652:
2647:
643:
One of the simplest settings for discrete logarithms is the group
1784:"Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice"
2989:
2482:
1922:
1630:. Progress in Computer Science and Applied Logic (1 ed.).
1472:
in discrete logarithm cryptography (DLC) are the cyclic groups
1421:
algorithms from one problem are often adapted to the other, and
2832:
2686:
499:{\displaystyle \ldots ,0.001,0.01,0.1,1,10,100,1000,\ldots .}
1034:, and the discrete logarithm amounts to a group isomorphism
1450:
can be shown to be about as hard as the worst case using
1557:
that NSA is able to break much of current cryptography.
949:
is also unique, and the discrete logarithm amounts to a
737:. Moreover, because 16 is the smallest positive integer
16:
The problem of inverting exponentiation in finite groups
2469:
indicate that algorithm is for numbers of special forms
1185:{\displaystyle \log _{c}a=\log _{c}b\cdot \log _{b}a.}
1081:{\displaystyle \log _{b}\colon H\to \mathbf {Z} _{n},}
1595:
Menezes, A. J.; van
Oorschot, P. C.; Vanstone, S. A.
1124:
1043:
961:
815:
582:
A similar example holds for any non-zero real number
441:
260:
1289:(in the number of digits in the size of the group).
3172:
3126:
3100:
3069:
3023:
2927:
2886:
2845:
2773:
2715:
2596:
2523:
2516:
2397:
2359:
2326:
2283:
2227:
2184:
2088:
2050:
1959:
617:, âŠ} of the non-zero real numbers. For any element
1184:
1080:
992:{\displaystyle \log _{b}\colon H\to \mathbf {Z} .}
991:
835:
498:
322:
1732:Blake, Ian F.; Garefalakis, Theo (2004-04-01).
1100:denotes the additive group of integers modulo
3001:
2494:
1934:
1773:
1771:
1769:
1251:is found. This algorithm is sometimes called
8:
1837:Elementary Number Theory and Its Application
1627:Cryptography and Computational Number Theory
1217:(more unsolved problems in computer science)
1597:"Chapter 8.4 ElGamal public-key encryption"
3008:
2994:
2986:
2520:
2501:
2487:
2479:
1941:
1927:
1919:
1890:Prime Numbers: A computational perspective
558:for this group. The discrete logarithm log
309:
1800:Harkins, D.; Carrel, D. (November 1998).
1749:
1692:
1167:
1148:
1129:
1123:
1069:
1064:
1048:
1042:
981:
966:
960:
836:{\displaystyle f\colon \mathbf {Z} \to G}
822:
814:
791:Powers obey the usual algebraic identity
440:
310:
305:
275:
265:
259:
1587:
1353:, and equality means congruence modulo
757:is the identity element 1 of the group
1319:Pollard's rho algorithm for logarithms
654:. This is the group of multiplication
3241:Unsolved problems in computer science
1392:Comparison with integer factorization
1225:A general algorithm for computing log
7:
2822:NaccacheâStern knapsack cryptosystem
1839:(6 ed.). Pearson. p. 368.
1619:
1617:
1208:Unsolved problem in computer science
1515:algorithm only depend on the group
586:. The powers form a multiplicative
3236:Computational hardness assumptions
3017:Computational hardness assumptions
1519:, not on the specific elements of
554:under multiplication, and 10 is a
14:
3076:
2852:
2150:Special number field sieve (SNFS)
2144:General number field sieve (GNFS)
1898:Cryptography: Theory and Practice
1802:"The Internet Key Exchange (IKE)"
513:in this list, one can compute log
112:, the more commonly used term is
3056:Decisional composite residuosity
1896:Stinson, Douglas Robert (2006).
1604:Handbook of Applied Cryptography
1523:whose finite log is desired. By
1372:, a cyclic group modulo a prime
1326:(aka Pollard's lambda algorithm)
1065:
982:
823:
775:other than 1, and every integer
2853:Discrete logarithm cryptography
547:terms, the powers of 10 form a
1468:Popular choices for the group
1400:both are special cases of the
1060:
978:
827:
1:
578:Powers of a fixed real number
203:, base their security on the
3092:Computational DiffieâHellman
2868:Non-commutative cryptography
2108:Lenstra elliptic curve (ECM)
1359:extended Euclidean algorithm
1324:Pollard's kangaroo algorithm
1243:to larger and larger powers
779:is a discrete logarithm for
761:, the discrete logarithm log
665:. Its elements are non-zero
3180:Exponential time hypothesis
2965:Identity-based cryptography
2858:Elliptic-curve cryptography
1506:Elliptic curve cryptography
1491:Digital Signature Algorithm
1487:DiffieâHellman key exchange
235:. For any positive integer
3257:
2415:Exponentiation by squaring
2098:Continued fraction (CFRAC)
1900:(3 ed.). London, UK:
1835:Rosen, Kenneth H. (2011).
1493:) and cyclic subgroups of
1459:exponentiation by squaring
1345:under addition, the power
1202:Discrete logarithm records
1199:
753:In the special case where
353:th power is the identity:
223:by multiplication and its
3190:Planted clique conjecture
3159:Ring learning with errors
3087:Decisional DiffieâHellman
2970:Post-quantum cryptography
2919:Post-Quantum Cryptography
2462:
1751:10.1016/j.jco.2004.01.002
1703:10.1137/s0097539795293172
1681:SIAM Journal on Computing
1640:10.1007/978-3-0348-8295-8
1262:in the size of the group
729:âit also follows that if
525: 10000 = 4, and log
375:that solves the equation
219:be any group. Denote its
1551:National Security Agency
1452:random self-reducibility
1314:PohligâHellman algorithm
1304:Index calculus algorithm
1111:is another generator of
704:. For example, consider
3185:Unique games conjecture
3134:Shortest vector problem
3108:External DiffieâHellman
2863:Hash-based cryptography
2510:Public-key cryptography
2328:Greatest common divisor
1530:It turns out that much
1448:average-case complexity
1402:hidden subgroup problem
727:Fermat's little theorem
243:denotes the product of
197:public-key cryptography
73:can be defined for all
3164:Short integer solution
3144:Closest vector problem
2439:Modular exponentiation
1330:There is an efficient
1186:
1082:
1002:On the other hand, if
993:
837:
803:. In other words, the
749:Powers of the identity
702:modular exponentiation
500:
393:, in this context) of
367:also be an element of
337:denote the product of
324:
189:DiffieâHellman problem
133:) (read "the index of
62:. Analogously, in any
3051:Quadratic residuosity
3031:Integer factorization
2525:Integer factorization
2166:Shanks's square forms
2090:Integer factorization
2065:Sieve of Eratosthenes
1806:Network Working Group
1738:Journal of Complexity
1567:A. W. Faber Model 366
1406:finite abelian groups
1357:in the integers. The
1279:integer factorization
1187:
1083:
1027:is unique only up to
994:
838:
625:, one can compute log
501:
325:
3154:Learning with errors
2444:Montgomery reduction
2318:Function field sieve
2293:Baby-step giant-step
2139:Quadratic sieve (QS)
1892:, 2nd ed., Springer.
1856:"Discrete Logarithm"
1555:leaked NSA documents
1384:, i.e. has no large
1380:â1) is sufficiently
1299:Function field sieve
1294:Baby-step giant-step
1253:trial multiplication
1122:
1041:
959:
813:
538:exponential function
439:
258:
191:. Several important
2828:Three-pass protocol
2454:Trachtenberg system
2420:Integer square root
2361:Modular square root
2080:Wheel factorization
2032:Quadratic Frobenius
2012:LucasâLehmerâRiesel
1854:Weisstein, Eric W.
1547:intelligence agency
920:does not exist for
566:is defined for any
205:hardness assumption
3211:Modular arithmetic
3077:Discrete logarithm
3061:Higher residuosity
2598:Discrete logarithm
2346:Extended Euclidean
2285:Discrete logarithm
2214:SchönhageâStrassen
2070:Sieve of Pritchard
1634:. pp. 54â56.
1513:number field sieve
1483:ElGamal encryption
1349:becomes a product
1309:Number field sieve
1247:until the desired
1182:
1078:
1029:congruence modulo
989:
862:from the integers
860:group homomorphism
833:
667:congruence classes
639:Modular arithmetic
521:. For example, log
496:
387:discrete logarithm
320:
316:
303:
231:be any element of
82:discrete logarithm
3198:
3197:
3173:Non-cryptographic
2983:
2982:
2935:Digital signature
2878:Trapdoor function
2841:
2840:
2558:GoldwasserâMicali
2476:
2475:
2075:Sieve of Sundaram
1911:978-1-58488-508-5
1657:978-3-7643-6510-3
1549:such as the U.S.
1463:one-way functions
1413:quantum computers
1332:quantum algorithm
1235:in finite groups
951:group isomorphism
771:is undefined for
313:
276:
274:
239:, the expression
183:) = 1.
3248:
3113:Sub-group hiding
3024:Number theoretic
3010:
3003:
2996:
2987:
2824:
2725:
2720:
2680:signature scheme
2583:OkamotoâUchiyama
2521:
2503:
2496:
2489:
2480:
2425:Integer relation
2398:Other algorithms
2303:Pollard kangaroo
2194:Ancient Egyptian
2052:Prime-generating
2037:SolovayâStrassen
1950:Number-theoretic
1943:
1936:
1929:
1920:
1915:
1882:Richard Crandall
1870:
1868:
1867:
1850:
1826:
1825:
1814:10.17487/RFC2409
1797:
1791:
1790:
1788:
1775:
1764:
1763:
1753:
1729:
1723:
1722:
1696:
1694:quant-ph/9508027
1687:(5): 1484â1509.
1676:
1670:
1669:
1632:BirkhÀuser Basel
1621:
1612:
1611:
1601:
1592:
1209:
1191:
1189:
1188:
1183:
1172:
1171:
1153:
1152:
1134:
1133:
1087:
1085:
1084:
1079:
1074:
1073:
1068:
1053:
1052:
998:
996:
995:
990:
985:
971:
970:
924:that are not in
842:
840:
839:
834:
826:
505:
503:
502:
497:
405: = log
384:
359:
329:
327:
326:
321:
315:
314:
311:
304:
299:
270:
269:
225:identity element
107:
61:
3256:
3255:
3251:
3250:
3249:
3247:
3246:
3245:
3201:
3200:
3199:
3194:
3168:
3122:
3118:Decision linear
3096:
3070:Group theoretic
3065:
3019:
3014:
2984:
2979:
2923:
2887:Standardization
2882:
2837:
2820:
2769:
2717:Lattice/SVP/CVP
2711:
2592:
2538:BlumâGoldwasser
2512:
2507:
2477:
2472:
2458:
2393:
2355:
2322:
2279:
2223:
2180:
2084:
2046:
2019:Proth's theorem
1961:Primality tests
1955:
1947:
1912:
1895:
1878:
1876:Further reading
1873:
1865:
1863:
1853:
1847:
1834:
1830:
1829:
1799:
1798:
1794:
1786:
1780:Heninger, Nadia
1777:
1776:
1767:
1731:
1730:
1726:
1678:
1677:
1673:
1658:
1623:
1622:
1615:
1599:
1594:
1593:
1589:
1584:
1576:Irish logarithm
1563:
1495:elliptic curves
1480:
1445:
1435:
1394:
1287:polynomial time
1230:
1220:
1219:
1214:
1211:
1207:
1204:
1198:
1163:
1144:
1125:
1120:
1119:
1099:
1063:
1044:
1039:
1038:
1022:
962:
957:
956:
944:
915:
901:
866:under addition
811:
810:
789:
766:
751:
717:
710:
652:
641:
630:
580:
561:
545:group-theoretic
535:
528:
524:
516:
509:For any number
437:
436:
426:
421:
410:
376:
354:
333:Similarly, let
277:
261:
256:
255:
221:group operation
213:
125:
116:: we can write
99:
89:
53:
43:
17:
12:
11:
5:
3254:
3252:
3244:
3243:
3238:
3233:
3228:
3223:
3218:
3213:
3203:
3202:
3196:
3195:
3193:
3192:
3187:
3182:
3176:
3174:
3170:
3169:
3167:
3166:
3161:
3156:
3151:
3141:
3130:
3128:
3124:
3123:
3121:
3120:
3115:
3110:
3104:
3102:
3098:
3097:
3095:
3094:
3089:
3084:
3082:Diffie-Hellman
3079:
3073:
3071:
3067:
3066:
3064:
3063:
3058:
3053:
3048:
3043:
3038:
3033:
3027:
3025:
3021:
3020:
3015:
3013:
3012:
3005:
2998:
2990:
2981:
2980:
2978:
2977:
2972:
2967:
2962:
2957:
2952:
2947:
2942:
2937:
2931:
2929:
2925:
2924:
2922:
2921:
2916:
2911:
2906:
2901:
2896:
2890:
2888:
2884:
2883:
2881:
2880:
2875:
2870:
2865:
2860:
2855:
2849:
2847:
2843:
2842:
2839:
2838:
2836:
2835:
2830:
2825:
2818:
2816:MerkleâHellman
2813:
2808:
2803:
2798:
2793:
2788:
2783:
2777:
2775:
2771:
2770:
2768:
2767:
2762:
2757:
2752:
2747:
2742:
2737:
2731:
2729:
2713:
2712:
2710:
2709:
2704:
2699:
2694:
2689:
2684:
2683:
2682:
2672:
2667:
2662:
2661:
2660:
2655:
2645:
2640:
2639:
2638:
2633:
2623:
2618:
2613:
2608:
2602:
2600:
2594:
2593:
2591:
2590:
2585:
2580:
2575:
2570:
2565:
2563:NaccacheâStern
2560:
2555:
2550:
2545:
2540:
2535:
2529:
2527:
2518:
2514:
2513:
2508:
2506:
2505:
2498:
2491:
2483:
2474:
2473:
2471:
2470:
2463:
2460:
2459:
2457:
2456:
2451:
2446:
2441:
2436:
2422:
2417:
2412:
2407:
2401:
2399:
2395:
2394:
2392:
2391:
2386:
2381:
2379:TonelliâShanks
2376:
2371:
2365:
2363:
2357:
2356:
2354:
2353:
2348:
2343:
2338:
2332:
2330:
2324:
2323:
2321:
2320:
2315:
2313:Index calculus
2310:
2308:PohligâHellman
2305:
2300:
2295:
2289:
2287:
2281:
2280:
2278:
2277:
2272:
2267:
2262:
2260:Newton-Raphson
2257:
2252:
2247:
2242:
2236:
2234:
2225:
2224:
2222:
2221:
2216:
2211:
2206:
2201:
2196:
2190:
2188:
2186:Multiplication
2182:
2181:
2179:
2178:
2173:
2171:Trial division
2168:
2163:
2158:
2156:Rational sieve
2153:
2146:
2141:
2136:
2128:
2120:
2115:
2110:
2105:
2100:
2094:
2092:
2086:
2085:
2083:
2082:
2077:
2072:
2067:
2062:
2060:Sieve of Atkin
2056:
2054:
2048:
2047:
2045:
2044:
2039:
2034:
2029:
2022:
2015:
2008:
2001:
1996:
1991:
1986:
1984:Elliptic curve
1981:
1976:
1971:
1965:
1963:
1957:
1956:
1948:
1946:
1945:
1938:
1931:
1923:
1917:
1916:
1910:
1893:
1886:Carl Pomerance
1877:
1874:
1872:
1871:
1851:
1846:978-0321500311
1845:
1831:
1828:
1827:
1792:
1765:
1744:(2): 148â170.
1724:
1671:
1656:
1613:
1586:
1585:
1583:
1580:
1579:
1578:
1569:
1562:
1559:
1476:
1441:
1434:
1431:
1430:
1429:
1422:
1419:
1416:
1409:
1393:
1390:
1370:DiffieâHellman
1328:
1327:
1321:
1316:
1311:
1306:
1301:
1296:
1255:. It requires
1226:
1215:
1212:
1206:
1197:
1194:
1193:
1192:
1181:
1178:
1175:
1170:
1166:
1162:
1159:
1156:
1151:
1147:
1143:
1140:
1137:
1132:
1128:
1095:
1089:
1088:
1077:
1072:
1067:
1062:
1059:
1056:
1051:
1047:
1018:
1000:
999:
988:
984:
980:
977:
974:
969:
965:
940:
911:
897:
844:
843:
832:
829:
825:
821:
818:
788:
785:
762:
750:
747:
745:⥠4 (mod 16).
715:
708:
648:
640:
637:
626:
579:
576:
559:
533:
526:
522:
514:
507:
506:
495:
492:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
425:
422:
420:
417:
406:
331:
330:
319:
308:
302:
298:
295:
292:
289:
286:
283:
280:
273:
268:
264:
212:
209:
165:primitive root
121:
94:is an integer
85:
39:
15:
13:
10:
9:
6:
4:
3:
2:
3253:
3242:
3239:
3237:
3234:
3232:
3231:Finite fields
3229:
3227:
3224:
3222:
3219:
3217:
3214:
3212:
3209:
3208:
3206:
3191:
3188:
3186:
3183:
3181:
3178:
3177:
3175:
3171:
3165:
3162:
3160:
3157:
3155:
3152:
3149:
3145:
3142:
3139:
3135:
3132:
3131:
3129:
3125:
3119:
3116:
3114:
3111:
3109:
3106:
3105:
3103:
3099:
3093:
3090:
3088:
3085:
3083:
3080:
3078:
3075:
3074:
3072:
3068:
3062:
3059:
3057:
3054:
3052:
3049:
3047:
3044:
3042:
3039:
3037:
3034:
3032:
3029:
3028:
3026:
3022:
3018:
3011:
3006:
3004:
2999:
2997:
2992:
2991:
2988:
2976:
2973:
2971:
2968:
2966:
2963:
2961:
2958:
2956:
2953:
2951:
2948:
2946:
2943:
2941:
2938:
2936:
2933:
2932:
2930:
2926:
2920:
2917:
2915:
2912:
2910:
2907:
2905:
2902:
2900:
2897:
2895:
2892:
2891:
2889:
2885:
2879:
2876:
2874:
2871:
2869:
2866:
2864:
2861:
2859:
2856:
2854:
2851:
2850:
2848:
2844:
2834:
2831:
2829:
2826:
2823:
2819:
2817:
2814:
2812:
2809:
2807:
2804:
2802:
2799:
2797:
2794:
2792:
2789:
2787:
2784:
2782:
2779:
2778:
2776:
2772:
2766:
2763:
2761:
2758:
2756:
2753:
2751:
2748:
2746:
2743:
2741:
2738:
2736:
2733:
2732:
2730:
2728:
2723:
2718:
2714:
2708:
2705:
2703:
2700:
2698:
2695:
2693:
2690:
2688:
2685:
2681:
2678:
2677:
2676:
2673:
2671:
2668:
2666:
2663:
2659:
2656:
2654:
2651:
2650:
2649:
2646:
2644:
2641:
2637:
2634:
2632:
2629:
2628:
2627:
2624:
2622:
2619:
2617:
2614:
2612:
2609:
2607:
2604:
2603:
2601:
2599:
2595:
2589:
2588:SchmidtâSamoa
2586:
2584:
2581:
2579:
2576:
2574:
2571:
2569:
2566:
2564:
2561:
2559:
2556:
2554:
2551:
2549:
2548:DamgĂ„rdâJurik
2546:
2544:
2543:CayleyâPurser
2541:
2539:
2536:
2534:
2531:
2530:
2528:
2526:
2522:
2519:
2515:
2511:
2504:
2499:
2497:
2492:
2490:
2485:
2484:
2481:
2468:
2465:
2464:
2461:
2455:
2452:
2450:
2447:
2445:
2442:
2440:
2437:
2434:
2430:
2426:
2423:
2421:
2418:
2416:
2413:
2411:
2408:
2406:
2403:
2402:
2400:
2396:
2390:
2387:
2385:
2382:
2380:
2377:
2375:
2374:Pocklington's
2372:
2370:
2367:
2366:
2364:
2362:
2358:
2352:
2349:
2347:
2344:
2342:
2339:
2337:
2334:
2333:
2331:
2329:
2325:
2319:
2316:
2314:
2311:
2309:
2306:
2304:
2301:
2299:
2296:
2294:
2291:
2290:
2288:
2286:
2282:
2276:
2273:
2271:
2268:
2266:
2263:
2261:
2258:
2256:
2253:
2251:
2248:
2246:
2243:
2241:
2238:
2237:
2235:
2233:
2230:
2226:
2220:
2217:
2215:
2212:
2210:
2207:
2205:
2202:
2200:
2197:
2195:
2192:
2191:
2189:
2187:
2183:
2177:
2174:
2172:
2169:
2167:
2164:
2162:
2159:
2157:
2154:
2152:
2151:
2147:
2145:
2142:
2140:
2137:
2135:
2133:
2129:
2127:
2125:
2121:
2119:
2118:Pollard's rho
2116:
2114:
2111:
2109:
2106:
2104:
2101:
2099:
2096:
2095:
2093:
2091:
2087:
2081:
2078:
2076:
2073:
2071:
2068:
2066:
2063:
2061:
2058:
2057:
2055:
2053:
2049:
2043:
2040:
2038:
2035:
2033:
2030:
2028:
2027:
2023:
2021:
2020:
2016:
2014:
2013:
2009:
2007:
2006:
2002:
2000:
1997:
1995:
1992:
1990:
1987:
1985:
1982:
1980:
1977:
1975:
1972:
1970:
1967:
1966:
1964:
1962:
1958:
1954:
1951:
1944:
1939:
1937:
1932:
1930:
1925:
1924:
1921:
1913:
1907:
1903:
1899:
1894:
1891:
1888:. Chapter 5,
1887:
1883:
1880:
1879:
1875:
1862:. Wolfram Web
1861:
1857:
1852:
1848:
1842:
1838:
1833:
1832:
1823:
1819:
1815:
1811:
1807:
1803:
1796:
1793:
1785:
1781:
1774:
1772:
1770:
1766:
1761:
1757:
1752:
1747:
1743:
1739:
1735:
1728:
1725:
1720:
1716:
1712:
1708:
1704:
1700:
1695:
1690:
1686:
1682:
1675:
1672:
1667:
1663:
1659:
1653:
1649:
1645:
1641:
1637:
1633:
1629:
1628:
1620:
1618:
1614:
1609:
1605:
1598:
1591:
1588:
1581:
1577:
1573:
1572:Percy Ludgate
1570:
1568:
1565:
1564:
1560:
1558:
1556:
1552:
1548:
1543:
1541:
1537:
1533:
1528:
1526:
1522:
1518:
1514:
1509:
1507:
1504:
1500:
1499:finite fields
1496:
1492:
1488:
1484:
1479:
1475:
1471:
1466:
1464:
1460:
1455:
1453:
1449:
1444:
1440:
1432:
1427:
1426:cryptographic
1423:
1420:
1417:
1414:
1410:
1407:
1403:
1399:
1398:
1397:
1391:
1389:
1387:
1386:prime factors
1383:
1379:
1375:
1371:
1366:
1364:
1360:
1356:
1352:
1348:
1344:
1339:
1337:
1333:
1325:
1322:
1320:
1317:
1315:
1312:
1310:
1307:
1305:
1302:
1300:
1297:
1295:
1292:
1291:
1290:
1288:
1284:
1280:
1275:
1273:
1269:
1265:
1261:
1258:
1254:
1250:
1246:
1242:
1238:
1234:
1229:
1223:
1218:
1203:
1195:
1179:
1176:
1173:
1168:
1164:
1160:
1157:
1154:
1149:
1145:
1141:
1138:
1135:
1130:
1126:
1118:
1117:
1116:
1114:
1110:
1105:
1103:
1098:
1094:
1075:
1070:
1057:
1054:
1049:
1045:
1037:
1036:
1035:
1033:
1032:
1026:
1021:
1016:
1013:
1009:
1005:
986:
975:
972:
967:
963:
955:
954:
953:
952:
948:
943:
938:
934:
929:
927:
923:
919:
914:
909:
905:
900:
895:
891:
887:
883:
880:
876:
873:
869:
865:
861:
857:
853:
849:
830:
819:
816:
809:
808:
807:
806:
802:
798:
794:
786:
784:
782:
778:
774:
770:
765:
760:
756:
748:
746:
744:
740:
736:
732:
728:
724:
719:
714:
707:
703:
699:
695:
691:
687:
683:
678:
676:
672:
668:
664:
661:
657:
653:
651:
647:
638:
636:
634:
629:
624:
620:
616:
612:
608:
604:
600:
596:
592:
589:
585:
577:
575:
573:
569:
565:
557:
553:
550:
546:
541:
539:
530:
520:
512:
493:
490:
487:
484:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
435:
434:
433:
431:
423:
418:
416:
414:
409:
404:
401:. One writes
400:
396:
392:
388:
383:
379:
374:
371:. An integer
370:
366:
361:
357:
352:
348:
344:
340:
336:
317:
306:
300:
296:
293:
290:
287:
284:
281:
278:
271:
266:
262:
254:
253:
252:
250:
246:
242:
238:
234:
230:
226:
222:
218:
210:
208:
206:
202:
198:
194:
190:
184:
182:
178:
174:
170:
166:
162:
158:
154:
150:
146:
143:
140:
136:
132:
128:
124:
119:
115:
111:
110:number theory
106:
102:
97:
93:
88:
83:
79:
76:
72:
68:
65:
60:
56:
51:
47:
42:
37:
33:
29:
26:
22:
3221:Cryptography
3216:Group theory
2975:OpenPGP card
2955:Web of trust
2611:CramerâShoup
2597:
2466:
2284:
2148:
2131:
2123:
2042:MillerâRabin
2024:
2017:
2010:
2005:LucasâLehmer
2003:
1897:
1889:
1864:. Retrieved
1859:
1836:
1805:
1795:
1741:
1737:
1727:
1684:
1680:
1674:
1626:
1603:
1590:
1544:
1540:export grade
1529:
1525:precomputing
1520:
1516:
1510:
1502:
1477:
1473:
1469:
1467:
1456:
1442:
1438:
1436:
1433:Cryptography
1395:
1377:
1373:
1367:
1362:
1354:
1350:
1346:
1342:
1340:
1329:
1276:
1271:
1263:
1257:running time
1252:
1248:
1244:
1240:
1239:is to raise
1236:
1232:
1227:
1224:
1221:
1112:
1108:
1106:
1101:
1096:
1092:
1090:
1030:
1024:
1019:
1014:
1003:
1001:
946:
941:
932:
930:
925:
921:
917:
912:
903:
898:
893:
889:
885:
878:
874:
863:
855:
851:
847:
845:
800:
796:
792:
790:
780:
776:
772:
768:
763:
758:
754:
752:
742:
738:
734:
730:
722:
720:
712:
705:
697:
693:
689:
681:
679:
674:
670:
662:
649:
645:
642:
632:
627:
622:
618:
614:
610:
606:
602:
598:
594:
590:
583:
581:
571:
567:
563:
551:
549:cyclic group
542:
531:
518:
510:
508:
430:powers of 10
427:
424:Powers of 10
412:
407:
402:
398:
397:to the base
394:
390:
386:
385:is termed a
381:
377:
372:
368:
364:
362:
355:
350:
346:
342:
341:with itself
338:
334:
332:
248:
247:with itself
244:
240:
236:
232:
228:
216:
214:
185:
180:
176:
168:
160:
156:
152:
148:
144:
138:
137:to the base
134:
130:
126:
122:
117:
113:
104:
100:
95:
91:
86:
81:
77:
70:
66:
58:
54:
49:
48:is a number
45:
40:
31:
27:
25:real numbers
23:, for given
18:
3041:RSA problem
2945:Fingerprint
2909:NSA Suite B
2873:RSA problem
2750:NTRUEncrypt
2298:Pollard rho
2255:Goldschmidt
1989:Pocklington
1979:BaillieâPSW
1283:square root
1268:exponential
846:defined by
389:(or simply
345:times. For
21:mathematics
3226:Logarithms
3205:Categories
3046:Strong RSA
3036:Phi-hiding
2899:IEEE P1363
2517:Algorithms
2410:Cornacchia
2405:Chakravala
1953:algorithms
1866:2019-01-01
1582:References
1489:, and the
1336:Peter Shor
1200:See also:
1196:Algorithms
1017:, then log
939:, then log
908:Conversely
888:. For all
787:Properties
227:by 1. Let
211:Definition
199:, such as
193:algorithms
155:(mod
129:(mod
98:such that
80:, and the
52:such that
2384:Berlekamp
2341:Euclidean
2229:Euclidean
2209:ToomâCook
2204:Karatsuba
1902:CRC Press
1860:MathWorld
1822:2070-1721
1760:0885-064X
1666:2297-0576
1648:2297-0584
1608:CRC Press
1365:quickly.
1266:and thus
1174:
1161:⋅
1155:
1136:
1061:→
1055::
979:→
973::
882:generated
828:→
820::
556:generator
491:…
443:…
391:logarithm
349:= 0, the
301:⏟
294:⋅
291:…
288:⋅
282:⋅
69:, powers
36:logarithm
3127:Lattices
3101:Pairings
2960:Key size
2894:CRYPTREC
2811:McEliece
2765:RLWE-SIG
2760:RLWE-KEX
2755:NTRUSign
2568:Paillier
2351:Lehmer's
2245:Chunking
2232:division
2161:Fermat's
1561:See also
1532:internet
1428:systems.
937:infinite
906:exists.
872:subgroup
805:function
588:subgroup
419:Examples
75:integers
2806:Lamport
2786:CEILIDH
2745:NewHope
2692:Schnorr
2675:ElGamal
2653:Ed25519
2533:Benaloh
2467:Italics
2389:Kunerth
2369:Cipolla
2250:Fourier
2219:FĂŒrer's
2113:Euler's
2103:Dixon's
2026:PĂ©pin's
1719:2337707
1711:1471990
1334:due to
1231:
1115:, then
1023:
945:
916:
902:
799:
767:
669:modulo
631:
562:
517:
411:
312:factors
251:times:
201:ElGamal
147:") for
90:
44:
2928:Topics
2904:NESSIE
2846:Theory
2774:Others
2631:X25519
2449:Schoof
2336:Binary
2240:Binary
2176:Shor's
1994:Fermat
1908:
1843:
1820:
1758:
1717:
1709:
1664:
1654:
1646:
1536:Logjam
1481:(e.g.
1382:smooth
1361:finds
1260:linear
1091:where
1008:finite
656:modulo
593:= {âŠ,
142:modulo
34:, the
2740:Kyber
2735:BLISS
2697:SPEKE
2665:ECMQV
2658:Ed448
2648:EdDSA
2643:ECDSA
2573:Rabin
2270:Short
1999:Lucas
1787:(PDF)
1715:S2CID
1689:arXiv
1644:eISSN
1600:(PDF)
1497:over
1368:With
1012:order
910:, log
896:, log
858:is a
783:= 1.
686:power
660:prime
605:, 1,
449:0.001
163:is a
159:) if
120:= ind
114:index
108:. In
64:group
2940:OAEP
2914:CNSA
2791:EPOC
2636:X448
2626:ECDH
2265:Long
2199:Long
1906:ISBN
1841:ISBN
1818:ISSN
1756:ISSN
1662:ISSN
1652:ISBN
1574:and
1404:for
870:the
868:onto
854:) =
680:The
658:the
485:1000
455:0.01
432:are
428:The
363:Let
215:Let
171:and
30:and
3148:gap
3138:gap
2950:PKI
2833:XTR
2801:IES
2796:HFE
2727:SIS
2722:LWE
2707:STS
2702:SRP
2687:MQV
2670:EKE
2621:DSA
2606:BLS
2578:RSA
2553:GMR
2429:LLL
2275:SRT
2134:+ 1
2126:â 1
1974:APR
1969:AKS
1810:doi
1746:doi
1699:doi
1636:doi
1508:).
1503:see
1165:log
1146:log
1127:log
1046:log
1010:of
1006:is
964:log
935:is
931:If
892:in
884:by
877:of
684:th
621:of
570:in
543:In
479:100
461:0.1
358:= 1
195:in
173:gcd
167:of
84:log
38:log
19:In
3207::
2781:AE
2616:DH
2433:KZ
2431:;
1904:.
1884:;
1858:.
1816:.
1808:.
1804:.
1768:^
1754:.
1742:20
1736:.
1713:.
1707:MR
1705:.
1697:.
1685:26
1683:.
1660:.
1650:.
1642:.
1616:^
1606:.
1602:.
1542:.
1485:,
1454:.
1415:),
1388:.
1351:bk
1338:.
1274:.
1104:.
928:.
795:=
718:.
716:17
709:17
677:.
635:.
613:,
609:,
601:,
597:,
574:.
560:10
540:.
534:10
527:10
523:10
515:10
473:10
415:.
380:=
360:.
151:âĄ
103:=
57:=
3150:)
3146:(
3140:)
3136:(
3009:e
3002:t
2995:v
2724:/
2719:/
2502:e
2495:t
2488:v
2435:)
2427:(
2132:p
2124:p
1942:e
1935:t
1928:v
1914:.
1869:.
1849:.
1824:.
1812::
1789:.
1762:.
1748::
1721:.
1701::
1691::
1668:.
1638::
1610:.
1521:G
1517:G
1501:(
1478:p
1474:Z
1470:G
1443:p
1439:Z
1408:,
1378:p
1374:p
1363:k
1355:p
1347:b
1343:p
1272:G
1264:G
1249:a
1245:k
1241:b
1237:G
1233:a
1228:b
1210::
1180:.
1177:a
1169:b
1158:b
1150:c
1142:=
1139:a
1131:c
1113:H
1109:c
1102:n
1097:n
1093:Z
1076:,
1071:n
1066:Z
1058:H
1050:b
1031:n
1025:a
1020:b
1015:n
1004:H
987:.
983:Z
976:H
968:b
947:a
942:b
933:H
926:H
922:a
918:a
913:b
904:a
899:b
894:H
890:a
886:b
879:G
875:H
864:Z
856:b
852:k
850:(
848:f
831:G
824:Z
817:f
801:b
797:b
793:b
781:a
777:k
773:a
769:a
764:b
759:G
755:b
743:k
739:m
735:n
731:n
723:k
713:Z
706:Z
698:p
694:p
690:k
682:k
675:p
671:p
663:p
650:p
646:Z
633:a
628:b
623:G
619:a
615:b
611:b
607:b
603:b
599:b
595:b
591:G
584:b
572:G
568:a
564:a
552:G
519:a
511:a
494:.
488:,
482:,
476:,
470:,
467:1
464:,
458:,
452:,
446:,
413:a
408:b
403:k
399:b
395:a
382:a
378:b
373:k
369:G
365:a
356:b
351:k
347:k
343:k
339:b
335:b
318:.
307:k
297:b
285:b
279:b
272:=
267:k
263:b
249:k
245:b
241:b
237:k
233:G
229:b
217:G
181:m
179:,
177:a
175:(
169:m
161:r
157:m
153:a
149:r
145:m
139:r
135:a
131:m
127:a
123:r
118:x
105:a
101:b
96:k
92:a
87:b
78:k
71:b
67:G
59:a
55:b
50:x
46:a
41:b
32:b
28:a
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.