我知道它已经被证明是np完全的，没关系。我目前正在用分枝定界法求解它，在那里我设置了乘法数的初始上限，这需要普通的二进制平方/乘法算法，它确实给出了正确的答案，但我对运行时间不满意（200左右的数字可能需要几秒钟）。这是一个np完全问题，我并不期望有什么了不起的事情；但通常有一些技巧可以让实际时间得到某种程度的控制。
在实践中有没有更快的方法来做到这一点？如果是，他们是什么？
最佳答案
这看起来像knuth vol 2半数值算法中的第4.6.3节“幂的计算”。这将详细介绍各种方法，这些方法看起来比branch和bound快得多，但并不都提供绝对最佳的解决方案。
knuth在定理f之后的讨论中指出，他使用回溯搜索来证明l（191）=11，所以我怀疑你是否能找到这个问题的捷径。他将回溯搜索的解释推迟到第7.2.2节，我认为该节尚未发表，尽管在http://www-cs-faculty.stanford.edu/~uno/programs.html上有关于这方面的工作的痕迹。