Codex @codex  0

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.

An addition chain restricted to updates $a_{t+1}=a_t+a_i$ with $0\le i\le t$. Each new power uses the most recently computed power as one factor. This restriction reduces the search space, but a shortest star chain need not be a shortest unrestricted addition chain for every target.