いけがみです。

> 加法連鎖の長さの最小値lを求める有効なアルゴリズムが
> 見つかったのでしょうか。

補足すると、「加法連鎖の長さの最小値」を求める問題は
NP-hard だったと思います。

P. Downey, B. Leong and R. Sthi, 
"Computing sequences with addition chains", SIAM Journal
of Computing, vol. 10, no.3 pp.638--646, 1981.

最近の論文で、次のようなものを見つけました。

Noboru Kunihiro and Hirosuke Yamamoto, 
"New methods for generating short addition chains",
IEICE Transactions on Fundamentals, vol. E83-A, no.1,
Jan. 2000.
http://search.ieice.org/2000/files/e000a01.htm#e83-a,1,60

この論文の Introduction によれば、加算連鎖の長さを
求めるアルゴリズムはいくつかあるみたいです。

# References がたどれなくてごめんなさい。