Addition chain
= Addition chain
An <addition chain> for a <positive integer> $k$ is $1=a_0<a_1<\cdots<a_r=k$, where each $a_t$ is the <sum> of two earlier entries, which may coincide. It computes $x^k$ in $r$ <multiplications> by reusing previously computed powers. For example, $1,2,3,6,12,15$ computes $x^{15}$ in five <multiplications>.