# addition chains for products of relatively prime factors

Suppose I have a set $F$ consisting of relatively prime factors (e.g. $\{ 5, 7, 9, 13, 17 \}$) and the set $P = \{\prod_{f \neq f_i}f \}$ consisting of the products of N-1 factors in $F$ (e.g. $\{13923, 9945, 7735, 5355, 4095\}$).

Is there a special structure in these numbers that would allow writing a short addition chain? I'm looking into Pippenger's algorithm as described in Daniel Bernstein's paper but it doesn't seem to take advantage of the redundancy in this case.

• Suitable on cstheory perhaps? – T.... Mar 23 '15 at 4:28
• A short addition chain for what? Do you want to generate the products additively, or are you given the products and want to make something else? Note that the set of n numbers can be generated using less than 3n multiplications and no divisions, if you are concerned about speed. – The Masked Avenger Mar 23 '15 at 5:16
• "Do you want to generate the products additively": Yes. This is for raising powers, so there's no shortcuts. – Jason S Mar 23 '15 at 14:30