84:
25:
814:
527:
In: an integer x; an integer n Out: x exp_by_squaring(x, n) if n < 0 then return exp_by_squaring(1 / x, -n); else if n = 0 then return 1; else if n is even then return exp_by_squaring(x * x, n / 2); else if n is odd then return x * exp_by_squaring(x * x, (n
448:
2537:: memory access latencies might still be observable to an attacker, as different variables are accessed depending on the value of bits of the secret exponent. Modern cryptographic implementations use a "scatter" technique to make sure the processor always misses the faster cache.
3484:
1771:
282:
2144:, we take a window of length 3 using the 2-ary method algorithm and calculate 1, x, x, x, x, x, x, x, x, x, x, x. But, we can also compute 1, x, x, x, x, x, x, x, x, x, which saves one multiplication and amounts to evaluating (110 001 110)
6004:
algorithms that, while not being optimal, have fewer multiplications than exponentiation by squaring at the cost of additional bookkeeping work and memory usage. Regardless, the number of multiplications never grows more slowly than
4537:(that is, a multiplication followed by a division with remainder) leads to only 27 multiplications and divisions of integers, which may all be stored in a single machine word. Generally, any of these approaches will take fewer than
629:
5571:
2949:
614:
The algorithms of the next section use a different approach, and the resulting algorithms needs the same number of operations, but use an auxiliary memory that is roughly the same as the memory required to store the result.
4796:
2389:. Namely, an attacker observing the sequence of squarings and multiplications can (partially) recover the exponent involved in the computation. This is a problem if the exponent should remain secret, as with many
2130:
3542:
4023:
5717:
5166:
5288:
516:
611:. This implies that it requires an amount of auxiliary memory that is roughly proportional to the number of recursive calls -- or perhaps higher if the amount of data per iteration is increasing.
5055:
4992:
5901:
5225:
5650:
5363:
3326:
2675:
5982:
4121:
3860:
4190:
3733:
2285:
1960:
4289:
1559:
1520:
579:
4922:
1626:
3927:
2717:
4863:
4350:
1583:
1431:
5772:
5415:
2530:): a multiplication and squaring takes place for each bit in the exponent, regardless of the bit's specific value. A similar algorithm for multiplication by doubling exists.
5996:
addition chain for a given exponent is a hard problem, for which no efficient algorithms are known, so optimal chains are typically used for small exponents only (e.g. in
6103:
5084:
4225:
1470:
5451:
4062:
1385:
277:
3784:
3640:
3308:
3230:
2761:
3260:
3194:
3160:
3122:
3092:
809:{\displaystyle yx^{n}={\begin{cases}(yx)\,(x^{2})^{(n-1)/2},&{\mbox{if }}n{\mbox{ is odd}}\\y\,(x^{2})^{n/2},&{\mbox{if }}n{\mbox{ is even}}.\end{cases}}}
3660:
3613:
4511:
when divided by 2345 were used. Even using a more effective method will take a long time: square 13789, take the remainder when divided by 2345, multiply the
1475:
These algorithms use exactly the same number of operations as the algorithm of the preceding section, but the multiplications are done in a different order.
5472:
456:
is zero then the answer is 1. If the exponent is negative then we can reuse the previous formula by rewriting the value using a positive exponent. That is,
5812:), one can sometimes perform the exponentiation using fewer multiplications (but typically using more memory). The smallest power where this occurs is for
2788:
101:
443:{\displaystyle x^{n}={\begin{cases}x\,(x^{2})^{(n-1)/2},&{\mbox{if }}n{\mbox{ is odd}}\\(x^{2})^{n/2},&{\mbox{if }}n{\mbox{ is even}}\end{cases}}}
6243:
4697:
459:
4628:
In certain computations it may be more efficient to allow negative coefficients and hence use the inverse of the base, provided inversion in
2140:
This method is an efficient variant of the 2-ary method. For example, to calculate the exponent 398, which has binary expansion (110 001 110)
2030:
3492:
148:
6155:
120:
3935:
6138:
6032:
5094:, we are interested in finding the signed-binary representation with the smallest number of non-zero entries, that is, the one with
167:
65:
5108:
127:
5290:. This representation always has minimal Hamming weight. A simple algorithm to compute the NAF representation of a given integer
5230:
2394:
47:
105:
134:
5789:
5783:
589:. So this algorithm computes this number of squares and a lower number of multiplication, which is equal to the number of
5657:
6248:
4997:
4934:
3479:{\displaystyle x_{0}^{n_{0}}\cdot x_{1}^{n_{1}}=\left(x_{0}\cdot x_{1}^{q}\right)^{n_{0}}\cdot x_{1}^{n_{1}\mod n_{0}},}
521:
5822:
5171:
116:
4680:
1601:
greater than about 4 this is computationally more efficient than naively multiplying the base with itself repeatedly.
5293:
1604:
Each squaring results in approximately double the number of digits of the previous, and so, if multiplication of two
43:
2607:
5908:
4924:. There are several methods for computing this representation. The representation is not unique. For example, take
4072:
3792:
4132:
94:
6013:), so these algorithms improve asymptotically upon exponentiation by squaring by only a constant factor at best.
5577:
3665:
2212:
1887:
1766:{\displaystyle \sum \limits _{i=0}^{O(\log n)}{\big (}2^{i}O(\log x){\big )}^{k}=O{\big (}(n\log x)^{k}{\big )}.}
4236:
1525:
1486:
6027:
542:
4868:
5090:. Since the binary method computes a multiplication for every non-zero entry in the base-2 representation of
3868:
2390:
2683:
6022:
4475:
4814:
4303:
35:
6238:
1564:
1390:
532:
141:
5725:
5368:
4606:
185:
654:
597:. This logarithmic number of operations is to be compared with the trivial algorithm which requires
304:
4549:
4471:
3320:
is a natural integer, whose algorithm is given below, is using the following equality recursively:
2386:
1589:. More precisely, the number of multiplications is one less than the number of ones present in the
6214:
6068:
4487:
4483:
221:
5060:
4198:
1436:
6134:
6037:
5102:
4617:
6105:
need be computed, and only those specifically involved in the computation need be considered.
5423:
4034:
6206:
6170:
2401:
1590:
1360:
1134:
The iterative version of the algorithm also uses a bounded auxiliary space, and is given by
256:
193:
6000:
where the chains for small powers have been pre-tabulated). However, there are a number of
3745:
3618:
3286:
3203:
2722:
4613:
4602:
3239:
3173:
3139:
3101:
3071:
6042:
6006:
5796:
consisting of repeated exponent doublings (squarings) and/or incrementing exponents by
5793:
5098:
3645:
3598:
2550:
2533:
This specific implementation of
Montgomery's ladder is not yet protected against cache
1586:
229:
6175:
5566:{\displaystyle c_{i+1}=\left\lfloor {\frac {1}{2}}(c_{i}+n_{i}+n_{i+1})\right\rfloor }
6232:
2944:{\displaystyle x^{n}=\prod _{i=0}^{w-1}x_{i}^{n_{i}}=\prod _{j=1}^{h-1}{\bigg }^{j}.}
2534:
225:
209:
4503:
would take a very long time and much storage space if the naïve method of computing
6218:
4479:
233:
6061:
In this line, the loop finds the longest string of length less than or equal to
181:
83:
6210:
205:
5722:
Another algorithm by Koyama and
Tsuruoka does not require the condition that
6001:
4612:
More generally, the approach works with positive integer exponents in every
4508:
4467:
608:
201:
5808:
previously computed exponents to be summed (by multiplying those powers of
4791:{\displaystyle n=\sum _{i=0}^{l-1}n_{i}b^{i}{\text{ with }}|n_{i}|<b.}
5997:
3278:
Efficient exponentiation using precomputation and vector addition chains
6191:
1789:
in 1939. In the algorithm below we make use of the following function
6133:. Discrete Mathematics and Its Applications. Chapman & Hall/CRC.
4512:
2125:{\displaystyle \lg n<{\frac {k(k+1)\cdot 2^{2k}}{2^{k+1}-k-2}}+1.}
1786:
197:
48:
talk:Exponentiation by squaring § Least significant bit is first
3537:{\displaystyle q=\left\lfloor {\frac {n_{1}}{n_{0}}}\right\rfloor }
6156:"Speeding the Pollard and Elliptic Curve Methods of Factorization"
3198:
times with the next highest powers, and so on. The algorithm uses
2523:
2385:
Many algorithms for exponentiation do not provide defence against
1785:
after expanding the exponent in base 2. It was first proposed by
2572:
and the computation is as performed in the algorithm above. Let
2549:
when the base is fixed and the exponent varies. As one can see,
623:
The variants described in this section are based on the formula
5101:. One method of doing this is to compute the representation in
4634:
is "fast" or has been precomputed. For example, when computing
4018:{\displaystyle \forall i\in {\big (}-M{\big )},n_{N}\geq n_{i}}
6192:"Efficient software implementations of modular exponentiation"
582:
77:
18:
4548:
The approach can also be used to compute integer powers in a
4164:
2966:
written in the above form, along with the precomputed values
2545:
There are several methods which can be employed to calculate
539:
is removed. It follows that the number of recursive calls is
520:
Together, these may be implemented directly as the following
253:
The method is based on the observation that, for any integer
5161:{\displaystyle n_{i}n_{i+1}=0{\text{ for all }}i\geqslant 0}
1357:
The correctness of the algorithm results from the fact that
531:
In each recursive call, the least significant digits of the
5283:{\displaystyle (1000{\bar {1}}000{\bar {1}}0)_{\text{NAF}}}
802:
436:
6065:
ending in a non-zero value. Not all odd powers of 2 up to
4931:: two distinct signed-binary representations are given by
819:
If one applies recursively this formula, by starting with
6131:
Handbook of
Elliptic and Hyperelliptic Curve Cryptography
5788:
Exponentiation by squaring can be viewed as a suboptimal
511:{\displaystyle x^{n}=\left({\frac {1}{x}}\right)^{-n}\,.}
3544:. In other words, a Euclidean division of the exponent
2522:
The algorithm performs a fixed sequence of operations (
4356:
The algorithm first finds the largest value among the
833:
This may be implemented as a tail-recursive function:
790:
780:
729:
719:
427:
417:
370:
360:
6071:
5911:
5825:
5728:
5660:
5580:
5475:
5426:
5371:
5296:
5233:
5174:
5111:
5063:
5000:
4937:
4871:
4817:
4700:
4306:
4239:
4201:
4135:
4075:
4037:
3938:
3871:
3795:
3748:
3668:
3648:
3621:
3601:
3495:
3329:
3289:
3242:
3206:
3176:
3142:
3104:
3074:
2791:
2725:
2686:
2610:
2215:
2033:
1890:
1629:
1567:
1528:
1489:
1439:
1393:
1363:
632:
545:
462:
285:
259:
2565:-ary method where the exponent is expanded in radix
220:. These can be of quite general use, for example in
5712:{\displaystyle (n_{l-1}'\dots n_{0}')_{\text{NAF}}}
1483:A brief analysis shows that such an algorithm uses
108:. Unsourced material may be challenged and removed.
6097:
5976:
5895:
5766:
5711:
5644:
5565:
5445:
5409:
5357:
5282:
5219:
5160:
5078:
5050:{\displaystyle (100{\bar {1}}1000{\bar {1}}0)_{s}}
5049:
4987:{\displaystyle (10{\bar {1}}1100{\bar {1}}10)_{s}}
4986:
4916:
4857:
4790:
4605:semigroups and is often used to compute powers of
4344:
4283:
4219:
4184:
4115:
4056:
4017:
3921:
3854:
3778:
3727:
3654:
3634:
3607:
3536:
3478:
3302:
3254:
3224:
3188:
3154:
3116:
3086:
2943:
2755:
2711:
2669:
2279:
2124:
1954:
1765:
1577:
1553:
1514:
1464:
1425:
1379:
830:, and the desired result is then the left factor.
808:
573:
510:
442:
271:
224:or powering of matrices. For semigroups for which
192:is a general method for fast computation of large
5896:{\displaystyle x^{15}=x\times (x\times ^{2})^{2}}
5220:{\displaystyle (n_{l-1}\dots n_{0})_{\text{NAF}}}
4474:, for example allowing fast computation of large
2927:
2886:
5984: (optimal addition chain, 5 multiplies if
5227:. For example, the NAF representation of 478 is
5105:, or NAF for short, which is one that satisfies
5358:{\displaystyle n=(n_{l}n_{l-1}\dots n_{0})_{2}}
2670:{\displaystyle n=\sum _{i=0}^{w-1}n_{i}b_{i},}
5977:{\displaystyle x^{15}=x^{3}\times (^{2})^{2}}
4116:{\displaystyle q=\lfloor n_{M}/n_{N}\rfloor }
3984:
3950:
3914:
3880:
3855:{\displaystyle \forall i\in ,n_{M}\geq n_{i}}
3276:The Euclidean method was first introduced in
1755:
1723:
1704:
1668:
8:
4852:
4831:
4185:{\displaystyle n_{N}=(n_{M}{\bmod {n}}_{N})}
4110:
4082:
1572:
1568:
1548:
1529:
1509:
1490:
565:
546:
212:. Some variants are commonly referred to as
5645:{\displaystyle n_{i}'=c_{i}+n_{i}-2c_{i+1}}
3728:{\displaystyle x^{b_{0}},...,x^{b_{l_{i}}}}
2280:{\displaystyle x^{3},x^{5},...,x^{2^{k}-1}}
1955:{\displaystyle x^{3},x^{5},...,x^{2^{k}-1}}
1387:is invariant during the computation; it is
826:, one gets eventually an exponent equal to
5792:algorithm: it computes the exponent by an
4284:{\displaystyle x_{N}=x_{N}\cdot x_{M}^{q}}
2024:should be the smallest integer satisfying
1571:
1554:{\displaystyle \lfloor \log _{2}n\rfloor }
1515:{\displaystyle \lfloor \log _{2}n\rfloor }
6174:
6081:
6076:
6070:
5968:
5958:
5948:
5929:
5916:
5910:
5887:
5877:
5867:
5830:
5824:
5774:; it still minimizes the Hamming weight.
5746:
5733:
5727:
5703:
5690:
5668:
5659:
5630:
5614:
5601:
5585:
5579:
5543:
5530:
5517:
5500:
5480:
5474:
5431:
5425:
5389:
5376:
5370:
5349:
5339:
5320:
5310:
5295:
5274:
5256:
5255:
5241:
5240:
5232:
5211:
5201:
5182:
5173:
5144:
5126:
5116:
5110:
5065:
5064:
5062:
5041:
5023:
5022:
5008:
5007:
4999:
4978:
4960:
4959:
4945:
4944:
4936:
4908:
4898:
4879:
4870:
4822:
4816:
4774:
4768:
4759:
4754:
4748:
4738:
4722:
4711:
4699:
4334:
4329:
4324:
4311:
4305:
4275:
4270:
4257:
4244:
4238:
4211:
4206:
4200:
4173:
4167:
4163:
4156:
4140:
4134:
4104:
4095:
4089:
4074:
4042:
4036:
4009:
3996:
3983:
3982:
3949:
3948:
3937:
3913:
3912:
3879:
3878:
3870:
3846:
3833:
3794:
3747:
3715:
3710:
3705:
3678:
3673:
3667:
3647:
3626:
3620:
3600:
3522:
3512:
3506:
3494:
3465:
3460:
3459:
3449:
3444:
3439:
3424:
3419:
3408:
3403:
3390:
3369:
3364:
3359:
3344:
3339:
3334:
3328:
3294:
3288:
3241:
3205:
3175:
3141:
3103:
3073:
2980:is calculated using the algorithm below:
2932:
2926:
2925:
2918:
2900:
2895:
2885:
2884:
2872:
2861:
2846:
2841:
2836:
2820:
2809:
2796:
2790:
2724:
2697:
2685:
2658:
2648:
2632:
2621:
2609:
2263:
2258:
2233:
2220:
2214:
2089:
2074:
2046:
2032:
1938:
1933:
1908:
1895:
1889:
1754:
1753:
1747:
1722:
1721:
1709:
1703:
1702:
1677:
1667:
1666:
1645:
1634:
1628:
1566:
1536:
1527:
1497:
1488:
1447:
1438:
1417:
1404:
1392:
1371:
1362:
789:
779:
764:
760:
750:
742:
728:
718:
703:
687:
677:
669:
649:
640:
631:
574:{\displaystyle \lceil \log _{2}n\rceil ,}
553:
544:
504:
495:
481:
467:
461:
426:
416:
401:
397:
387:
369:
359:
344:
328:
318:
310:
299:
290:
284:
258:
168:Learn how and when to remove this message
66:Learn how and when to remove this message
4917:{\displaystyle (n_{l-1}\dots n_{0})_{s}}
4367:and then the supremum within the set of
3615:written as in Yao's method, the element
2373:y := y * x i := s - 1
6118:
6054:
3922:{\displaystyle N\in {\big (}-M{\big )}}
1781:This algorithm calculates the value of
200:, or more generally of an element of a
6124:
6122:
5804:) only. More generally, if one allows
4654:squarings. However, one could perform
4482:, it is useful to compute powers in a
3013:u = u × x y = y × u j = j - 1
46:. There is a discussion about this on
4804:corresponds to the particular choice
3096:; in the next round those with power
2782:Then the algorithm uses the equality
2712:{\displaystyle 0\leqslant n_{i}<h}
2553:play a key role in these algorithms.
236:, this method is also referred to as
7:
6199:Journal of Cryptographic Engineering
2333:s := max{i - k + 1, 0}
2001:y := y y := y * x
106:adding citations to reliable sources
4858:{\displaystyle n_{i}\in \{-1,0,1\}}
4522:algorithm, with "*" interpreted as
4425:the result of this computation and
4345:{\displaystyle x^{n}=x_{M}^{n_{M}}}
3455:
3264:elements must be stored to compute
2209:> 0 and the pre-computed values
1631:
1616:, then the complexity of computing
1608:-digit numbers is implemented in O(
6129:Cohen, H.; Frey, G., eds. (2006).
4616:for which the binary operation is
3939:
3796:
2561:Yao's method is orthogonal to the
1578:{\displaystyle \lfloor \;\rfloor }
1426:{\displaystyle 1\cdot x^{n}=x^{n}}
14:
6176:10.1090/S0025-5718-1987-0866113-7
6033:Montgomery modular multiplication
4493:. For example, the evaluation of
3066:that appear to the highest power
2329:y := y' i := i - 1
16:Algorithm for fast exponentiation
5903: (squaring, 6 multiplies),
5778:Alternatives and generalizations
3047:values are simply the digits of
2404:of a positive, non-zero integer
2397:ladder" addresses this concern.
2380:
2357:y := y u := (n
2013:y := y i := i - 1
593:in the binary representation of
585:of the binary representation of
82:
23:
5767:{\displaystyle n_{i}=n_{i+1}=0}
5410:{\displaystyle n_{l}=n_{l-1}=0}
2150:Here is the general algorithm:
1985:i ≥ 0 do (s, u) := f(n
1847:> 0, a non-negative integer
93:needs additional citations for
6244:Computer arithmetic algorithms
5965:
5955:
5941:
5938:
5884:
5874:
5854:
5845:
5700:
5661:
5555:
5510:
5346:
5303:
5271:
5261:
5246:
5234:
5208:
5175:
5070:
5038:
5028:
5013:
5001:
4975:
4965:
4950:
4938:
4905:
4872:
4775:
4760:
4179:
4149:
3973:
3955:
3903:
3885:
3823:
3805:
3773:
3755:
3735:and then the algorithm below.
2750:
2732:
2064:
2052:
1744:
1728:
1698:
1686:
1661:
1649:
757:
743:
700:
688:
684:
670:
666:
657:
619:With constant auxiliary memory
394:
380:
341:
329:
325:
311:
1:
6190:Gueron, Shay (5 April 2012).
6154:Montgomery, Peter L. (1987).
5790:addition-chain exponentiation
5784:Addition-chain exponentiation
4640:, the binary method requires
4466:The approach also works with
4403:, multiplies this value with
3562:is used to return a quotient
2381:Montgomery's ladder technique
2310:y := 1; i := l - 1
1981:y := 1; i := l - 1
4802:Signed binary representation
4552:, using either of the rules
1612:) operations for some fixed
1433:at the beginning; and it is
117:"Exponentiation by squaring"
6098:{\displaystyle x^{2^{k}-1}}
4681:signed-digit representation
4601:The approach also works in
3055:. Yao's method collects in
1884:and the precomputed values
6265:
5781:
5079:{\displaystyle {\bar {1}}}
4679:To this end we define the
3283:This method for computing
3130:as well etc. The variable
528:- 1) / 2); end function
190:exponentiating by squaring
6211:10.1007/s13389-012-0031-5
4545:modular multiplications.
4220:{\displaystyle x_{M}^{q}}
2168:, a non negative integer
1465:{\displaystyle yx^{1}=xy}
1142:exp_by_squaring_iterative
6028:Vectorial addition chain
5992:In general, finding the
4478:a number. Especially in
2983:y = 1, u = 1, j = h - 1
2391:public-key cryptosystems
2345:s := s + 1
2020:For optimal efficiency,
1479:Computational complexity
1136:
835:
5446:{\displaystyle c_{0}=0}
4498:13789 (mod 2345) = 2029
4057:{\displaystyle n_{N}=0}
3585:Given the base element
3164:times with the initial
1561:multiplications, where
228:is commonly used, like
6099:
6023:Modular exponentiation
5978:
5897:
5768:
5713:
5646:
5567:
5447:
5411:
5359:
5284:
5221:
5162:
5080:
5051:
4988:
4918:
4859:
4792:
4733:
4346:
4285:
4221:
4186:
4117:
4058:
4019:
3923:
3856:
3780:
3729:
3656:
3636:
3609:
3538:
3480:
3304:
3256:
3226:
3190:
3156:
3118:
3088:
2945:
2883:
2831:
2757:
2713:
2671:
2643:
2556:
2393:. A technique called "
2281:
2126:
1956:
1767:
1665:
1579:
1555:
1522:squarings and at most
1516:
1466:
1427:
1381:
1380:{\displaystyle yx^{n}}
810:
607:This algorithm is not
575:
512:
444:
273:
272:{\displaystyle n>0}
6100:
5979:
5898:
5769:
5714:
5647:
5568:
5448:
5412:
5360:
5285:
5222:
5163:
5081:
5052:
4989:
4919:
4860:
4793:
4707:
4664:and then multiply by
4624:Signed-digit recoding
4515:by 13789, and so on.
4347:
4286:
4222:
4187:
4118:
4059:
4020:
3924:
3857:
3781:
3779:{\displaystyle M\in }
3730:
3657:
3637:
3635:{\displaystyle x^{n}}
3610:
3539:
3481:
3305:
3303:{\displaystyle x^{n}}
3257:
3234:multiplications, and
3227:
3225:{\displaystyle w+h-2}
3191:
3157:
3119:
3089:
2946:
2857:
2805:
2758:
2756:{\displaystyle i\in }
2714:
2672:
2617:
2282:
2136:Sliding-window method
2127:
1957:
1768:
1630:
1580:
1556:
1517:
1467:
1428:
1382:
811:
576:
533:binary representation
513:
445:
274:
218:binary exponentiation
6069:
5909:
5823:
5726:
5658:
5578:
5473:
5424:
5369:
5294:
5231:
5172:
5109:
5061:
4998:
4935:
4869:
4815:
4698:
4647:multiplications and
4507:and then taking the
4462:Further applications
4304:
4237:
4199:
4195:Compute recursively
4133:
4073:
4035:
3936:
3869:
3793:
3746:
3666:
3646:
3642:is calculated using
3619:
3599:
3493:
3327:
3287:
3240:
3204:
3174:
3140:
3102:
3072:
2789:
2723:
2684:
2608:
2436:= 1, we can compute
2387:side-channel attacks
2213:
2031:
1888:
1627:
1565:
1526:
1487:
1437:
1391:
1361:
630:
543:
460:
283:
257:
186:computer programming
102:improve this article
36:confusing or unclear
6249:Computer arithmetic
5698:
5682:
5593:
5146: for all
4865:. It is denoted by
4543:(722340) ≤ 40
4472:characteristic zero
4414:, and then assigns
4341:
4280:
4216:
3662:precomputed values
3595:, and the exponent
3472:
3413:
3376:
3351:
3255:{\displaystyle w+1}
3189:{\displaystyle h-2}
3155:{\displaystyle h-1}
3117:{\displaystyle h-2}
3087:{\displaystyle h-1}
2962:, and the exponent
2853:
2541:Fixed-base exponent
522:recursive algorithm
214:square-and-multiply
44:clarify the article
6095:
5974:
5893:
5764:
5709:
5686:
5664:
5642:
5581:
5563:
5443:
5417:is the following:
5407:
5355:
5280:
5217:
5158:
5086:is used to denote
5076:
5047:
4984:
4914:
4855:
4788:
4342:
4320:
4281:
4266:
4217:
4202:
4182:
4113:
4054:
4015:
3919:
3852:
3776:
3725:
3652:
3632:
3605:
3534:
3476:
3435:
3399:
3355:
3330:
3300:
3252:
3222:
3186:
3152:
3114:
3084:
2954:Given the element
2941:
2913:
2832:
2753:
2709:
2667:
2277:
2122:
1952:
1763:
1575:
1551:
1512:
1462:
1423:
1377:
806:
801:
794:
784:
733:
723:
571:
508:
440:
435:
431:
421:
374:
364:
269:
222:modular arithmetic
6038:Non-adjacent form
5706:
5508:
5277:
5264:
5249:
5214:
5147:
5103:non-adjacent form
5073:
5031:
5016:
4968:
4953:
4757:
4658:squarings to get
4618:power associative
4388:. Then it raises
3655:{\displaystyle l}
3608:{\displaystyle n}
3528:
3126:are collected in
2891:
2597:Let the exponent
2114:
793:
783:
732:
722:
604:multiplications.
489:
430:
420:
373:
363:
249:Recursive version
226:additive notation
178:
177:
170:
152:
76:
75:
68:
6256:
6223:
6222:
6196:
6187:
6181:
6180:
6178:
6169:(177): 243–264.
6160:
6151:
6145:
6144:
6126:
6106:
6104:
6102:
6101:
6096:
6094:
6093:
6086:
6085:
6059:
5983:
5981:
5980:
5975:
5973:
5972:
5963:
5962:
5953:
5952:
5934:
5933:
5921:
5920:
5902:
5900:
5899:
5894:
5892:
5891:
5882:
5881:
5872:
5871:
5835:
5834:
5800:(multiplying by
5773:
5771:
5770:
5765:
5757:
5756:
5738:
5737:
5719:
5718:
5716:
5715:
5710:
5708:
5707:
5704:
5694:
5678:
5652:
5651:
5649:
5648:
5643:
5641:
5640:
5619:
5618:
5606:
5605:
5589:
5573:
5572:
5570:
5569:
5564:
5562:
5558:
5554:
5553:
5535:
5534:
5522:
5521:
5509:
5501:
5491:
5490:
5467:
5460:
5453:
5452:
5450:
5449:
5444:
5436:
5435:
5416:
5414:
5413:
5408:
5400:
5399:
5381:
5380:
5364:
5362:
5361:
5356:
5354:
5353:
5344:
5343:
5331:
5330:
5315:
5314:
5289:
5287:
5286:
5281:
5279:
5278:
5275:
5266:
5265:
5257:
5251:
5250:
5242:
5226:
5224:
5223:
5218:
5216:
5215:
5212:
5206:
5205:
5193:
5192:
5167:
5165:
5164:
5159:
5148:
5145:
5137:
5136:
5121:
5120:
5093:
5089:
5085:
5083:
5082:
5077:
5075:
5074:
5066:
5056:
5054:
5053:
5048:
5046:
5045:
5033:
5032:
5024:
5018:
5017:
5009:
4993:
4991:
4990:
4985:
4983:
4982:
4970:
4969:
4961:
4955:
4954:
4946:
4930:
4923:
4921:
4920:
4915:
4913:
4912:
4903:
4902:
4890:
4889:
4864:
4862:
4861:
4856:
4827:
4826:
4810:
4797:
4795:
4794:
4789:
4778:
4773:
4772:
4763:
4758:
4756: with
4755:
4753:
4752:
4743:
4742:
4732:
4721:
4690:
4686:
4675:
4669:
4663:
4657:
4653:
4646:
4639:
4633:
4596:
4574:
4544:
4536:
4506:
4499:
4491:
4488:integers modulo
4476:exponents modulo
4470:that are not of
4457:
4446:
4435:
4424:
4413:
4402:
4398:
4387:
4366:
4353:
4351:
4349:
4348:
4343:
4340:
4339:
4338:
4328:
4316:
4315:
4292:
4290:
4288:
4287:
4282:
4279:
4274:
4262:
4261:
4249:
4248:
4228:
4226:
4224:
4223:
4218:
4215:
4210:
4193:
4191:
4189:
4188:
4183:
4178:
4177:
4172:
4171:
4161:
4160:
4145:
4144:
4124:
4122:
4120:
4119:
4114:
4109:
4108:
4099:
4094:
4093:
4065:
4063:
4061:
4060:
4055:
4047:
4046:
4026:
4024:
4022:
4021:
4016:
4014:
4013:
4001:
4000:
3988:
3987:
3954:
3953:
3930:
3928:
3926:
3925:
3920:
3918:
3917:
3884:
3883:
3863:
3861:
3859:
3858:
3853:
3851:
3850:
3838:
3837:
3787:
3785:
3783:
3782:
3777:
3734:
3732:
3731:
3726:
3724:
3723:
3722:
3721:
3720:
3719:
3685:
3684:
3683:
3682:
3661:
3659:
3658:
3653:
3641:
3639:
3638:
3633:
3631:
3630:
3614:
3612:
3611:
3606:
3594:
3588:
3581:
3565:
3561:
3552:
3543:
3541:
3540:
3535:
3533:
3529:
3527:
3526:
3517:
3516:
3507:
3485:
3483:
3482:
3477:
3471:
3470:
3469:
3454:
3453:
3443:
3431:
3430:
3429:
3428:
3418:
3414:
3412:
3407:
3395:
3394:
3375:
3374:
3373:
3363:
3350:
3349:
3348:
3338:
3319:
3315:
3309:
3307:
3306:
3301:
3299:
3298:
3272:Euclidean method
3267:
3263:
3261:
3259:
3258:
3253:
3233:
3231:
3229:
3228:
3223:
3197:
3195:
3193:
3192:
3187:
3167:
3163:
3161:
3159:
3158:
3153:
3129:
3125:
3123:
3121:
3120:
3115:
3095:
3093:
3091:
3090:
3085:
3065:
3054:
3050:
3046:
3039:
3026:
2979:
2975:
2965:
2961:
2957:
2950:
2948:
2947:
2942:
2937:
2936:
2931:
2930:
2923:
2922:
2912:
2905:
2904:
2890:
2889:
2882:
2871:
2852:
2851:
2850:
2840:
2830:
2819:
2801:
2800:
2778:
2762:
2760:
2759:
2754:
2718:
2716:
2715:
2710:
2702:
2701:
2676:
2674:
2673:
2668:
2663:
2662:
2653:
2652:
2642:
2631:
2600:
2593:
2586:
2582:
2575:
2571:
2564:
2402:binary expansion
2286:
2284:
2283:
2278:
2276:
2275:
2268:
2267:
2238:
2237:
2225:
2224:
2204:
2131:
2129:
2128:
2123:
2115:
2113:
2100:
2099:
2083:
2082:
2081:
2047:
1961:
1959:
1958:
1953:
1951:
1950:
1943:
1942:
1913:
1912:
1900:
1899:
1883:
1772:
1770:
1769:
1764:
1759:
1758:
1752:
1751:
1727:
1726:
1714:
1713:
1708:
1707:
1682:
1681:
1672:
1671:
1664:
1644:
1591:binary expansion
1584:
1582:
1581:
1576:
1560:
1558:
1557:
1552:
1541:
1540:
1521:
1519:
1518:
1513:
1502:
1501:
1471:
1469:
1468:
1463:
1452:
1451:
1432:
1430:
1429:
1424:
1422:
1421:
1409:
1408:
1386:
1384:
1383:
1378:
1376:
1375:
1353:
1350:
1347:
1344:
1341:
1338:
1335:
1332:
1329:
1326:
1323:
1320:
1317:
1314:
1311:
1308:
1305:
1302:
1299:
1296:
1293:
1290:
1287:
1284:
1281:
1278:
1275:
1272:
1269:
1266:
1263:
1260:
1257:
1254:
1251:
1248:
1245:
1242:
1239:
1236:
1233:
1230:
1227:
1224:
1221:
1218:
1215:
1212:
1209:
1206:
1203:
1200:
1197:
1194:
1191:
1188:
1185:
1182:
1179:
1176:
1173:
1170:
1167:
1164:
1161:
1158:
1155:
1152:
1149:
1146:
1143:
1140:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1085:
1082:
1079:
1076:
1075:exp_by_squaring2
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1015:exp_by_squaring2
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:
931:exp_by_squaring2
929:
926:
923:
920:
917:
914:
911:
908:
905:
902:
899:
896:
893:
890:
889:exp_by_squaring2
887:
884:
881:
878:
875:
872:
869:
866:
863:
862:exp_by_squaring2
860:
857:
854:
851:
848:
845:
842:
839:
829:
825:
815:
813:
812:
807:
805:
804:
795:
791:
785:
781:
773:
772:
768:
755:
754:
734:
730:
724:
720:
712:
711:
707:
682:
681:
645:
644:
603:
596:
592:
588:
580:
578:
577:
572:
558:
557:
538:
517:
515:
514:
509:
503:
502:
494:
490:
482:
472:
471:
455:
452:If the exponent
449:
447:
446:
441:
439:
438:
432:
428:
422:
418:
410:
409:
405:
392:
391:
375:
371:
365:
361:
353:
352:
348:
323:
322:
295:
294:
278:
276:
275:
270:
194:positive integer
173:
166:
162:
159:
153:
151:
110:
86:
78:
71:
64:
60:
57:
51:
27:
26:
19:
6264:
6263:
6259:
6258:
6257:
6255:
6254:
6253:
6229:
6228:
6227:
6226:
6194:
6189:
6188:
6184:
6158:
6153:
6152:
6148:
6141:
6128:
6127:
6120:
6115:
6110:
6109:
6077:
6072:
6067:
6066:
6060:
6056:
6051:
6019:
5964:
5954:
5944:
5925:
5912:
5907:
5906:
5883:
5873:
5863:
5826:
5821:
5820:
5786:
5780:
5742:
5729:
5724:
5723:
5720:
5699:
5656:
5655:
5653:
5626:
5610:
5597:
5576:
5575:
5574:
5539:
5526:
5513:
5499:
5495:
5476:
5471:
5470:
5469:
5462:
5455:
5427:
5422:
5421:
5420:
5385:
5372:
5367:
5366:
5345:
5335:
5316:
5306:
5292:
5291:
5270:
5229:
5228:
5207:
5197:
5178:
5170:
5169:
5168:and denoted by
5122:
5112:
5107:
5106:
5091:
5087:
5059:
5058:
5037:
4996:
4995:
4974:
4933:
4932:
4925:
4904:
4894:
4875:
4867:
4866:
4818:
4813:
4812:
4805:
4764:
4744:
4734:
4696:
4695:
4688:
4684:
4671:
4665:
4659:
4655:
4648:
4641:
4635:
4629:
4626:
4603:non-commutative
4578:
4556:
4542:
4538:
4523:
4520:exp-by-squaring
4518:Applying above
4504:
4497:
4489:
4464:
4456:
4448:
4445:
4437:
4434:
4426:
4423:
4415:
4412:
4404:
4400:
4397:
4389:
4377:
4368:
4365:
4357:
4354:
4330:
4307:
4302:
4301:
4297:
4253:
4240:
4235:
4234:
4229:
4197:
4196:
4194:
4162:
4152:
4136:
4131:
4130:
4125:
4100:
4085:
4071:
4070:
4066:
4038:
4033:
4032:
4030:
4005:
3992:
3934:
3933:
3931:
3867:
3866:
3864:
3842:
3829:
3791:
3790:
3788:
3744:
3743:
3741:
3711:
3706:
3701:
3674:
3669:
3664:
3663:
3644:
3643:
3622:
3617:
3616:
3597:
3596:
3590:
3586:
3580:
3573:
3567:
3563:
3560:
3554:
3551:
3545:
3518:
3508:
3502:
3491:
3490:
3461:
3445:
3420:
3386:
3385:
3381:
3380:
3365:
3340:
3325:
3324:
3317:
3311:
3290:
3285:
3284:
3274:
3265:
3238:
3237:
3235:
3202:
3201:
3199:
3172:
3171:
3169:
3165:
3138:
3137:
3135:
3127:
3100:
3099:
3097:
3070:
3069:
3067:
3064:
3060:
3052:
3048:
3045:
3041:
3033:
3028:
3021:
3018:
3008:
2977:
2967:
2963:
2959:
2955:
2924:
2914:
2896:
2842:
2792:
2787:
2786:
2772:
2767:
2721:
2720:
2693:
2682:
2681:
2654:
2644:
2606:
2605:
2598:
2592:
2588:
2584:
2581:
2577:
2573:
2566:
2562:
2559:
2551:precomputations
2543:
2520:
2519:
2512:
2508:
2504:
2500:
2496:
2489:
2485:
2481:
2477:
2473:
2465:
2455:i = k - 2 to 0
2450:
2446:
2435:
2428:
2424:
2417:
2383:
2378:
2372:
2368:
2364:
2360:
2340:
2324:
2259:
2254:
2229:
2216:
2211:
2210:
2203:
2199:
2192:
2182:
2169:
2147:
2143:
2138:
2085:
2084:
2070:
2048:
2029:
2028:
2018:
1988:
1934:
1929:
1904:
1891:
1886:
1885:
1882:
1878:
1871:
1861:
1848:
1779:
1743:
1701:
1673:
1625:
1624:
1563:
1562:
1532:
1524:
1523:
1493:
1485:
1484:
1481:
1443:
1435:
1434:
1413:
1400:
1389:
1388:
1367:
1359:
1358:
1355:
1354:
1351:
1348:
1345:
1342:
1339:
1336:
1333:
1330:
1327:
1324:
1321:
1318:
1315:
1312:
1309:
1306:
1303:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1273:
1270:
1267:
1264:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1234:
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:
1132:
1131:
1128:
1125:
1122:
1119:
1116:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1077:
1074:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1050:
1047:
1044:
1041:
1038:
1035:
1032:
1029:
1026:
1023:
1020:
1017:
1014:
1011:
1008:
1005:
1002:
999:
996:
993:
990:
987:
984:
981:
978:
975:
972:
969:
966:
963:
960:
957:
954:
951:
948:
945:
942:
939:
936:
933:
930:
927:
924:
921:
918:
915:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
867:
864:
861:
858:
855:
852:
849:
846:
843:
841:exp_by_squaring
840:
837:
827:
820:
800:
799:
777:
756:
746:
736:
735:
716:
683:
673:
650:
636:
628:
627:
621:
598:
594:
590:
586:
549:
541:
540:
536:
529:
477:
476:
463:
458:
457:
453:
434:
433:
414:
393:
383:
377:
376:
357:
324:
314:
300:
286:
281:
280:
255:
254:
251:
246:
230:elliptic curves
174:
163:
157:
154:
111:
109:
99:
87:
72:
61:
55:
52:
41:
28:
24:
17:
12:
11:
5:
6262:
6260:
6252:
6251:
6246:
6241:
6231:
6230:
6225:
6224:
6182:
6146:
6139:
6117:
6116:
6114:
6111:
6108:
6107:
6092:
6089:
6084:
6080:
6075:
6053:
6052:
6050:
6047:
6046:
6045:
6043:Addition chain
6040:
6035:
6030:
6025:
6018:
6015:
5990:
5989:
5971:
5967:
5961:
5957:
5951:
5947:
5943:
5940:
5937:
5932:
5928:
5924:
5919:
5915:
5904:
5890:
5886:
5880:
5876:
5870:
5866:
5862:
5859:
5856:
5853:
5850:
5847:
5844:
5841:
5838:
5833:
5829:
5794:addition chain
5782:Main article:
5779:
5776:
5763:
5760:
5755:
5752:
5749:
5745:
5741:
5736:
5732:
5702:
5697:
5693:
5689:
5685:
5681:
5677:
5674:
5671:
5667:
5663:
5639:
5636:
5633:
5629:
5625:
5622:
5617:
5613:
5609:
5604:
5600:
5596:
5592:
5588:
5584:
5561:
5557:
5552:
5549:
5546:
5542:
5538:
5533:
5529:
5525:
5520:
5516:
5512:
5507:
5504:
5498:
5494:
5489:
5486:
5483:
5479:
5442:
5439:
5434:
5430:
5419:
5406:
5403:
5398:
5395:
5392:
5388:
5384:
5379:
5375:
5352:
5348:
5342:
5338:
5334:
5329:
5326:
5323:
5319:
5313:
5309:
5305:
5302:
5299:
5273:
5269:
5263:
5260:
5254:
5248:
5245:
5239:
5236:
5210:
5204:
5200:
5196:
5191:
5188:
5185:
5181:
5177:
5157:
5154:
5151:
5143:
5140:
5135:
5132:
5129:
5125:
5119:
5115:
5099:Hamming weight
5072:
5069:
5044:
5040:
5036:
5030:
5027:
5021:
5015:
5012:
5006:
5003:
4981:
4977:
4973:
4967:
4964:
4958:
4952:
4949:
4943:
4940:
4911:
4907:
4901:
4897:
4893:
4888:
4885:
4882:
4878:
4874:
4854:
4851:
4848:
4845:
4842:
4839:
4836:
4833:
4830:
4825:
4821:
4799:
4798:
4787:
4784:
4781:
4777:
4771:
4767:
4762:
4751:
4747:
4741:
4737:
4731:
4728:
4725:
4720:
4717:
4714:
4710:
4706:
4703:
4683:of an integer
4625:
4622:
4599:
4598:
4576:
4540:
4501:
4500:
4463:
4460:
4452:
4441:
4430:
4419:
4408:
4393:
4373:
4361:
4337:
4333:
4327:
4323:
4319:
4314:
4310:
4278:
4273:
4269:
4265:
4260:
4256:
4252:
4247:
4243:
4214:
4209:
4205:
4181:
4176:
4170:
4166:
4159:
4155:
4151:
4148:
4143:
4139:
4112:
4107:
4103:
4098:
4092:
4088:
4084:
4081:
4078:
4053:
4050:
4045:
4041:
4012:
4008:
4004:
3999:
3995:
3991:
3986:
3981:
3978:
3975:
3972:
3969:
3966:
3963:
3960:
3957:
3952:
3947:
3944:
3941:
3916:
3911:
3908:
3905:
3902:
3899:
3896:
3893:
3890:
3887:
3882:
3877:
3874:
3849:
3845:
3841:
3836:
3832:
3828:
3825:
3822:
3819:
3816:
3813:
3810:
3807:
3804:
3801:
3798:
3775:
3772:
3769:
3766:
3763:
3760:
3757:
3754:
3751:
3737:
3718:
3714:
3709:
3704:
3700:
3697:
3694:
3691:
3688:
3681:
3677:
3672:
3651:
3629:
3625:
3604:
3578:
3571:
3558:
3549:
3532:
3525:
3521:
3515:
3511:
3505:
3501:
3498:
3487:
3486:
3475:
3468:
3464:
3458:
3452:
3448:
3442:
3438:
3434:
3427:
3423:
3417:
3411:
3406:
3402:
3398:
3393:
3389:
3384:
3379:
3372:
3368:
3362:
3358:
3354:
3347:
3343:
3337:
3333:
3297:
3293:
3280:by P.D Rooij.
3273:
3270:
3251:
3248:
3245:
3221:
3218:
3215:
3212:
3209:
3185:
3182:
3179:
3151:
3148:
3145:
3134:is multiplied
3113:
3110:
3107:
3083:
3080:
3077:
3062:
3043:
3031:
3006:
2982:
2976:, the element
2952:
2951:
2940:
2935:
2929:
2921:
2917:
2911:
2908:
2903:
2899:
2894:
2888:
2881:
2878:
2875:
2870:
2867:
2864:
2860:
2856:
2849:
2845:
2839:
2835:
2829:
2826:
2823:
2818:
2815:
2812:
2808:
2804:
2799:
2795:
2770:
2752:
2749:
2746:
2743:
2740:
2737:
2734:
2731:
2728:
2708:
2705:
2700:
2696:
2692:
2689:
2678:
2677:
2666:
2661:
2657:
2651:
2647:
2641:
2638:
2635:
2630:
2627:
2624:
2620:
2616:
2613:
2601:be written as
2590:
2579:
2558:
2555:
2542:
2539:
2535:timing attacks
2517:
2510:
2506:
2502:
2498:
2494:
2487:
2483:
2479:
2475:
2471:
2463:
2448:
2444:
2442:
2433:
2426:
2422:
2412:
2382:
2379:
2370:
2366:
2362:
2358:
2338:
2322:
2309:
2305:
2304:
2293:
2289:
2288:
2274:
2271:
2266:
2262:
2257:
2253:
2250:
2247:
2244:
2241:
2236:
2232:
2228:
2223:
2219:
2205:, a parameter
2201:
2197:
2187:
2177:
2158:
2145:
2141:
2137:
2134:
2133:
2132:
2121:
2118:
2112:
2109:
2106:
2103:
2098:
2095:
2092:
2088:
2080:
2077:
2073:
2069:
2066:
2063:
2060:
2057:
2054:
2051:
2045:
2042:
2039:
2036:
1986:
1980:
1979:
1978:
1968:
1964:
1963:
1949:
1946:
1941:
1937:
1932:
1928:
1925:
1922:
1919:
1916:
1911:
1907:
1903:
1898:
1894:
1880:
1876:
1866:
1856:
1843:, a parameter
1833:
1778:
1775:
1774:
1773:
1762:
1757:
1750:
1746:
1742:
1739:
1736:
1733:
1730:
1725:
1720:
1717:
1712:
1706:
1700:
1697:
1694:
1691:
1688:
1685:
1680:
1676:
1670:
1663:
1660:
1657:
1654:
1651:
1648:
1643:
1640:
1637:
1633:
1587:floor function
1574:
1570:
1550:
1547:
1544:
1539:
1535:
1531:
1511:
1508:
1505:
1500:
1496:
1492:
1480:
1477:
1461:
1458:
1455:
1450:
1446:
1442:
1420:
1416:
1412:
1407:
1403:
1399:
1396:
1374:
1370:
1366:
1137:
836:
817:
816:
803:
798:
788:
778:
776:
771:
767:
763:
759:
753:
749:
745:
741:
738:
737:
727:
717:
715:
710:
706:
702:
699:
696:
693:
690:
686:
680:
676:
672:
668:
665:
662:
659:
656:
655:
653:
648:
643:
639:
635:
620:
617:
609:tail-recursive
581:the number of
570:
567:
564:
561:
556:
552:
548:
526:
507:
501:
498:
493:
488:
485:
480:
475:
470:
466:
437:
425:
415:
413:
408:
404:
400:
396:
390:
386:
382:
379:
378:
368:
358:
356:
351:
347:
343:
340:
337:
334:
331:
327:
321:
317:
313:
309:
306:
305:
303:
298:
293:
289:
268:
265:
262:
250:
247:
245:
242:
238:double-and-add
216:algorithms or
176:
175:
90:
88:
81:
74:
73:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
6261:
6250:
6247:
6245:
6242:
6240:
6237:
6236:
6234:
6220:
6216:
6212:
6208:
6204:
6200:
6193:
6186:
6183:
6177:
6172:
6168:
6164:
6157:
6150:
6147:
6142:
6140:9781584885184
6136:
6132:
6125:
6123:
6119:
6112:
6090:
6087:
6082:
6078:
6073:
6064:
6058:
6055:
6048:
6044:
6041:
6039:
6036:
6034:
6031:
6029:
6026:
6024:
6021:
6020:
6016:
6014:
6012:
6008:
6003:
5999:
5995:
5987:
5969:
5959:
5949:
5945:
5935:
5930:
5926:
5922:
5917:
5913:
5905:
5888:
5878:
5868:
5864:
5860:
5857:
5851:
5848:
5842:
5839:
5836:
5831:
5827:
5819:
5818:
5817:
5815:
5811:
5807:
5803:
5799:
5795:
5791:
5785:
5777:
5775:
5761:
5758:
5753:
5750:
5747:
5743:
5739:
5734:
5730:
5695:
5691:
5687:
5683:
5679:
5675:
5672:
5669:
5665:
5637:
5634:
5631:
5627:
5623:
5620:
5615:
5611:
5607:
5602:
5598:
5594:
5590:
5586:
5582:
5559:
5550:
5547:
5544:
5540:
5536:
5531:
5527:
5523:
5518:
5514:
5505:
5502:
5496:
5492:
5487:
5484:
5481:
5477:
5465:
5458:
5440:
5437:
5432:
5428:
5418:
5404:
5401:
5396:
5393:
5390:
5386:
5382:
5377:
5373:
5350:
5340:
5336:
5332:
5327:
5324:
5321:
5317:
5311:
5307:
5300:
5297:
5267:
5258:
5252:
5243:
5237:
5202:
5198:
5194:
5189:
5186:
5183:
5179:
5155:
5152:
5149:
5141:
5138:
5133:
5130:
5127:
5123:
5117:
5113:
5104:
5100:
5097:
5067:
5042:
5034:
5025:
5019:
5010:
5004:
4979:
4971:
4962:
4956:
4947:
4941:
4928:
4909:
4899:
4895:
4891:
4886:
4883:
4880:
4876:
4849:
4846:
4843:
4840:
4837:
4834:
4828:
4823:
4819:
4808:
4803:
4785:
4782:
4779:
4769:
4765:
4749:
4745:
4739:
4735:
4729:
4726:
4723:
4718:
4715:
4712:
4708:
4704:
4701:
4694:
4693:
4692:
4682:
4677:
4674:
4668:
4662:
4651:
4644:
4638:
4632:
4623:
4621:
4619:
4615:
4610:
4608:
4604:
4594:
4590:
4586:
4582:
4577:
4572:
4568:
4564:
4560:
4555:
4554:
4553:
4551:
4546:
4534:
4530:
4526:
4521:
4516:
4514:
4510:
4496:
4495:
4494:
4492:
4485:
4481:
4477:
4473:
4469:
4461:
4459:
4455:
4451:
4444:
4440:
4433:
4429:
4422:
4418:
4411:
4407:
4399:to the power
4396:
4392:
4385:
4381:
4376:
4372:
4364:
4360:
4335:
4331:
4325:
4321:
4317:
4312:
4308:
4300:
4295:
4276:
4271:
4267:
4263:
4258:
4254:
4250:
4245:
4241:
4233:
4212:
4207:
4203:
4174:
4168:
4157:
4153:
4146:
4141:
4137:
4129:
4105:
4101:
4096:
4090:
4086:
4079:
4076:
4069:
4051:
4048:
4043:
4039:
4029:
4010:
4006:
4002:
3997:
3993:
3989:
3979:
3976:
3970:
3967:
3964:
3961:
3958:
3945:
3942:
3909:
3906:
3900:
3897:
3894:
3891:
3888:
3875:
3872:
3847:
3843:
3839:
3834:
3830:
3826:
3820:
3817:
3814:
3811:
3808:
3802:
3799:
3770:
3767:
3764:
3761:
3758:
3752:
3749:
3740:
3736:
3716:
3712:
3707:
3702:
3698:
3695:
3692:
3689:
3686:
3679:
3675:
3670:
3649:
3627:
3623:
3602:
3593:
3583:
3577:
3570:
3557:
3548:
3530:
3523:
3519:
3513:
3509:
3503:
3499:
3496:
3473:
3466:
3462:
3456:
3450:
3446:
3440:
3436:
3432:
3425:
3421:
3415:
3409:
3404:
3400:
3396:
3391:
3387:
3382:
3377:
3370:
3366:
3360:
3356:
3352:
3345:
3341:
3335:
3331:
3323:
3322:
3321:
3314:
3295:
3291:
3281:
3279:
3271:
3269:
3249:
3246:
3243:
3219:
3216:
3213:
3210:
3207:
3183:
3180:
3177:
3149:
3146:
3143:
3133:
3111:
3108:
3105:
3081:
3078:
3075:
3058:
3038:
3034:
3024:
3016:
3012:
3004:
3001:
2997:
2993:
2990:
2986:
2981:
2974:
2970:
2938:
2933:
2919:
2915:
2909:
2906:
2901:
2897:
2892:
2879:
2876:
2873:
2868:
2865:
2862:
2858:
2854:
2847:
2843:
2837:
2833:
2827:
2824:
2821:
2816:
2813:
2810:
2806:
2802:
2797:
2793:
2785:
2784:
2783:
2780:
2777:
2773:
2764:
2747:
2744:
2741:
2738:
2735:
2729:
2726:
2706:
2703:
2698:
2694:
2690:
2687:
2664:
2659:
2655:
2649:
2645:
2639:
2636:
2633:
2628:
2625:
2622:
2618:
2614:
2611:
2604:
2603:
2602:
2595:
2594:be integers.
2569:
2554:
2552:
2548:
2540:
2538:
2536:
2531:
2529:
2525:
2515:
2492:
2469:
2461:
2458:
2454:
2441:
2439:
2432:
2421:
2415:
2411:
2407:
2403:
2398:
2396:
2392:
2388:
2376:
2356:
2352:
2348:
2344:
2336:
2332:
2328:
2320:
2317:
2313:
2308:
2302:
2298:
2294:
2291:
2290:
2272:
2269:
2264:
2260:
2255:
2251:
2248:
2245:
2242:
2239:
2234:
2230:
2226:
2221:
2217:
2208:
2196:
2190:
2186:
2180:
2176:
2172:
2167:
2163:
2159:
2156:
2155:
2154:
2151:
2148:
2135:
2119:
2116:
2110:
2107:
2104:
2101:
2096:
2093:
2090:
2086:
2078:
2075:
2071:
2067:
2061:
2058:
2055:
2049:
2043:
2040:
2037:
2034:
2027:
2026:
2025:
2023:
2016:
2012:
2008:
2004:
2000:
1996:
1992:
1984:
1977:
1973:
1969:
1966:
1965:
1947:
1944:
1939:
1935:
1930:
1926:
1923:
1920:
1917:
1914:
1909:
1905:
1901:
1896:
1892:
1875:
1869:
1865:
1859:
1855:
1851:
1846:
1842:
1838:
1834:
1831:
1830:
1829:
1826:
1824:
1820:
1816:
1812:
1808:
1804:
1800:
1796:
1792:
1788:
1784:
1776:
1760:
1748:
1740:
1737:
1734:
1731:
1718:
1715:
1710:
1695:
1692:
1689:
1683:
1678:
1674:
1658:
1655:
1652:
1646:
1641:
1638:
1635:
1623:
1622:
1621:
1619:
1615:
1611:
1607:
1602:
1600:
1596:
1592:
1588:
1545:
1542:
1537:
1533:
1506:
1503:
1498:
1494:
1478:
1476:
1473:
1459:
1456:
1453:
1448:
1444:
1440:
1418:
1414:
1410:
1405:
1401:
1397:
1394:
1372:
1368:
1364:
1135:
834:
831:
823:
796:
792: is even
786:
774:
769:
765:
761:
751:
747:
739:
725:
713:
708:
704:
697:
694:
691:
678:
674:
663:
660:
651:
646:
641:
637:
633:
626:
625:
624:
618:
616:
612:
610:
605:
601:
584:
568:
562:
559:
554:
550:
534:
525:
523:
518:
505:
499:
496:
491:
486:
483:
478:
473:
468:
464:
450:
429: is even
423:
411:
406:
402:
398:
388:
384:
366:
354:
349:
345:
338:
335:
332:
319:
315:
307:
301:
296:
291:
287:
266:
263:
260:
248:
243:
241:
239:
235:
231:
227:
223:
219:
215:
211:
210:square matrix
207:
203:
199:
195:
191:
187:
183:
172:
169:
161:
158:February 2018
150:
147:
143:
140:
136:
133:
129:
126:
122:
119: –
118:
114:
113:Find sources:
107:
103:
97:
96:
91:This article
89:
85:
80:
79:
70:
67:
59:
49:
45:
39:
37:
32:This article
30:
21:
20:
6239:Exponentials
6205:(1): 31–43.
6202:
6198:
6185:
6166:
6163:Math. Comput
6162:
6149:
6130:
6062:
6057:
6010:
5993:
5991:
5988:is re-used).
5985:
5813:
5809:
5805:
5801:
5797:
5787:
5721:
5463:
5456:
5095:
4926:
4806:
4801:
4800:
4678:
4672:
4666:
4660:
4649:
4642:
4636:
4630:
4627:
4611:
4600:
4592:
4588:
4584:
4580:
4570:
4566:
4562:
4558:
4547:
4532:
4528:
4524:
4519:
4517:
4502:
4480:cryptography
4465:
4453:
4449:
4442:
4438:
4431:
4427:
4420:
4416:
4409:
4405:
4394:
4390:
4383:
4379:
4374:
4370:
4362:
4358:
4355:
4298:
4293:
4231:
4127:
4067:
4027:
3738:
3591:
3584:
3575:
3568:
3555:
3546:
3488:
3312:
3282:
3277:
3275:
3131:
3059:first those
3056:
3036:
3029:
3022:
3019:
3014:
3010:
3002:
2999:
2995:
2991:
2988:
2984:
2972:
2968:
2953:
2781:
2775:
2768:
2765:
2679:
2596:
2567:
2560:
2557:Yao's method
2546:
2544:
2532:
2527:
2521:
2513:
2490:
2467:
2459:
2456:
2452:
2440:as follows:
2437:
2430:
2419:
2413:
2409:
2405:
2399:
2395:Montgomery's
2384:
2374:
2354:
2350:
2349:h := 1
2346:
2342:
2334:
2330:
2326:
2318:
2315:
2311:
2306:
2300:
2296:
2295:The element
2206:
2194:
2188:
2184:
2178:
2174:
2170:
2165:
2161:
2152:
2149:
2139:
2021:
2019:
2014:
2010:
2006:
2005:j := 1
2002:
1998:
1994:
1993:j := 1
1990:
1982:
1975:
1971:
1970:The element
1873:
1867:
1863:
1857:
1853:
1849:
1844:
1840:
1836:
1827:
1822:
1818:
1814:
1810:
1806:
1802:
1798:
1794:
1790:
1782:
1780:
1777:2-ary method
1620:is given by
1617:
1613:
1609:
1605:
1603:
1598:
1594:
1585:denotes the
1482:
1474:
1472:at the end.
1356:
1133:
832:
821:
818:
731: is odd
622:
613:
606:
599:
530:
519:
451:
372: is odd
252:
244:Basic method
237:
234:cryptography
217:
213:
196:powers of a
189:
179:
164:
155:
145:
138:
131:
124:
112:
100:Please help
95:verification
92:
62:
53:
42:Please help
33:
4587:) = (Power(
3566:and a rest
3040:, then the
2307:Algorithm:
2160:An element
2153:Algorithm:
1835:An element
1828:Algorithm:
279:, one has:
182:mathematics
6233:Categories
6113:References
4670:to obtain
4565:) = Power(
4468:semigroups
4436:the value
4028:Break loop
3932:such that
3789:such that
3739:Begin loop
3020:If we set
2400:Given the
2353:i - s + 1
2314:i > -1
206:polynomial
128:newspapers
38:to readers
6088:−
6002:heuristic
5998:compilers
5936:×
5861:×
5852:×
5843:×
5684:…
5673:−
5621:−
5394:−
5333:…
5325:−
5262:¯
5247:¯
5195:…
5187:−
5153:⩾
5071:¯
5029:¯
5014:¯
4966:¯
4951:¯
4892:…
4884:−
4835:−
4829:∈
4727:−
4709:∑
4687:in radix
4509:remainder
4264:⋅
4230:and then
4126:and then
4111:⌋
4083:⌊
4003:≥
3977:−
3968:−
3946:∈
3940:∀
3907:−
3898:−
3876:∈
3840:≥
3818:−
3803:∈
3797:∀
3768:−
3753:∈
3589:in group
3433:⋅
3397:⋅
3353:⋅
3310:in group
3217:−
3181:−
3147:−
3109:−
3079:−
2987:j > 0
2893:∏
2877:−
2859:∏
2825:−
2807:∏
2745:−
2730:∈
2691:⩽
2637:−
2619:∑
2270:−
2108:−
2102:−
2068:⋅
2038:
1945:−
1813:), where
1797:, 0) and
1738:
1693:
1656:
1632:∑
1573:⌋
1569:⌊
1549:⌋
1543:
1530:⌊
1510:⌋
1504:
1491:⌊
1398:⋅
695:−
566:⌉
560:
547:⌈
497:−
336:−
204:, like a
202:semigroup
6017:See also
5696:′
5680:′
5591:′
5560:⌋
5497:⌊
5057:, where
4607:matrices
4535:mod 2345
4294:End loop
3531:⌋
3504:⌊
3316:, where
3051:in base
2719:for all
2365:, ..., n
2299:∈
1821:·2 with
1139:Function
886:Function
838:Function
782:if
721:if
419:if
362:if
232:used in
56:May 2022
6219:7629541
5994:optimal
5654:return
5096:minimal
4447:modulo
3262:
3236:
3232:
3200:
3196:
3170:
3162:
3136:
3124:
3098:
3094:
3068:
2193:, ...,
1872:, ...,
1793:(0) = (
142:scholar
34:may be
6217:
6137:
6007:Θ
5816:= 15:
4579:Power(
4557:Power(
4513:result
4299:Return
3489:where
3015:return
2998:w - 1
2994:i = 0
2680:where
2587:, and
2514:return
2447:= x; x
2375:return
2292:Output
2015:return
1997:k - s
1989:)
1967:Output
1787:Brauer
1597:. For
1343:return
1223:return
1072:return
1012:return
985:return
928:return
859:return
198:number
144:
137:
130:
123:
115:
6215:S2CID
6195:(PDF)
6159:(PDF)
6049:Notes
6009:(log
5468:do
5365:with
4929:= 478
4614:magma
4550:group
4505:13789
3865:Find
3742:Find
2985:while
2524:up to
2429:with
2335:while
2312:while
2157:Input
1983:while
1832:Input
1825:odd.
1805:) = (
1241:while
208:or a
149:JSTOR
135:books
6135:ISBN
5454:for
5238:1000
5020:1000
4994:and
4957:1100
4811:and
4780:<
4539:2log
4484:ring
3574:mod
3027:and
3011:then
3009:= j
2766:Let
2704:<
2526:log
2491:else
2468:then
2466:= 0
2451:= x
2341:= 0
2331:else
2327:then
2325:= 0
2044:<
1268:then
1247:>
1220:then
1172:then
1166:<
1069:then
1054:else
1009:then
1006:even
994:else
982:then
967:else
925:then
919:<
583:bits
264:>
184:and
121:news
6207:doi
6171:doi
5806:any
5798:one
5705:NAF
5466:− 1
5461:to
5459:= 0
5276:NAF
5253:000
5213:NAF
5005:100
4809:= 2
4691:as
4583:, −
4561:, −
4486:of
4232:let
4165:mod
4128:let
4068:Let
4031:if
3553:by
3457:mod
3025:= 2
2992:for
2971:...
2958:of
2570:= 2
2509:= x
2505:; x
2501:* x
2497:= x
2486:= x
2482:; x
2478:* x
2474:= x
2453:for
2434:k−1
2418:...
2408:= (
2363:i-1
2361:, n
2347:for
2164:of
2003:for
1991:for
1974:in
1852:= (
1839:of
1735:log
1690:log
1653:log
1593:of
1534:log
1495:log
1265:odd
1066:odd
824:= 1
602:− 1
551:log
535:of
180:In
104:by
6235::
6213:.
6201:.
6197:.
6167:48
6165:.
6161:.
6121:^
5918:15
5832:15
5088:−1
4972:10
4942:10
4676:.
4652:−1
4645:−1
4620:.
4609:.
4595:))
4591:,
4569:,
4533:xy
4531:=
4527:*
4458:.
4382:≠
4378:\
4369:{
4296:;
3582:.
3268:.
3168:,
3035:=
3017:y
3003:if
3000:do
2996:to
2989:do
2779:.
2774:=
2763:.
2583:,
2576:,
2460:if
2457:do
2416:−1
2377:y
2355:do
2351:to
2343:do
2319:if
2316:do
2191:−2
2183:,
2181:−1
2173:=(
2120:1.
2035:lg
2017:y
2011:do
2009:s
2007:to
1999:do
1995:to
1870:−2
1862:,
1860:−1
1817:=
1809:,
1328::=
1310::=
1292::=
1274::=
1262:is
1256:if
1253:do
1232::=
1208:if
1196::=
1178::=
1160:if
1063:is
1057:if
1003:is
997:if
970:if
913:if
524::
240:.
188:,
6221:.
6209::
6203:2
6179:.
6173::
6143:.
6091:1
6083:k
6079:2
6074:x
6063:k
6011:n
5986:x
5970:2
5966:)
5960:2
5956:]
5950:3
5946:x
5942:[
5939:(
5931:3
5927:x
5923:=
5914:x
5889:2
5885:)
5879:2
5875:]
5869:2
5865:x
5858:x
5855:[
5849:x
5846:(
5840:x
5837:=
5828:x
5814:n
5810:x
5802:x
5762:0
5759:=
5754:1
5751:+
5748:i
5744:n
5740:=
5735:i
5731:n
5701:)
5692:0
5688:n
5676:1
5670:l
5666:n
5662:(
5638:1
5635:+
5632:i
5628:c
5624:2
5616:i
5612:n
5608:+
5603:i
5599:c
5595:=
5587:i
5583:n
5556:)
5551:1
5548:+
5545:i
5541:n
5537:+
5532:i
5528:n
5524:+
5519:i
5515:c
5511:(
5506:2
5503:1
5493:=
5488:1
5485:+
5482:i
5478:c
5464:l
5457:i
5441:0
5438:=
5433:0
5429:c
5405:0
5402:=
5397:1
5391:l
5387:n
5383:=
5378:l
5374:n
5351:2
5347:)
5341:0
5337:n
5328:1
5322:l
5318:n
5312:l
5308:n
5304:(
5301:=
5298:n
5272:)
5268:0
5259:1
5244:1
5235:(
5209:)
5203:0
5199:n
5190:1
5184:l
5180:n
5176:(
5156:0
5150:i
5142:0
5139:=
5134:1
5131:+
5128:i
5124:n
5118:i
5114:n
5092:n
5068:1
5043:s
5039:)
5035:0
5026:1
5011:1
5002:(
4980:s
4976:)
4963:1
4948:1
4939:(
4927:n
4910:s
4906:)
4900:0
4896:n
4887:1
4881:l
4877:n
4873:(
4853:}
4850:1
4847:,
4844:0
4841:,
4838:1
4832:{
4824:i
4820:n
4807:b
4786:.
4783:b
4776:|
4770:i
4766:n
4761:|
4750:i
4746:b
4740:i
4736:n
4730:1
4724:l
4719:0
4716:=
4713:i
4705:=
4702:n
4689:b
4685:n
4673:x
4667:x
4661:x
4656:k
4650:k
4643:k
4637:x
4631:G
4597:.
4593:n
4589:x
4585:n
4581:x
4575:,
4573:)
4571:n
4567:x
4563:n
4559:x
4541:2
4529:y
4525:x
4490:q
4454:N
4450:n
4443:M
4439:n
4432:M
4428:n
4421:N
4417:x
4410:N
4406:x
4401:q
4395:M
4391:x
4386:}
4384:M
4380:i
4375:i
4371:n
4363:i
4359:n
4352:.
4336:M
4332:n
4326:M
4322:x
4318:=
4313:n
4309:x
4291:.
4277:q
4272:M
4268:x
4259:N
4255:x
4251:=
4246:N
4242:x
4227:,
4213:q
4208:M
4204:x
4192:.
4180:)
4175:N
4169:n
4158:M
4154:n
4150:(
4147:=
4142:N
4138:n
4123:,
4106:N
4102:n
4097:/
4091:M
4087:n
4080:=
4077:q
4064:.
4052:0
4049:=
4044:N
4040:n
4025:.
4011:i
4007:n
3998:N
3994:n
3990:,
3985:)
3980:M
3974:]
3971:1
3965:l
3962:,
3959:0
3956:[
3951:(
3943:i
3929:,
3915:)
3910:M
3904:]
3901:1
3895:l
3892:,
3889:0
3886:[
3881:(
3873:N
3862:.
3848:i
3844:n
3835:M
3831:n
3827:,
3824:]
3821:1
3815:l
3812:,
3809:0
3806:[
3800:i
3786:,
3774:]
3771:1
3765:l
3762:,
3759:0
3756:[
3750:M
3717:i
3713:l
3708:b
3703:x
3699:,
3696:.
3693:.
3690:.
3687:,
3680:0
3676:b
3671:x
3650:l
3628:n
3624:x
3603:n
3592:G
3587:x
3579:0
3576:n
3572:1
3569:n
3564:q
3559:0
3556:n
3550:1
3547:n
3524:0
3520:n
3514:1
3510:n
3500:=
3497:q
3474:,
3467:0
3463:n
3451:1
3447:n
3441:1
3437:x
3426:0
3422:n
3416:)
3410:q
3405:1
3401:x
3392:0
3388:x
3383:(
3378:=
3371:1
3367:n
3361:1
3357:x
3346:0
3342:n
3336:0
3332:x
3318:n
3313:G
3296:n
3292:x
3266:x
3250:1
3247:+
3244:w
3220:2
3214:h
3211:+
3208:w
3184:2
3178:h
3166:u
3150:1
3144:h
3132:y
3128:u
3112:2
3106:h
3082:1
3076:h
3063:i
3061:x
3057:u
3053:h
3049:n
3044:i
3042:n
3037:h
3032:i
3030:b
3023:h
3007:i
3005:n
2978:x
2973:x
2969:x
2964:n
2960:G
2956:x
2939:.
2934:j
2928:]
2920:i
2916:x
2910:j
2907:=
2902:i
2898:n
2887:[
2880:1
2874:h
2869:1
2866:=
2863:j
2855:=
2848:i
2844:n
2838:i
2834:x
2828:1
2822:w
2817:0
2814:=
2811:i
2803:=
2798:n
2794:x
2776:x
2771:i
2769:x
2751:]
2748:1
2742:w
2739:,
2736:0
2733:[
2727:i
2707:h
2699:i
2695:n
2688:0
2665:,
2660:i
2656:b
2650:i
2646:n
2640:1
2634:w
2629:0
2626:=
2623:i
2615:=
2612:n
2599:n
2591:i
2589:b
2585:b
2580:i
2578:n
2574:n
2568:b
2563:2
2547:x
2528:n
2518:1
2516:x
2511:2
2507:2
2503:2
2499:1
2495:1
2493:x
2488:1
2484:1
2480:2
2476:1
2472:2
2470:x
2464:i
2462:n
2449:2
2445:1
2443:x
2438:x
2431:n
2427:2
2425:)
2423:0
2420:n
2414:k
2410:n
2406:n
2371:2
2369:)
2367:s
2359:i
2339:s
2337:n
2323:i
2321:n
2303:.
2301:G
2297:x
2287:.
2273:1
2265:k
2261:2
2256:x
2252:,
2249:.
2246:.
2243:.
2240:,
2235:5
2231:x
2227:,
2222:3
2218:x
2207:k
2202:2
2200:)
2198:0
2195:n
2189:l
2185:n
2179:l
2175:n
2171:n
2166:G
2162:x
2146:2
2142:2
2117:+
2111:2
2105:k
2097:1
2094:+
2091:k
2087:2
2079:k
2076:2
2072:2
2065:)
2062:1
2059:+
2056:k
2053:(
2050:k
2041:n
2022:k
1987:i
1976:G
1972:x
1962:.
1948:1
1940:k
1936:2
1931:x
1927:,
1924:.
1921:.
1918:.
1915:,
1910:5
1906:x
1902:,
1897:3
1893:x
1881:2
1879:)
1877:0
1874:n
1868:l
1864:n
1858:l
1854:n
1850:n
1845:k
1841:G
1837:x
1823:u
1819:u
1815:m
1811:u
1807:s
1803:m
1801:(
1799:f
1795:k
1791:f
1783:x
1761:.
1756:)
1749:k
1745:)
1741:x
1732:n
1729:(
1724:(
1719:O
1716:=
1711:k
1705:)
1699:)
1696:x
1687:(
1684:O
1679:i
1675:2
1669:(
1662:)
1659:n
1650:(
1647:O
1642:0
1639:=
1636:i
1618:x
1614:k
1610:d
1606:d
1599:n
1595:n
1546:n
1538:2
1507:n
1499:2
1460:y
1457:x
1454:=
1449:1
1445:x
1441:y
1419:n
1415:x
1411:=
1406:n
1402:x
1395:1
1373:n
1369:x
1365:y
1352:y
1349:*
1346:x
1340:;
1337:2
1334:/
1331:n
1325:n
1322:;
1319:x
1316:*
1313:x
1307:x
1304:;
1301:1
1298:-
1295:n
1289:n
1286:;
1283:y
1280:*
1277:x
1271:y
1259:n
1250:1
1244:n
1238:;
1235:1
1229:y
1226:1
1217:0
1214:=
1211:n
1205:;
1202:n
1199:-
1193:n
1190:;
1187:x
1184:/
1181:1
1175:x
1169:0
1163:n
1157:)
1154:n
1151:,
1148:x
1145:(
1129:.
1126:)
1123:2
1120:/
1117:)
1114:1
1111:-
1108:n
1105:(
1102:,
1099:x
1096:*
1093:x
1090:,
1087:y
1084:*
1081:x
1078:(
1060:n
1051:;
1048:)
1045:2
1042:/
1039:n
1036:,
1033:x
1030:*
1027:x
1024:,
1021:y
1018:(
1000:n
991:;
988:y
979:0
976:=
973:n
964:;
961:)
958:n
955:-
952:,
949:x
946:/
943:1
940:,
937:y
934:(
922:0
916:n
910:)
907:n
904:,
901:x
898:,
895:y
892:(
883:)
880:n
877:,
874:x
871:,
868:1
865:(
856:)
853:n
850:,
847:x
844:(
828:0
822:y
797:.
787:n
775:,
770:2
766:/
762:n
758:)
752:2
748:x
744:(
740:y
726:n
714:,
709:2
705:/
701:)
698:1
692:n
689:(
685:)
679:2
675:x
671:(
667:)
664:x
661:y
658:(
652:{
647:=
642:n
638:x
634:y
600:n
595:n
591:1
587:n
569:,
563:n
555:2
537:n
506:.
500:n
492:)
487:x
484:1
479:(
474:=
469:n
465:x
454:n
424:n
412:,
407:2
403:/
399:n
395:)
389:2
385:x
381:(
367:n
355:,
350:2
346:/
342:)
339:1
333:n
330:(
326:)
320:2
316:x
312:(
308:x
302:{
297:=
292:n
288:x
267:0
261:n
171:)
165:(
160:)
156:(
146:·
139:·
132:·
125:·
98:.
69:)
63:(
58:)
54:(
50:.
40:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
