Minimal addition-chain exponentiation

Question

I know it has been proven NP-complete, and that's ok. I'm currently solving it with branch and bound where I set the initial upper limit at the number of multiplications it would take the normal binary square/multiply algorithm, and it does give the right answers, but I'm not satisfied with the running time (it can take several seconds for numbers around 200). This being an NP-complete problem, I'm not expecting anything spectacular; but there are often tricks to get the Actual Time under control somewhat.

Are there faster ways to do this in practice? If so, what are they?

Answer 1

This looks like section 4.6.3 "Evaluation of Powers" in Knuth Vol 2 Seminumerical Algorithms. This goes into considerable detail to give various approaches, which look much quicker than branch and bound but do not all provide the absolutely best solution.

Knuth states in the discussion after Theorem F that he uses backtrack search to prove that l(191) = 11, so I doubt if you will find a short-cut answer for this. He defers explanation of the backtrack search to section 7.2.2, which is I think still unpublished, although there are traces of work on this at http://www-cs-faculty.stanford.edu/~uno/programs.html.

Answer 2

Metaheuristics algorithms will scale far better. They include Tabu search, Genetic algorithms, Simulated Annealing, ...

There's a couple of free books and free software out there.

Answer 3

I'm late to the party but in Handbook of Elliptic and Hyperelliptic Curve Cryptography there is a chapter "9.2 Fixed exponent" which also discusses various kinds addition chains.