关于a^n的计算
1.计算a^n至少需要几步乘法（显然>=$log_2 n$)2.使用该最少的步数共有多少种不同的计算方法？
比如：
计算a^14最少需要6步，共14种计算方法：
1 2 3 4 7 14
1 2 3 5 7 14
1 2 3 6 7 14
1 2 3 6 8 14
1 2 3 6 12 14
1 2 4 5 7 14
1 2 4 5 9 14
1 2 4 5 10 14
1 2 4 6 7 14
1 2 4 6 8 14
1 2 4 6 10 14
1 2 4 6 12 14
1 2 4 8 10 14
1 2 4 8 12 14
3. a^n计算时，最少步数正好有 n种的除了1和14还有哪些？ 一般地，一数列1=a0, a1, a2,... ar=e，如果对每个i=1,2,...r,存在一整数对(j,k),j<=k<i，使得ai=aj+ak成立，则称为e的长为r的加法链。
寻找最短加法链的问题，目前还不知道有没有多项式时间的算法。它是属于复杂类NP中的问题，即通过“猜测”能用非确定性方法在多项式时间内解决的问题，P类问题则是能确定性地在多项式时间内解决的问题。容易明白P类问题是NP类问题的子集，因为所有多项式时间确定性的问题都可以非确定性地解出。
最短加法链的确定是一个NP完全问题，它是一个至少与解NP集合中所有其他问题同样困难的一个问题。因此，NP完全问题有特别的重要性，因为如果发现它们中间一个的确定性多项式时间的算法，则其他的NP问题也可以在多项式时间内解出。在这种情况下P类与NP类恰好重合。目前，普遍认为P！=NP。
《密码编码学---加密方法的C与C++实现 第2版》P69 谢谢回复。
更正一下，1楼的a^14 应该是5步：
1 2 3 4 7 14
即
a*a=a^2
a*a^2=a^3
a^2*a^2=a^4
a^3*a^4=a^7
a^7*a^7=a^14 乘法链的长度似乎有公式可以估算上界 计算a^n至少需要几步乘法（显然>=log2n)
-------------------------------------------------
已经推导出：
p(1)=0
p(2)=1
p(3)=2
p(2^n)=n
p(2n)=p(n)+1
p(2n+1)=min(p(n)+2, p(n+1)+2) 按楼上的思路，编了一个Mathematica程序：
g = If[# > 3, If, #0[#/2] + 1, Min[#0[(# - 1)/2], #0[(# + 1)/2]] + 2], # - 1] &;
Table[{ii,g@ii}, {ii, 1, 100}]
5# northwolves
p(2n+1)=min(p(n)+2, p(n+1)+2)
感觉这个好像有问题 比如：计算 a^27,按5楼的理论，应该先算出13或14，而a^13,a^14都至少需要5步，所以，
27应该要7步，可是这个只需要6步即可完成：
2,3,6,12,24,27
2,4,8,9,18,27 另外，算31,63,127,255,......似乎也有问题。
a^16需要四步，按5楼的理论，那么a^31应该要6步，可六步的方案我笔画了很长时间，也没找到。
7步的如下：
2，3，6，12，24，30，31
2，3，6，12，18，30，31
2，4，5，10，20，30，31
2，4，5，10，15，30，31 Knuth写了一个程序计算的：
http://www-cs-faculty.stanford.edu/~knuth/programs.html