541:. Even given a shortest chain, addition-chain exponentiation requires more memory than the binary method, because it must potentially store many previous exponents from the chain. So in practice, shortest addition-chain exponentiation is primarily used for small fixed exponents for which a shortest chain can be pre-computed and is not too large.
548:
a shortest addition chain, and which often require fewer multiplications than binary exponentiation; binary exponentiation itself is a suboptimal addition-chain algorithm. The optimal algorithm choice depends on the context (such as the relative cost of the multiplication and the number of times a
536:
On the other hand, the determination of a shortest addition chain is hard: no efficient optimal methods are currently known for arbitrary exponents, and the related problem of finding a shortest addition chain for a given set of exponents has been proven
560:. That is, it is not sufficient to decompose the power into smaller powers, each of which is computed minimally, since the addition chains for the smaller powers may be related (to share computations). For example, in the shortest addition chain for
600:
may be used to obtain even fewer total multiplications+divisions (where subtraction corresponds to division). However, the slowness of division compared to multiplication makes this technique unattractive in general. For exponentiation to
722:
163:
320:
238:
62:
may also refer to exponentiation by non-minimal addition chains constructed by a variety of algorithms (since a shortest addition chain is very difficult to find).
890:
605:
integer powers, on the other hand, since one division is required anyway, an addition-subtraction chain is often beneficial. One such example is
617:
requires 7 multiplications and one division, whereas the shortest addition-subtraction chain requires 5 multiplications and one division:
623:
58:.) Each exponentiation in the chain can be evaluated by multiplying two of the earlier exponentiation results. More generally,
83:
245:
597:
170:
885:
748:), and therefore addition-subtraction chains are optimal in this context even for positive integer exponents.
808:
895:
77:, where the binary method needs six multiplications but the shortest addition chain requires only five:
70:
48:
47:, with multiplication instead of addition, computes the desired exponent (instead of multiple) of the
557:
813:
553:
765:
Downey, Peter; Leong, Benton; Sethi, Ravi (1981). "Computing sequences with addition chains".
818:
774:
24:
16:
Method of exponentiation by positive integers requiring a minimal number of multiplications
854:
602:
729:
44:
32:
879:
837:
Speeding up the computations on an elliptic curve using addition-subtraction chains
836:
538:
20:
66:
822:
793:
865:
552:
The problem of finding the shortest addition chain cannot be solved by
36:
778:
56:
sequence A003313 (Length of shortest addition chain for n)
859:
The Art of
Computer Programming, Volume 2: Seminumerical Algorithms
73:
and usually less. The first example of where it does better is for
52:
39:
power that requires a minimal number of multiplications. Using
861:, 3rd edition, §4.6.3 (Addison-Wesley: San Francisco, 1998).
55:
717:{\displaystyle a^{-31}=a/((((a^{2})^{2})^{2})^{2})^{2}\!}
596:
If both multiplication and division are allowed, then an
626:
248:
173:
86:
158:{\displaystyle a^{15}=a\times (a\times ^{2})^{2}\!}
716:
322:(also shortest addition chain, 5 multiplications).
314:
232:
157:
713:
311:
229:
154:
556:, because it does not satisfy the assumption of
740:) is available at no cost, since it is simply (
315:{\displaystyle a^{15}=a^{3}\times (^{2})^{2}\!}
724:(addition-subtraction chain, 5 mults + 1 div).
841:RAIRO Informatique théoretique et application
240:(shortest addition chain, 5 multiplications).
8:
233:{\displaystyle a^{15}=(^{2}\times a)^{3}\!}
588:), which also requires three multiplies).
812:
794:"A survey of fast exponentiation methods"
707:
697:
687:
677:
667:
646:
631:
625:
592:Addition-subtraction–chain exponentiation
305:
295:
285:
266:
253:
247:
223:
207:
197:
178:
172:
148:
138:
128:
91:
85:
325:
757:
69:requires no more multiplications than
7:
868:", to be incorporated into author's
835:François Morain and Jorge Olivos, "
544:There are also several methods to
14:
613:by a shortest addition chain for
576:is re-used (as opposed to, say,
891:Computer arithmetic algorithms
704:
694:
684:
674:
660:
657:
654:
651:
530:(((a × a→b) × b→d) × d→h) × h
519:((a × a→b) × b × a→e) × e × e
508:((a × a→b) × b→d) × d × d × b
497:((a × a→b) × b→d) × d × d × a
475:((a × a→b) × b→d) × d × b × a
327:Table demonstrating how to do
302:
292:
278:
275:
220:
204:
190:
187:
145:
135:
115:
106:
1:
60:addition-chain exponentiation
29:addition-chain exponentiation
549:given exponent is re-used).
65:The shortest addition-chain
165:(binary, 6 multiplications)
912:
792:Gordon, Daniel M. (1998).
732:, the inverse of a point (
598:addition-subtraction chain
564:above, the subproblem for
486:((a × a→b) × b→d) × d × d
464:((a × a→b) × b→d) × d × b
349:Specific implementation of
767:SIAM Journal on Computing
870:High-speed cryptography
51:. (This corresponds to
864:Daniel J. Bernstein, "
823:10.1006/jagm.1997.0913
728:For exponentiation on
718:
453:(a × a × a→c) × c × c
442:((a × a→b) × b→d) × d
431:(a × a→b) × b × b × a
316:
234:
159:
866:Pippenger's Algorithm
846:, pp. 531-543 (1990).
719:
568:must be computed as (
354:to do exponentiation
317:
235:
160:
71:binary exponentiation
624:
609:, where computing 1/
558:optimal substructure
246:
171:
84:
554:dynamic programming
335:
714:
420:(a × a→b) × b × b
409:(a × a→b) × b × a
326:
312:
230:
155:
534:
533:
903:
847:
833:
827:
826:
816:
798:
789:
783:
782:
762:
723:
721:
720:
715:
712:
711:
702:
701:
692:
691:
682:
681:
672:
671:
650:
639:
638:
336:
321:
319:
318:
313:
310:
309:
300:
299:
290:
289:
271:
270:
258:
257:
239:
237:
236:
231:
228:
227:
212:
211:
202:
201:
183:
182:
164:
162:
161:
156:
153:
152:
143:
142:
133:
132:
96:
95:
54:
25:computer science
911:
910:
906:
905:
904:
902:
901:
900:
886:Addition chains
876:
875:
855:Donald E. Knuth
851:
850:
834:
830:
796:
791:
790:
786:
779:10.1137/0210047
764:
763:
759:
754:
730:elliptic curves
703:
693:
683:
673:
663:
627:
622:
621:
594:
352:addition chains
350:
345:
341:multiplications
340:
333:addition chains
301:
291:
281:
262:
249:
244:
243:
219:
203:
193:
174:
169:
168:
144:
134:
124:
87:
82:
81:
31:is a method of
17:
12:
11:
5:
909:
907:
899:
898:
893:
888:
878:
877:
874:
873:
862:
849:
848:
828:
814:10.1.1.17.7076
784:
773:(3): 638–646.
756:
755:
753:
750:
744:, −
726:
725:
710:
706:
700:
696:
690:
686:
680:
676:
670:
666:
662:
659:
656:
653:
649:
645:
642:
637:
634:
630:
593:
590:
532:
531:
528:
525:
521:
520:
517:
514:
510:
509:
506:
503:
499:
498:
495:
492:
488:
487:
484:
481:
477:
476:
473:
470:
466:
465:
462:
459:
455:
454:
451:
448:
444:
443:
440:
437:
433:
432:
429:
426:
422:
421:
418:
415:
411:
410:
407:
404:
400:
399:
398:(a × a→b) × b
396:
393:
389:
388:
385:
382:
378:
377:
374:
371:
367:
366:
363:
360:
356:
355:
347:
346:exponentiation
342:
329:exponentiation
324:
323:
308:
304:
298:
294:
288:
284:
280:
277:
274:
269:
265:
261:
256:
252:
241:
226:
222:
218:
215:
210:
206:
200:
196:
192:
189:
186:
181:
177:
166:
151:
147:
141:
137:
131:
127:
123:
120:
117:
114:
111:
108:
105:
102:
99:
94:
90:
45:addition chain
35:by a positive
33:exponentiation
15:
13:
10:
9:
6:
4:
3:
2:
908:
897:
894:
892:
889:
887:
884:
883:
881:
871:
867:
863:
860:
856:
853:
852:
845:
842:
838:
832:
829:
824:
820:
815:
810:
806:
802:
801:J. Algorithms
795:
788:
785:
780:
776:
772:
768:
761:
758:
751:
749:
747:
743:
739:
735:
731:
708:
698:
688:
678:
668:
664:
647:
643:
640:
635:
632:
628:
620:
619:
618:
616:
612:
608:
604:
599:
591:
589:
587:
583:
580: =
579:
575:
571:
567:
563:
559:
555:
550:
547:
542:
540:
529:
526:
523:
522:
518:
515:
512:
511:
507:
504:
501:
500:
496:
493:
490:
489:
485:
482:
479:
478:
474:
471:
468:
467:
463:
460:
457:
456:
452:
449:
446:
445:
441:
438:
435:
434:
430:
427:
424:
423:
419:
416:
413:
412:
408:
405:
402:
401:
397:
394:
391:
390:
386:
383:
380:
379:
375:
372:
369:
368:
364:
361:
358:
357:
353:
348:
343:
338:
337:
334:
330:
306:
296:
286:
282:
272:
267:
263:
259:
254:
250:
242:
224:
216:
213:
208:
198:
194:
184:
179:
175:
167:
149:
139:
129:
125:
121:
118:
112:
109:
103:
100:
97:
92:
88:
80:
79:
78:
76:
72:
68:
63:
61:
57:
50:
46:
43:the shortest
42:
38:
34:
30:
26:
22:
896:Exponentials
872:book. (2002)
869:
858:
843:
840:
831:
804:
800:
787:
770:
766:
760:
745:
741:
737:
733:
727:
614:
610:
606:
595:
585:
581:
577:
573:
569:
565:
561:
551:
545:
543:
535:
351:
332:
328:
74:
64:
59:
40:
28:
18:
807:: 129–146.
546:approximate
539:NP-complete
41:the form of
21:mathematics
880:Categories
752:References
387:a × a × a
27:, optimal
809:CiteSeerX
633:−
339:Number of
273:×
214:×
122:×
113:×
104:×
67:algorithm
603:negative
572:) since
736:,
37:integer
811:
376:a × a
344:Actual
331:using
797:(PDF)
53:OEIS
49:base
23:and
839:",
819:doi
775:doi
19:In
882::
857:,
844:24
817:.
805:27
803:.
799:.
771:10
769:.
636:31
365:a
255:15
180:15
93:15
825:.
821::
781:.
777::
746:y
742:x
738:y
734:x
709:2
705:)
699:2
695:)
689:2
685:)
679:2
675:)
669:2
665:a
661:(
658:(
655:(
652:(
648:/
644:a
641:=
629:a
615:a
611:a
607:a
586:a
584:(
582:a
578:a
574:a
570:a
566:a
562:a
527:a
524:4
516:a
513:5
505:a
502:5
494:a
491:5
483:a
480:4
472:a
469:5
461:a
458:4
450:a
447:4
439:a
436:3
428:a
425:4
417:a
414:3
406:a
403:3
395:a
392:2
384:a
381:2
373:a
370:1
362:a
359:0
307:2
303:)
297:2
293:]
287:3
283:a
279:[
276:(
268:3
264:a
260:=
251:a
225:3
221:)
217:a
209:2
205:]
199:2
195:a
191:[
188:(
185:=
176:a
150:2
146:)
140:2
136:]
130:2
126:a
119:a
116:[
110:a
107:(
101:a
98:=
89:a
75:a
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.