2010/09/10 by Neill Michael Clift · 1 citation
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #graph theory and CDMA systems #Cryptography and Residue Arithmetic #Conjecture #Chain (unit) #Mathematics #Combinatorics #Sequence (biology) #Discrete mathematics #Physics
paper · pdf · doi:10.1007/s00607-010-0118-8
openalex publication_date 2010/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
An addition chain is a finite sequence of positive integers 1 = a 0 ≤ a 1 ≤ · · · ≤ a r = n with the property that for all i > 0 there exists a j, k with a i = a j + a k and r ≥ i > j ≥ k ≥ 0. An optimal addition chain is one of shortest possible length r denoted l(n). A new algorithm for calculating optimal addition chains is described. This algorithm is far faster than the best known methods when used to calculate ranges of optimal addition chains. When used for single values the algorithm is slower than the best known methods but does not require the use of tables of pre-computed values. Hence it is suitable for calculating optimal addition chains for point values above currently calculated chain limits. The lengths of all optimal addition chains for n ≤ 232 were calculated and the conjecture that l(2n) ≥ l(n) was disproved. Exact equality in the Scholz–Brauer conjecture l(2 n − 1) = l(n) + n − 1 was confirmed for many new values.