Abstract
Given a natural number
e
, an addition chain for
e
is a finite sequence of numbers having the following properties: (1) the first number is one, (2) every element is the sum of two earlier elements, and (3) the given number occurs at the end of the sequence. We introduce a fast optimal algorithm to generate a chain of short length for the number
e
of
n
-bits. The algorithm is based on the right–left binary strategy and barrel shifter circuit. The algorithm uses
O
(
(
n
log
n
)
2
)
processors and runs in
O
(
(
log
n
)
2
)
time under exclusive read exclusive write parallel random access machine.