19:
2114:
723:: the resulting implementation can be laid out to avoid repeated work, invoking identity 2 at the start and maintaining as invariant that both numbers are odd upon entering the loop, which only needs to implement identities 3 and 4;
3365:
1689:, as each arithmetic operation (subtract and shift) involves a linear number of machine operations (one per word in the numbers' binary representation). If the numbers can be represented in the machine's memory,
1755:
1887:
1375:
253:
3369:
2067:
If possible halve it; otherwise, take the denominator and the numerator, subtract the lesser from the greater, and do that alternately to make them the same. Reduce by the same number.
438:
1644:
650:
334:
2877:
550:
53:
Although the algorithm in its contemporary form was first published by the physicist and programmer Josef Stein in 1967, it was known by the 2nd century BCE, in ancient China.
1937:
591:
143:
2910:
2022:
1687:
820:
490:
1966:
1566:
1497:
754:
464:
1759:
This is the same as for the
Euclidean algorithm, though a more precise analysis by Akhavi and Vallée proved that binary GCD uses about 60% fewer bit operations.
1986:
1824:
1804:
1590:
1537:
1517:
794:
774:
706:
670:
374:
354:
273:
183:
163:
99:
79:
680:
While the above description of the algorithm is mathematically correct, performant software implementations typically differ from it in a few notable ways:
3234:
2870:
2074:
835:
3102:
2305:
1700:
2694:
2509:
2267:
2762:
3425:
3044:
2863:
2973:
3150:
2029:
1519:
is the number of bits in the larger of the two numbers, as every two steps reduce at least one of the operands by at least a factor of
22:
Visualisation of using the binary GCD algorithm to find the greatest common divisor (GCD) of 36 and 24. Thus, the GCD is 2 Ă 3 = 12.
2948:
2731:
2455:
2410:
1572:
numbers, each arithmetic operation translates to a single machine operation, so the number of machine operations is on the order of
3059:
3097:
3034:
2978:
2941:
3239:
3130:
3049:
3039:
2686:
2472:
2259:
2915:
3067:
1768:
3320:
2324:
2719:
2709:
2443:
2433:
3315:
3244:
3145:
3282:
2132:
1779:
1569:
720:
3196:
2119:
831:
1829:
1314:
3361:
3351:
3310:
3086:
3080:
3054:
2925:
190:
3346:
3287:
2846:
2746:
727:
3249:
3122:
2968:
2920:
2024:, though concrete implementations only outperform older algorithms for numbers larger than about 64 kilobits (
42:(GCD) of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conventional
1767:
The binary GCD algorithm can be extended in several ways, either to output additional information, deal with
3264:
3155:
2656:. Automata, Languages and Programming, 32nd International Colloquium. Lisbon, Portugal. pp. 1189â1201.
39:
381:
3375:
3325:
3305:
2742:
2487:
2361:
1783:
1595:
596:
280:
499:
3026:
3001:
2930:
2137:
1385:/// The result is unsigned and not always representable as i64: gcd(i64::MIN, i64::MIN) == 1 << 63
3385:
18:
3380:
3254:
3229:
3191:
2935:
2215:
709:
2492:
3390:
3356:
3277:
3181:
3140:
3135:
3112:
3016:
2802:
2476:
2366:
2127:
2098:
2040:
1895:
1650:
43:
2790:
3221:
3168:
3165:
3006:
2905:
2782:
2750:
2523:
2186:
2028:
greater than 8Ă10). This is achieved by extending the binary GCD algorithm using ideas from the
555:
107:
2962:
2955:
2758:
2035:
The binary GCD algorithm has also been extended to domains other than natural numbers, such as
3341:
3297:
3011:
2988:
2814:
2810:
2727:
2690:
2505:
2451:
2406:
2263:
2231:
2036:
1991:
1656:
823:
712:
primitive; this is functionally equivalent to repeatedly applying identity 3, but much faster;
799:
469:
3186:
2806:
2774:
2657:
2634:
2633:. 7th Latin American Symposium on Theoretical Informatics. Valdivia, Chile. pp. 30â42.
2611:
2584:
2555:
2497:
2353:
2223:
2176:
2156:
2044:
1988:-bit multiplication; this is near-linear and vastly smaller than the binary GCD algorithm's
47:
2519:
3176:
3075:
2723:
2515:
2447:
1942:
1542:
1473:
1254:// The shift by k is necessary to add back the 2á” factor that was removed before the loop
733:
443:
2393:
2219:
2180:
2059:
An algorithm for computing the GCD of two numbers was known in ancient China, under the
3206:
3107:
3092:
2996:
2897:
2607:
1971:
1809:
1789:
1575:
1522:
1502:
1467:
779:
759:
691:
685:
655:
359:
339:
258:
168:
148:
84:
64:
2741:
Covers a variety of topics, including the extended binary GCD algorithm which outputs
2544:"(1+i)-ary GCD Computation in Z[i] as an Analogue to the Binary GCD Algorithm"
3419:
3201:
2886:
2577:
Efficient
Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers
2486:, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, pp. 411â425,
2227:
2048:
2840:
2786:
2160:
3211:
2835:
2826:
2678:
2527:
2251:
2206:
Stein, J. (February 1967), "Computational problems associated with Racah algebra",
2165:. 1999 Oxford-Microsoft Symposium in honour of Professor Sir Antony Hoare. Oxford.
2713:
2588:
2501:
2437:
2831:
2615:
2113:
2060:
2763:"Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators"
2704:
Covers the extended binary GCD, and a probabilistic analysis of the algorithm.
2855:
2392:
Menezes, Alfred J.; van
Oorschot, Paul C.; Vanstone, Scott A. (October 1996).
2109:
2235:
2889:
826:; hard-to-predict branches can have a large, negative impact on performance.
716:
2560:
2543:
2338:
2579:. 14th International Symposium on the Fundamentals of Computation Theory.
2580:
1771:
more efficiently, or to compute GCDs in domains other than the integers.
2661:
2631:
A New GCD Algorithm for
Quadratic Number Rings with Unique Factorization
2827:
NIST Dictionary of
Algorithms and Data Structures: binary GCD algorithm
2778:
2638:
2575:
DamgÄrd, Ivan Bjerre; Frandsen, Gudmund
Skovbjerg (12â15 August 2003).
2283:
1697:
can be represented by a single machine word, this bound is reduced to:
2801:
An analysis of the algorithm in the average case, through the lens of
2090:
of the numbers become even, the algorithm is the binary GCD algorithm;
1218:// Identity 4: gcd(u, v) = gcd(u, v-u) as u †v and u, v are both odd
2745:, efficient handling of multi-precision integers using a variant of
2712:(1993). "Chapter 1 : Fundamental Number-Theoretic Algorithms".
2436:(1993). "Chapter 1 : Fundamental Number-Theoretic Algorithms".
2629:
Agarwal, Saurabh; Frandsen, Gudmund
Skovbjerg (20â24 March 2006).
2191:
990:// 2á” is the greatest power of two that divides both 2â± u and 2ÊČ v
17:
2602:
Agarwal, Saurabh; Frandsen, Gudmund
Skovbjerg (13â18 June 2004).
1892:
In the case of large integers, the best asymptotic complexity is
987:// gcd(2â± u, 2ÊČ v) = 2á” gcd(u, v) with u, v odd and k = min(i, j)
2689:. Vol. 2 (3rd ed.). Addison-Wesley. pp. 330â417.
2400:
2859:
552:), those identities still apply if the operands are swapped:
2185:(Technical report). Oxford University Computing Laboratory.
2604:
Binary GCD Like
Algorithms for Some Complex Quadratic Rings
1782:, fits in the first kind of extension, as it provides the
2358:
Proceedings ICALP'00, Lecture Notes
Computer Science 1853
1750:{\displaystyle O\left({\frac {n^{2}}{\log _{2}n}}\right)}
2162:
Twenty years' analysis of the Binary Euclidean Algorithm
1539:. Each step involves only a few arithmetic operations (
3406:
indicate that algorithm is for numbers of special forms
2325:"Mispredicted branches can multiply your running times"
830:
The following is an implementation of the algorithm in
61:
The algorithm finds the GCD of two nonnegative numbers
2382:, p. 646, answer to exercise 39 of section 4.5.2
1994:
1974:
1945:
1898:
1832:
1812:
1792:
1703:
1659:
1598:
1578:
1545:
1525:
1505:
1476:
1317:
802:
782:
762:
736:
694:
658:
599:
558:
502:
472:
446:
384:
362:
342:
283:
261:
193:
171:
151:
110:
87:
67:
3334:
3296:
3263:
3220:
3164:
3121:
3025:
2987:
2896:
1275:// Identity 3: gcd(u, 2ÊČ v) = gcd(u, v) as u is odd
2182:Further analysis of the Binary Euclidean algorithm
2097:numbers are even, the algorithm is similar to the
2016:
1980:
1960:
1931:
1881:
1818:
1798:
1749:
1681:
1638:
1584:
1560:
1531:
1511:
1491:
1382:/// Computes the GCD of two signed 64-bit integers
1369:
814:
788:
768:
748:
700:
664:
644:
585:
544:
484:
458:
432:
368:
348:
328:
267:
247:
177:
157:
137:
93:
73:
2715:A Course In Computational Algebraic Number Theory
2439:A Course In Computational Algebraic Number Theory
2805:: the algorithms' main parameters are cast as a
2354:"Average Bit-Complexity of Euclidean Algorithms"
2082:The phrase "if possible halve it" is ambiguous,
1861:
1615:
1339:
1318:
624:
600:
559:
524:
503:
406:
385:
308:
284:
227:
194:
111:
2654:On the l-Ary GCD-Algorithm in Rings of Integers
2065:
1882:{\displaystyle a\cdot {}u+b\cdot {}v=\gcd(u,v)}
1370:{\displaystyle \gcd(u,v)=\gcd(\pm {}u,\pm {}v)}
2262:, vol. 2 (3rd ed.), Addison-Wesley,
2871:
1377:, the signed case can be handled as follows:
834:exemplifying those differences, adapted from
8:
2809:, and their average value is related to the
248:{\displaystyle \gcd(2u,2v)=2\cdot \gcd(u,v)}
2306:"Avoiding the Cost of Branch Misprediction"
1092:// u and v are odd at the start of the loop
2878:
2864:
2856:
2842:Analysis of the Binary Euclidean Algorithm
2394:"§14.4 Greatest Common Divisor Algorithms"
1568:with a small constant); when working with
2559:
2491:
2365:
2246:
2244:
2190:
2075:The Nine Chapters on the Mathematical Art
2005:
1993:
1973:
1944:
1897:
1853:
1839:
1831:
1811:
1791:
1728:
1717:
1711:
1702:
1670:
1658:
1603:
1597:
1577:
1544:
1524:
1504:
1475:
1359:
1348:
1316:
801:
781:
761:
756:): in the example below, the exchange of
735:
693:
657:
598:
557:
501:
471:
445:
383:
361:
341:
282:
260:
192:
170:
150:
109:
101:by repeatedly applying these identities:
86:
66:
924:// Base cases: gcd(n, 0) = gcd(0, n) = n
2849:, including a variant using left shifts
2832:Cut-the-Knot: Binary Euclid's Algorithm
2749:, and the relationship between GCD and
2606:. Algorithmic Number Theory Symposium.
2148:
708:in favour of a single bitshift and the
2352:Akhavi, Ali; Vallée, Brigitte (2000),
2652:Wikström, Douglas (11â15 July 2005).
2379:
433:{\displaystyle \gcd(u,v)=\gcd(u,v-u)}
7:
2681:(1998). "§4.5 Rational arithmetic".
1639:{\displaystyle \log _{2}(\max(u,v))}
1311:(non-negative) integers; given that
645:{\displaystyle \gcd(2u,v)=\gcd(u,v)}
329:{\displaystyle \gcd(u,2v)=\gcd(u,v)}
38:, is an algorithm that computes the
2063:, as a method to reduce fractions:
1649:For arbitrarily-large numbers, the
1307:: The implementation above accepts
545:{\displaystyle \gcd(u,v)=\gcd(v,u)}
165:is the largest number that divides
2477:"A binary recursive gcd algorithm"
2323:Lemire, Daniel (15 October 2019).
2304:Kapoor, Rajiv (21 February 2009).
2032:for fast integer multiplication.
14:
3087:Special number field sieve (SNFS)
3081:General number field sieve (GNFS)
1786:in addition to the GCD: integers
2402:Handbook of Applied Cryptography
2208:Journal of Computational Physics
2112:
1155:"v = {} should be odd"
1119:"u = {} should be odd"
50:, comparisons, and subtraction.
2687:The Art of Computer Programming
2548:Journal of Symbolic Computation
2530:, INRIA Research Report RR-5050
2405:. CRC Press. pp. 606â610.
2260:The Art of Computer Programming
730:except for its exit condition (
145:: everything divides zero, and
2011:
1998:
1955:
1949:
1926:
1914:
1908:
1902:
1876:
1864:
1676:
1663:
1633:
1630:
1618:
1612:
1555:
1549:
1486:
1480:
1364:
1342:
1333:
1321:
639:
627:
618:
603:
574:
562:
539:
527:
518:
506:
427:
409:
400:
388:
323:
311:
302:
287:
242:
230:
215:
197:
126:
114:
1:
2720:Graduate Texts in Mathematics
2444:Graduate Texts in Mathematics
1932:{\displaystyle O(M(n)\log n)}
1167:// Swap if necessary so u †v
376:is then not a common divisor.
3045:Lenstra elliptic curve (ECM)
2753:expansions of real numbers.
2589:10.1007/978-3-540-45077-1_11
2583:, Sweden. pp. 109â117.
2542:Weilert, André (July 2000).
2502:10.1007/978-3-540-24847-7_31
2228:10.1016/0021-9991(67)90047-2
2133:Extended Euclidean algorithm
2030:SchönhageâStrassen algorithm
1780:extended Euclidean algorithm
1778:algorithm, analogous to the
1251:// Identity 1: gcd(u, 0) = u
984:// Using identities 2 and 3:
46:; it replaces division with
3426:Number theoretic algorithms
2616:10.1007/978-3-540-24847-7_4
2120:Computer programming portal
2072:Fangtian â Land surveying,
586:{\displaystyle \gcd(0,v)=v}
138:{\displaystyle \gcd(u,0)=u}
3442:
3352:Exponentiation by squaring
3035:Continued fraction (CFRAC)
2761:(SeptemberâOctober 1998).
2339:"GNU MP 6.1.2: Binary GCD"
2093:if this only applies when
1769:arbitrarily-large integers
36:binary Euclidean algorithm
3399:
2484:Algorithmic number theory
1470:, the algorithm requires
715:expressing the algorithm
2683:Seminumerical Algorithms
2256:Seminumerical Algorithms
2159:(13â15 September 1999).
2017:{\displaystyle O(n^{2})}
1682:{\displaystyle O(n^{2})}
1379:
842:
3265:Greatest common divisor
2610:, USA. pp. 57â71.
2043:, quadratic rings, and
815:{\displaystyle u\leq v}
726:making the loop's body
496:As GCD is commutative (
485:{\displaystyle u\leq v}
40:greatest common divisor
3376:Modular exponentiation
2747:Lehmer's GCD algorithm
2561:10.1006/jsco.2000.0422
2080:
2055:Historical description
2018:
1982:
1962:
1933:
1883:
1820:
1800:
1751:
1683:
1640:
1586:
1562:
1533:
1513:
1493:
1371:
816:
790:
770:
750:
702:
666:
646:
587:
546:
486:
460:
434:
370:
350:
330:
269:
249:
179:
159:
139:
95:
75:
23:
3103:Shanks's square forms
3027:Integer factorization
3002:Sieve of Eratosthenes
2138:Least common multiple
2086:if this applies when
2019:
1983:
1963:
1934:
1884:
1821:
1801:
1752:
1684:
1653:of this algorithm is
1651:asymptotic complexity
1641:
1587:
1563:
1534:
1514:
1494:
1372:
817:
791:
771:
751:
703:
667:
647:
588:
547:
487:
461:
435:
371:
351:
331:
270:
250:
180:
160:
140:
96:
76:
21:
3381:Montgomery reduction
3255:Function field sieve
3230:Baby-step giant-step
3076:Quadratic sieve (QS)
2310:Intel Developer Zone
1992:
1972:
1961:{\displaystyle M(n)}
1943:
1896:
1830:
1810:
1790:
1701:
1657:
1596:
1576:
1561:{\displaystyle O(1)}
1543:
1523:
1503:
1492:{\displaystyle O(n)}
1474:
1315:
800:
780:
760:
734:
710:count trailing zeros
692:
656:
597:
556:
500:
470:
444:
382:
360:
340:
281:
275:is a common divisor.
259:
191:
169:
149:
108:
85:
65:
28:binary GCD algorithm
3391:Trachtenberg system
3357:Integer square root
3298:Modular square root
3017:Wheel factorization
2969:Quadratic Frobenius
2949:LucasâLehmerâRiesel
2845:(1976), a paper by
2803:functional analysis
2743:BĂ©zout coefficients
2662:10.1007/11523468_96
2284:"Compiler Explorer"
2220:1967JCoPh...1..397S
2128:Euclidean algorithm
2099:Euclidean algorithm
2041:Eisenstein integers
1784:BĂ©zout coefficients
1776:extended binary GCD
822:) compiles down to
749:{\displaystyle v=0}
459:{\displaystyle u,v}
44:Euclidean algorithm
3283:Extended Euclidean
3222:Discrete logarithm
3151:SchönhageâStrassen
3007:Sieve of Pritchard
2779:10.1007/PL00009246
2751:continued fraction
2726:. pp. 12â24.
2639:10.1007/11682462_8
2450:. pp. 17â18.
2014:
1978:
1958:
1929:
1879:
1816:
1796:
1747:
1679:
1636:
1582:
1558:
1529:
1509:
1489:
1367:
812:
786:
766:
746:
698:
662:
642:
583:
542:
482:
456:
430:
366:
346:
326:
265:
245:
175:
155:
135:
91:
71:
24:
3413:
3412:
3012:Sieve of Sundaram
2815:transfer operator
2811:invariant measure
2722:. Vol. 138.
2696:978-0-201-89684-8
2511:978-3-540-22156-2
2446:. Vol. 138.
2269:978-0-201-89684-8
2179:(November 1999).
2177:Brent, Richard P.
2157:Brent, Richard P.
2037:Gaussian integers
1981:{\displaystyle n}
1819:{\displaystyle b}
1799:{\displaystyle a}
1741:
1585:{\displaystyle n}
1532:{\displaystyle 2}
1512:{\displaystyle n}
824:conditional moves
789:{\displaystyle v}
769:{\displaystyle u}
701:{\displaystyle 2}
665:{\displaystyle v}
369:{\displaystyle 2}
349:{\displaystyle u}
268:{\displaystyle 2}
178:{\displaystyle u}
158:{\displaystyle u}
94:{\displaystyle v}
74:{\displaystyle u}
48:arithmetic shifts
32:Stein's algorithm
3433:
3362:Integer relation
3335:Other algorithms
3240:Pollard kangaroo
3131:Ancient Egyptian
2989:Prime-generating
2974:SolovayâStrassen
2887:Number-theoretic
2880:
2873:
2866:
2857:
2847:Richard P. Brent
2813:of the system's
2807:dynamical system
2797:
2795:
2789:. Archived from
2759:Vallée, Brigitte
2737:
2700:
2666:
2665:
2649:
2643:
2642:
2626:
2620:
2619:
2599:
2593:
2592:
2572:
2566:
2565:
2563:
2539:
2533:
2531:
2495:
2481:
2473:Zimmermann, Paul
2471:Stehlé, Damien;
2468:
2462:
2461:
2430:
2424:
2423:
2421:
2419:
2398:
2389:
2383:
2377:
2371:
2370:
2369:
2349:
2343:
2342:
2335:
2329:
2328:
2320:
2314:
2313:
2301:
2295:
2294:
2292:
2290:
2279:
2273:
2272:
2248:
2239:
2238:
2203:
2197:
2196:
2194:
2173:
2167:
2166:
2153:
2122:
2117:
2116:
2078:
2023:
2021:
2020:
2015:
2010:
2009:
1987:
1985:
1984:
1979:
1967:
1965:
1964:
1959:
1938:
1936:
1935:
1930:
1888:
1886:
1885:
1880:
1854:
1840:
1825:
1823:
1822:
1817:
1805:
1803:
1802:
1797:
1756:
1754:
1753:
1748:
1746:
1742:
1740:
1733:
1732:
1722:
1721:
1712:
1688:
1686:
1685:
1680:
1675:
1674:
1645:
1643:
1642:
1637:
1608:
1607:
1591:
1589:
1588:
1583:
1567:
1565:
1564:
1559:
1538:
1536:
1535:
1530:
1518:
1516:
1515:
1510:
1498:
1496:
1495:
1490:
1458:
1455:
1452:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1422:
1418:
1415:
1411:
1408:
1405:
1401:
1398:
1395:
1392:
1389:
1386:
1383:
1376:
1374:
1373:
1368:
1360:
1349:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1273:
1270:
1267:
1264:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1234:
1233:// v is now even
1231:
1228:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1144:
1141:
1138:
1135:
1132:
1129:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1105:
1102:
1099:
1096:
1093:
1090:
1087:
1084:
1081:
1078:
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1015:
1012:
1009:
1006:
1003:
1000:
997:
994:
991:
988:
985:
982:
979:
976:
973:
970:
967:
964:
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
931:
928:
925:
922:
919:
915:
912:
908:
905:
902:
899:
895:
892:
889:
886:
883:
880:
877:
874:
870:
866:
863:
860:
857:
853:
849:
846:
821:
819:
818:
813:
795:
793:
792:
787:
775:
773:
772:
767:
755:
753:
752:
747:
707:
705:
704:
699:
671:
669:
668:
663:
651:
649:
648:
643:
592:
590:
589:
584:
551:
549:
548:
543:
491:
489:
488:
483:
465:
463:
462:
457:
439:
437:
436:
431:
375:
373:
372:
367:
355:
353:
352:
347:
335:
333:
332:
327:
274:
272:
271:
266:
254:
252:
251:
246:
184:
182:
181:
176:
164:
162:
161:
156:
144:
142:
141:
136:
100:
98:
97:
92:
80:
78:
77:
72:
30:, also known as
3441:
3440:
3436:
3435:
3434:
3432:
3431:
3430:
3416:
3415:
3414:
3409:
3395:
3330:
3292:
3259:
3216:
3160:
3117:
3021:
2983:
2956:Proth's theorem
2898:Primality tests
2892:
2884:
2853:
2823:
2796:on 13 May 2011.
2793:
2757:
2734:
2724:Springer-Verlag
2708:
2697:
2677:
2674:
2672:Further reading
2669:
2651:
2650:
2646:
2628:
2627:
2623:
2601:
2600:
2596:
2574:
2573:
2569:
2541:
2540:
2536:
2512:
2493:10.1.1.107.8612
2479:
2470:
2469:
2465:
2458:
2448:Springer-Verlag
2432:
2431:
2427:
2417:
2415:
2413:
2396:
2391:
2390:
2386:
2378:
2374:
2351:
2350:
2346:
2337:
2336:
2332:
2322:
2321:
2317:
2303:
2302:
2298:
2288:
2286:
2282:Godbolt, Matt.
2281:
2280:
2276:
2270:
2250:
2249:
2242:
2205:
2204:
2200:
2175:
2174:
2170:
2155:
2154:
2150:
2146:
2118:
2111:
2108:
2079:
2071:
2057:
2001:
1990:
1989:
1970:
1969:
1941:
1940:
1894:
1893:
1828:
1827:
1808:
1807:
1788:
1787:
1765:
1724:
1723:
1713:
1707:
1699:
1698:
1666:
1655:
1654:
1599:
1594:
1593:
1574:
1573:
1541:
1540:
1521:
1520:
1501:
1500:
1472:
1471:
1465:
1460:
1459:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1429:
1426:
1423:
1420:
1416:
1413:
1409:
1406:
1403:
1399:
1396:
1393:
1390:
1387:
1384:
1381:
1313:
1312:
1302:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1151:
1148:
1145:
1142:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1085:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1001:
998:
995:
992:
989:
986:
983:
980:
977:
974:
971:
968:
965:
962:
959:
956:
953:
950:
947:
944:
941:
938:
935:
932:
929:
926:
923:
920:
917:
913:
910:
906:
903:
900:
897:
893:
890:
887:
884:
881:
878:
875:
872:
868:
864:
861:
858:
855:
851:
847:
844:
798:
797:
778:
777:
758:
757:
732:
731:
690:
689:
678:
654:
653:
595:
594:
554:
553:
498:
497:
468:
467:
442:
441:
380:
379:
358:
357:
338:
337:
279:
278:
257:
256:
189:
188:
167:
166:
147:
146:
106:
105:
83:
82:
63:
62:
59:
12:
11:
5:
3439:
3437:
3429:
3428:
3418:
3417:
3411:
3410:
3408:
3407:
3400:
3397:
3396:
3394:
3393:
3388:
3383:
3378:
3373:
3359:
3354:
3349:
3344:
3338:
3336:
3332:
3331:
3329:
3328:
3323:
3318:
3316:TonelliâShanks
3313:
3308:
3302:
3300:
3294:
3293:
3291:
3290:
3285:
3280:
3275:
3269:
3267:
3261:
3260:
3258:
3257:
3252:
3250:Index calculus
3247:
3245:PohligâHellman
3242:
3237:
3232:
3226:
3224:
3218:
3217:
3215:
3214:
3209:
3204:
3199:
3197:Newton-Raphson
3194:
3189:
3184:
3179:
3173:
3171:
3162:
3161:
3159:
3158:
3153:
3148:
3143:
3138:
3133:
3127:
3125:
3123:Multiplication
3119:
3118:
3116:
3115:
3110:
3108:Trial division
3105:
3100:
3095:
3093:Rational sieve
3090:
3083:
3078:
3073:
3065:
3057:
3052:
3047:
3042:
3037:
3031:
3029:
3023:
3022:
3020:
3019:
3014:
3009:
3004:
2999:
2997:Sieve of Atkin
2993:
2991:
2985:
2984:
2982:
2981:
2976:
2971:
2966:
2959:
2952:
2945:
2938:
2933:
2928:
2923:
2921:Elliptic curve
2918:
2913:
2908:
2902:
2900:
2894:
2893:
2885:
2883:
2882:
2875:
2868:
2860:
2851:
2850:
2838:
2829:
2822:
2821:External links
2819:
2799:
2798:
2773:(4): 660â685.
2739:
2738:
2732:
2702:
2701:
2695:
2673:
2670:
2668:
2667:
2644:
2621:
2608:Burlington, VT
2594:
2567:
2554:(5): 605â617.
2534:
2510:
2463:
2456:
2425:
2411:
2384:
2372:
2367:10.1.1.42.7616
2344:
2330:
2315:
2296:
2274:
2268:
2240:
2214:(3): 397â405,
2198:
2195:. PRG TR-7-99.
2168:
2147:
2145:
2142:
2141:
2140:
2135:
2130:
2124:
2123:
2107:
2104:
2103:
2102:
2091:
2069:
2056:
2053:
2013:
2008:
2004:
2000:
1997:
1977:
1957:
1954:
1951:
1948:
1928:
1925:
1922:
1919:
1916:
1913:
1910:
1907:
1904:
1901:
1878:
1875:
1872:
1869:
1866:
1863:
1860:
1857:
1852:
1849:
1846:
1843:
1838:
1835:
1815:
1795:
1764:
1761:
1745:
1739:
1736:
1731:
1727:
1720:
1716:
1710:
1706:
1693:each number's
1678:
1673:
1669:
1665:
1662:
1635:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1606:
1602:
1581:
1557:
1554:
1551:
1548:
1528:
1508:
1488:
1485:
1482:
1479:
1468:Asymptotically
1464:
1461:
1380:
1366:
1363:
1358:
1355:
1352:
1347:
1344:
1341:
1338:
1335:
1332:
1329:
1326:
1323:
1320:
1290:trailing_zeros
1041:trailing_zeros
1008:trailing_zeros
843:
828:
827:
811:
808:
805:
785:
765:
745:
742:
739:
724:
713:
697:
686:trial division
677:
676:Implementation
674:
661:
641:
638:
635:
632:
629:
626:
623:
620:
617:
614:
611:
608:
605:
602:
582:
579:
576:
573:
570:
567:
564:
561:
541:
538:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
494:
493:
481:
478:
475:
455:
452:
449:
429:
426:
423:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
377:
365:
345:
325:
322:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
276:
264:
244:
241:
238:
235:
232:
229:
226:
223:
220:
217:
214:
211:
208:
205:
202:
199:
196:
186:
174:
154:
134:
131:
128:
125:
122:
119:
116:
113:
90:
70:
58:
55:
13:
10:
9:
6:
4:
3:
2:
3438:
3427:
3424:
3423:
3421:
3405:
3402:
3401:
3398:
3392:
3389:
3387:
3384:
3382:
3379:
3377:
3374:
3371:
3367:
3363:
3360:
3358:
3355:
3353:
3350:
3348:
3345:
3343:
3340:
3339:
3337:
3333:
3327:
3324:
3322:
3319:
3317:
3314:
3312:
3311:Pocklington's
3309:
3307:
3304:
3303:
3301:
3299:
3295:
3289:
3286:
3284:
3281:
3279:
3276:
3274:
3271:
3270:
3268:
3266:
3262:
3256:
3253:
3251:
3248:
3246:
3243:
3241:
3238:
3236:
3233:
3231:
3228:
3227:
3225:
3223:
3219:
3213:
3210:
3208:
3205:
3203:
3200:
3198:
3195:
3193:
3190:
3188:
3185:
3183:
3180:
3178:
3175:
3174:
3172:
3170:
3167:
3163:
3157:
3154:
3152:
3149:
3147:
3144:
3142:
3139:
3137:
3134:
3132:
3129:
3128:
3126:
3124:
3120:
3114:
3111:
3109:
3106:
3104:
3101:
3099:
3096:
3094:
3091:
3089:
3088:
3084:
3082:
3079:
3077:
3074:
3072:
3070:
3066:
3064:
3062:
3058:
3056:
3055:Pollard's rho
3053:
3051:
3048:
3046:
3043:
3041:
3038:
3036:
3033:
3032:
3030:
3028:
3024:
3018:
3015:
3013:
3010:
3008:
3005:
3003:
3000:
2998:
2995:
2994:
2992:
2990:
2986:
2980:
2977:
2975:
2972:
2970:
2967:
2965:
2964:
2960:
2958:
2957:
2953:
2951:
2950:
2946:
2944:
2943:
2939:
2937:
2934:
2932:
2929:
2927:
2924:
2922:
2919:
2917:
2914:
2912:
2909:
2907:
2904:
2903:
2901:
2899:
2895:
2891:
2888:
2881:
2876:
2874:
2869:
2867:
2862:
2861:
2858:
2854:
2848:
2844:
2843:
2839:
2837:
2833:
2830:
2828:
2825:
2824:
2820:
2818:
2816:
2812:
2808:
2804:
2792:
2788:
2784:
2780:
2776:
2772:
2768:
2764:
2760:
2756:
2755:
2754:
2752:
2748:
2744:
2735:
2733:0-387-55640-0
2729:
2725:
2721:
2717:
2716:
2711:
2707:
2706:
2705:
2698:
2692:
2688:
2684:
2680:
2679:Knuth, Donald
2676:
2675:
2671:
2663:
2659:
2655:
2648:
2645:
2640:
2636:
2632:
2625:
2622:
2617:
2613:
2609:
2605:
2598:
2595:
2590:
2586:
2582:
2578:
2571:
2568:
2562:
2557:
2553:
2549:
2545:
2538:
2535:
2529:
2525:
2521:
2517:
2513:
2507:
2503:
2499:
2494:
2489:
2485:
2478:
2474:
2467:
2464:
2459:
2457:0-387-55640-0
2453:
2449:
2445:
2441:
2440:
2435:
2429:
2426:
2414:
2412:0-8493-8523-7
2408:
2404:
2403:
2395:
2388:
2385:
2381:
2376:
2373:
2368:
2363:
2359:
2355:
2348:
2345:
2340:
2334:
2331:
2326:
2319:
2316:
2311:
2307:
2300:
2297:
2285:
2278:
2275:
2271:
2265:
2261:
2257:
2253:
2252:Knuth, Donald
2247:
2245:
2241:
2237:
2233:
2229:
2225:
2221:
2217:
2213:
2209:
2202:
2199:
2193:
2188:
2184:
2183:
2178:
2172:
2169:
2164:
2163:
2158:
2152:
2149:
2143:
2139:
2136:
2134:
2131:
2129:
2126:
2125:
2121:
2115:
2110:
2105:
2100:
2096:
2092:
2089:
2085:
2084:
2083:
2077:
2076:
2068:
2064:
2062:
2054:
2052:
2050:
2049:number fields
2046:
2045:integer rings
2042:
2038:
2033:
2031:
2027:
2006:
2002:
1995:
1975:
1952:
1946:
1923:
1920:
1917:
1911:
1905:
1899:
1890:
1873:
1870:
1867:
1858:
1855:
1850:
1847:
1844:
1841:
1836:
1833:
1813:
1793:
1785:
1781:
1777:
1772:
1770:
1762:
1760:
1757:
1743:
1737:
1734:
1729:
1725:
1718:
1714:
1708:
1704:
1696:
1692:
1671:
1667:
1660:
1652:
1647:
1627:
1624:
1621:
1609:
1604:
1600:
1579:
1571:
1552:
1546:
1526:
1506:
1499:steps, where
1483:
1477:
1469:
1462:
1378:
1361:
1356:
1353:
1350:
1345:
1336:
1330:
1327:
1324:
1310:
1306:
1131:debug_assert!
1095:debug_assert!
841:
839:
838:
833:
825:
809:
806:
803:
783:
763:
743:
740:
737:
729:
725:
722:
718:
714:
711:
695:
687:
683:
682:
681:
675:
673:
672:is odd, etc.
659:
636:
633:
630:
621:
615:
612:
609:
606:
580:
577:
571:
568:
565:
536:
533:
530:
521:
515:
512:
509:
479:
476:
473:
453:
450:
447:
424:
421:
418:
415:
412:
403:
397:
394:
391:
378:
363:
343:
320:
317:
314:
305:
299:
296:
293:
290:
277:
262:
239:
236:
233:
224:
221:
218:
212:
209:
206:
203:
200:
187:
172:
152:
132:
129:
123:
120:
117:
104:
103:
102:
88:
68:
56:
54:
51:
49:
45:
41:
37:
33:
29:
20:
16:
3403:
3272:
3085:
3068:
3060:
2979:MillerâRabin
2961:
2954:
2947:
2942:LucasâLehmer
2940:
2852:
2841:
2836:cut-the-knot
2800:
2791:the original
2770:
2767:Algorithmica
2766:
2740:
2714:
2710:Cohen, Henri
2703:
2682:
2653:
2647:
2630:
2624:
2603:
2597:
2576:
2570:
2551:
2547:
2537:
2483:
2466:
2438:
2434:Cohen, Henri
2428:
2416:. Retrieved
2401:
2387:
2375:
2357:
2347:
2333:
2318:
2309:
2299:
2287:. Retrieved
2277:
2255:
2211:
2207:
2201:
2181:
2171:
2161:
2151:
2094:
2087:
2081:
2073:
2066:
2058:
2034:
2025:
1968:the cost of
1891:
1775:
1773:
1766:
1758:
1694:
1690:
1648:
1466:
1451:unsigned_abs
1439:unsigned_abs
1308:
1304:
1303:
836:
829:
719:rather than
679:
495:
60:
52:
35:
31:
27:
25:
15:
3235:Pollard rho
3192:Goldschmidt
2926:Pocklington
2916:BaillieâPSW
2418:9 September
2360:: 373â387,
2061:Han dynasty
728:branch-free
721:recursively
717:iteratively
3347:Cornacchia
3342:Chakravala
2890:algorithms
2380:Knuth 1998
2289:4 February
2144:References
1826:such that
1763:Extensions
1570:word-sized
1463:Complexity
1394:signed_gcd
796:(ensuring
684:eschewing
3321:Berlekamp
3278:Euclidean
3166:Euclidean
3146:ToomâCook
3141:Karatsuba
2488:CiteSeerX
2362:CiteSeerX
2236:0021-9991
2192:1303.2772
1921:
1851:⋅
1837:⋅
1735:
1610:
1357:±
1346:±
1281:>>=
1050:>>=
1017:>>=
807:≤
477:≤
422:−
225:⋅
57:Algorithm
3420:Category
3288:Lehmer's
3182:Chunking
3169:division
3098:Fermat's
2787:27441335
2475:(2004),
2254:(1998),
2106:See also
2070:â
1309:unsigned
1263:<<
466:odd and
356:is odd:
3404:Italics
3326:Kunerth
3306:Cipolla
3187:Fourier
3156:FĂŒrer's
3050:Euler's
3040:Dixon's
2963:PĂ©pin's
2528:3119374
2520:2138011
2216:Bibcode
1939:, with
1592:, i.e.
34:or the
3386:Schoof
3273:Binary
3177:Binary
3113:Shor's
2931:Fermat
2785:
2730:
2693:
2526:
2518:
2508:
2490:
2454:
2409:
2364:
2266:
2234:
2088:either
1419:->
1257:return
972:return
942:return
916:->
837:uutils
3207:Short
2936:Lucas
2783:S2CID
2581:Malmö
2524:S2CID
2480:(PDF)
2397:(PDF)
2187:arXiv
1203:&
1191:&
3202:Long
3136:Long
2794:(PS)
2728:ISBN
2691:ISBN
2506:ISBN
2452:ISBN
2420:2017
2407:ISBN
2291:2024
2264:ISBN
2232:ISSN
2095:both
2026:i.e.
1806:and
1774:The
1695:size
1691:i.e.
1305:Note
1185:swap
1176:>
1086:loop
954:else
873:swap
832:Rust
776:and
81:and
26:The
3366:LLL
3212:SRT
3071:+ 1
3063:â 1
2911:APR
2906:AKS
2834:at
2775:doi
2658:doi
2635:doi
2612:doi
2585:doi
2556:doi
2498:doi
2224:doi
2047:of
1918:log
1862:gcd
1726:log
1616:max
1601:log
1454:())
1442:(),
1427:gcd
1421:u64
1414:i64
1404:i64
1388:pub
1340:gcd
1319:gcd
1293:();
1206:mut
1194:mut
1068:min
1059:let
1044:();
1026:let
1011:();
993:let
918:u64
911:u64
904:mut
898:u64
891:mut
885:gcd
879:pub
869:mem
865:std
862:use
856:min
852:cmp
848:std
845:use
688:by
652:if
625:gcd
601:gcd
560:gcd
525:gcd
504:gcd
440:if
407:gcd
386:gcd
336:if
309:gcd
285:gcd
228:gcd
195:gcd
112:gcd
3422::
3370:KZ
3368:;
2817:.
2781:.
2771:22
2769:.
2765:.
2718:.
2685:.
2552:30
2550:.
2546:.
2522:,
2516:MR
2514:,
2504:,
2496:,
2482:,
2442:.
2399:.
2356:,
2308:.
2258:,
2243:^
2230:,
2222:,
2210:,
2051:.
2039:,
1889:.
1646:.
1412::
1402::
1391:fn
1242:==
1236:if
1224:-=
1212:);
1170:if
1164:);
1146:==
1128:);
1110:==
1083:);
963:==
957:if
933:==
927:if
909::
896::
882:fn
871:::
867:::
854:::
850:::
840::
593:,
255::
3372:)
3364:(
3069:p
3061:p
2879:e
2872:t
2865:v
2777::
2736:.
2699:.
2664:.
2660::
2641:.
2637::
2618:.
2614::
2591:.
2587::
2564:.
2558::
2532:.
2500::
2460:.
2422:.
2341:.
2327:.
2312:.
2293:.
2226::
2218::
2212:1
2189::
2101:.
2012:)
2007:2
2003:n
1999:(
1996:O
1976:n
1956:)
1953:n
1950:(
1947:M
1927:)
1924:n
1915:)
1912:n
1909:(
1906:M
1903:(
1900:O
1877:)
1874:v
1871:,
1868:u
1865:(
1859:=
1856:v
1848:b
1845:+
1842:u
1834:a
1814:b
1794:a
1744:)
1738:n
1730:2
1719:2
1715:n
1709:(
1705:O
1677:)
1672:2
1668:n
1664:(
1661:O
1634:)
1631:)
1628:v
1625:,
1622:u
1619:(
1613:(
1605:2
1580:n
1556:)
1553:1
1550:(
1547:O
1527:2
1507:n
1487:)
1484:n
1481:(
1478:O
1457:}
1448:.
1445:v
1436:.
1433:u
1430:(
1424:{
1417:)
1410:v
1407:,
1400:u
1397:(
1365:)
1362:v
1354:,
1351:u
1343:(
1337:=
1334:)
1331:v
1328:,
1325:u
1322:(
1299:}
1296:}
1287:.
1284:v
1278:v
1272:}
1269:;
1266:k
1260:u
1248:{
1245:0
1239:v
1230:;
1227:u
1221:v
1215:}
1209:v
1200:,
1197:u
1188:(
1182:{
1179:v
1173:u
1161:v
1158:,
1152:,
1149:1
1143:2
1140:%
1137:v
1134:(
1125:u
1122:,
1116:,
1113:1
1107:2
1104:%
1101:u
1098:(
1089:{
1080:j
1077:,
1074:i
1071:(
1065:=
1062:k
1056:;
1053:j
1047:v
1038:.
1035:v
1032:=
1029:j
1023:;
1020:i
1014:u
1005:.
1002:u
999:=
996:i
981:}
978:;
975:u
969:{
966:0
960:v
951:}
948:;
945:v
939:{
936:0
930:u
921:{
914:)
907:v
901:,
894:u
888:(
876:;
859:;
810:v
804:u
784:v
764:u
744:0
741:=
738:v
696:2
660:v
640:)
637:v
634:,
631:u
628:(
622:=
619:)
616:v
613:,
610:u
607:2
604:(
581:v
578:=
575:)
572:v
569:,
566:0
563:(
540:)
537:u
534:,
531:v
528:(
522:=
519:)
516:v
513:,
510:u
507:(
492:.
480:v
474:u
454:v
451:,
448:u
428:)
425:u
419:v
416:,
413:u
410:(
404:=
401:)
398:v
395:,
392:u
389:(
364:2
344:u
324:)
321:v
318:,
315:u
312:(
306:=
303:)
300:v
297:2
294:,
291:u
288:(
263:2
243:)
240:v
237:,
234:u
231:(
222:2
219:=
216:)
213:v
210:2
207:,
204:u
201:2
198:(
185:.
173:u
153:u
133:u
130:=
127:)
124:0
121:,
118:u
115:(
89:v
69:u
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
