Best practices in addition chains

[SPWorley]

What's the current standard algorithm for optimizing addition chains?
This is of course to minimize the number of multiplications needed to compute powers.

I'd love to find a decent heuristic that doesn't have to be completely optimal, but is better than the double-and-add-if-odd standard binary method.

Ie, for 15, I'd like to get a 6-long chain like

1 2 3 6 12 15

which is better than the binary method which computes the 7-long
1 2 3 4 7 8 15

Knuth's 4.6.3 survey is fun but not too practical.

Currently I'm computing short chains by a pretty simple heuristic.. kind of a poor man's broken dynamic program.

If N is prime, I return the shorter of the binary chain, 1+chain(N-1), or 1+chain(N-2).

if N is factorable into pq, I return the shortest of the binary chain, or
chain(p)+chain(q) for all possible pq.

That heuristic certainly isn't optimal but it seems OK for medium sized n up to 2^32 or so. But surely there's some better methods.

There's explicit tables here. But I'm hoping for a nice little function I can call to get "pretty likely optimal" results.

Huge bonus points if someone did some template metaprogramming in C++ to do this right at runtime!

[Robert Holmes]

If your objective is not to find the absolute best chain, there are a lot of improvements that can be done to the binary method. Bernstein has a survey with focus on exponentiation applications at:

http://cr.yp.to/papers/pippenger.pdf

[jasonp]

GMP-ECM uses Montgomery's PRAC algorithm. His experiments show that the worst case result of the algorithm is within just a few percent of the performance of an optimal addition chain.

[SPWorley]

Originally Posted by Robert Holmes

Bernstein has a survey with focus on exponentiation applications at:

http://cr.yp.to/papers/pippenger.pdf

Excellent, lots of useful details in there!

[SPWorley]

Originally Posted by jasonp

GMP-ECM uses Montgomery's PRAC algorithm. His experiments show that the worst case result of the algorithm is within just a few percent of the performance of an optimal addition chain.

Googling for Montgomery PRAC doesn't turn up anything.
Is this the idea of precomputing a table of 1 x^2 x^3 x^4 x^5 x^6 x^7
(or up to some 2^m -1) and then taking big steps of m bits at once and just doing one table lookup and then m doubling steps?

[akruppa]

PRAC looks for what Montgomery dubbed "Lucas chains," which are addition chains with the extra condition that whenever a+b is formed from earlier chain elements a and b, then a-b must also be in the chain, or must be 0. For example, 1,2,3,6,7 isn't a Lucas chain because you need 6-1=5 to make 6+1=7. However, 1,2,3,5,7 is a Lucas chain. Such chains are needed for arithmetic on elliptic curves in Montgomery form, and for P+1 factoring/primality testing. The relevant manuscript (it was never formally published) is "Evaluating recurrences of form X_{m+n} = f (X_m, X_n, X_{m-n}) via Lucas chains", see ftp://ftp.cwi.nl/pub/pmontgom/Lucas.ps.gz.

Alex

[SPWorley]

Originally Posted by akruppa

PRAC looks for what Montgomery dubbed "Lucas chains," which are addition chains with the extra condition that whenever a+b is formed from earlier chain elements a and b, then a-b must also be in the chain, or must be 0. For example, 1,2,3,6,7 isn't a Lucas chain because you need 6-1=5 to make 6+1=7. However, 1,2,3,5,7 is a Lucas chain. Such chains are needed for arithmetic on elliptic curves in Montgomery form, and for P+1 factoring/primality testing. The relevant manuscript (it was never formally published) is "Evaluating recurrences of form X_{m+n} = f (X_m, X_n, X_{m-n}) via Lucas chains", see ftp://ftp.cwi.nl/pub/pmontgom/Lucas.ps.gz.

Alex, wow, excellent.. I would never have found that. This is also a lot to digest! Thanks.

Knuth was so correct when he wrote that there was a rich and mysterious theory behind efficient addition chains. 30 years later it seems just as true.

[cheesehead]

Originally Posted by SPWorley

Knuth was so correct when he wrote that there was a rich and mysterious theory behind efficient addition chains. 30 years later it seems just as true.

Write him a note! I'm sure he'd appreciate it.

Just be sure to use "snail mail" (as Knuth writes: "So if you want to write to me about any topic, please use good ol' snail mail and send a letter to the following address: ") and send it to the address given on this page: http://www-cs-faculty.stanford.edu/~knuth/email.html

[R.D. Silverman]

Originally Posted by SPWorley

Alex, wow, excellent.. I would never have found that. This is also a lot to digest! Thanks.

Knuth was so correct when he wrote that there was a rich and mysterious theory behind efficient addition chains. 30 years later it seems just as true.

Indeed. AFAIK even today it is not known if finding an optimal
addition chain is in P or whether it is NPC. I suspect the latter.
It may be reducible to the subset-sum problem in some way.

[R.D. Silverman]

Originally Posted by R.D. Silverman

Indeed. AFAIK even today it is not known if finding an optimal
addition chain is in P or whether it is NPC. I suspect the latter.
It may be reducible to the subset-sum problem in some way.

AHA!! It is known to be NPC.

http://scitation.aip.org/getabs/serv...cvips&gifs=yes

[Robert Holmes]

It might still be possible, albeit unlikely, that the special (and more often used) case where m=1 is solvable in P.