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.

  • $\begingroup$ Suitable on cstheory perhaps? $\endgroup$ – 1.. Mar 23 '15 at 4:28
  • $\begingroup$ 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. $\endgroup$ – The Masked Avenger Mar 23 '15 at 5:16
  • $\begingroup$ "Do you want to generate the products additively": Yes. This is for raising powers, so there's no shortcuts. $\endgroup$ – Jason S Mar 23 '15 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.