Short Addition Chains for Cryptographic Exponents

For mathematical definitions see the top-level Addition Chains.

Field and scalar inversions and square roots in elliptic curve cryptography are often computed in constant time as a fixed power \(x^n\), using a fixed addition chain for \(n\). The chain length is the number of field squarings plus multiplications. This page lists short chains for several standard exponents, including contributions from other searchers. Best known means best known to this page; it does not assert optimality. Every chain can be downloaded and checked.

Preliminary results; updated 2 November 2026.

New Records

The squarings and multiplications column gives the operation counts when the chain is used for exponentiation. The column \(s\) is the number of small steps in the new chain, so \(l(n)\le\lambda(n)+s\) and \(s(n)\le s\). The number of multiplications can exceed \(s\), because an addition that increases \(\lambda\) counts as a multiplication but not as a small step. The column \(s(n)\ge\) is the best known lower bound (currently from an older program called crouton).

[1] B. Smith, The Most Efficient Known Addition Chains for Field Element & Scalar Inversion. [2] M. McLoughlin, addchain results. [3] M. Scott, On inversion modulo pseudo-Mersenne primes, ePrint 2018/1038 (Table 1, counted as \(k-1\) squarings plus the multiplications listed). [4] Length from running the addchain ensemble; no published figure was found.

Scalar Inversions

Brian Smith supplied the following chains on 1 November 2026. They are the best known to this page for the scalar inversion exponents \(n=q-2\), where \(q\) is the group order. All 1,013 supplied chains have been independently checked using exact integers: each begins at 1, every later element is the sum of two earlier elements, and each ends at the appropriate group order minus two. All chains in each collection are distinct by their numerical entries.

The operation counts describe a cheapest example within each supplied collection under Smith's illustrative cost model: one squaring costs 0.8 multiplications, giving cost \(0.8S+M\). Actual relative costs depend on the implementation. None of these lengths is proved optimal.

Each download contains one chain in the one-integer-per-line format below. The selected example has the lowest weighted cost among the supplied chains of the shortest supplied length for that curve.

Smith reports using evolutionary search and a dynamic programming approach to tail addends, with promising heads handled separately. These are search methods, not proofs of global optimality. His P-256 and P-384 results supersede the dictionary-method chains previously found here (lengths 286 and 431). The earlier published scalar lengths on Smith's 2017 page were 292 (P-256), 283 (Curve25519), 290 (secp256k1), and 433 (P-384).

Source: personal communications from Brian Smith and his chain collection dated 1 November 2026; validation performed 2 November 2026. The P-384 result updates the previously reported length 420 to 419. The previously recorded small-step lower bounds remain 9 for P-256 and P-384; no new lower-bound computation is claimed here.

The column \(s=\text{length}-\lfloor\log_2 n\rfloor\) gives the number of small steps in the displayed chain, so \(s(n)\le s\). The column \(s(n)\ge\) records lower bounds on the minimum number of small steps, where \(s(n)=\ell(n)-\lfloor\log_2 n\rfloor\). A dash indicates that no lower bound is recorded here. These bounds can be updated independently of the example chains.

File Format

Each file lists the chain one element per line in increasing order, starting at 1 and ending at \(n\). Each element after the first is the sum of two earlier elements (possibly the same element twice). The number of lines minus one is the chain length.

How the Chains Were Found

Field exponents. Most field exponents have the form \(2^k-c\) or consist of a few long runs of ones. Typical chains build \(2^m-1\) with an exponent chain for \(m\) and append the remaining bits. The new chains choose the opening of the chain (the head) so that it produces both a seed \(2^a-1\) and the constant needed for the low bits, at no extra cost. For example, the Curve1174 chain starts 1, 2, 4, 8, 16, 20, 21, 42, 63, which gives \(2^6-1\) and 21 together. It then builds \(2^{246}-1\) from \(2^6-1\), and finishes with \((2^{246}-1)\cdot 2^5+21\). Every head below 512 and every minimal exponent chain was searched exhaustively within this structure.

Learning from truncated exponents. To find structures the run model misses, each exponent was shrunk to a family of 64-bit numbers with the same low bits and a shorter top run. Optimal chains for these were computed exactly with ac2fastfg. Where the optimal small instances beat the best constructed chain consistently as the run grew, the optimal chains were decoded and the mechanism rebuilt at full size. This is how the P-192 chain was found. With \(a=t-1\) and \(n=2^{3t}-2^t-3\) (P-192 has \(t=64\)):

\(P = 4(2^a-1)+1,\quad T = (2^a-1)\cdot 2^{t+1}+P = 2^{2t}-3,\quad n = T\cdot 2^t + P.\)

Only \(2^{63}-1\) has to be built. The second long run comes from a carry instead of a second exponent chain.

Scalar exponents. The low halves of scalar exponents are essentially random. The superseded chains (P-256: 286, P-384: 431) came from a dictionary method: \(n\) was written as a sum of terms \(d_i 2^{e_i}\), all the \(d_i\) were built with one addition sequence, and the decomposition was optimised by simulated annealing. The truncation method does not help for exponents of this kind.

What Is and Is Not Known

None of these lengths is proved optimal. The size of the exponent is not the obstacle. Exact search handles exponents of several hundred bits when the number of small steps is small (fewer than about 9), and possibly more when the exponent's Hamming weight is large. These chains need 10 to 14 small steps for the field exponents, and the best scalar chains need 26 (P-256), 36 (P-384) and 27 (secp256k1). Both are beyond what exact search can currently settle. The truncation experiments give evidence for some of them:

• For \(2^k-c\) with \(c\in\{5,11,19,107,119,189\}\), the constructed chains matched the exact optimum on every truncated instance with \(50\le k\le 62\), except one. This suggests that 230, 232, 261, 393, 395, 424 and 524 are optimal or very close to it.
• For secp256k1, Goldilocks and the Goldilocks square root, the truncated instances beat the constructed chains only through coincidences between the run lengths that do not occur at full size.
• For secp192k1 and secp224k1 the truncated instances beat the constructed chains only for some lengths \(m\) of the top run. When \(m\) is even, the top bits are \(3Y\) for an alternating binary number \(Y\) with one phase break. When \(m\equiv 1 \pmod 4\), the top bits are \(5Y\) for a period-4 pattern \(Y\). The secp192k1 truncations with \(m\equiv 3\pmod 4\) (\(m=11, 19\)) matched the constructed chains exactly. The full-size top runs, 159 and 191, are both \(\equiv 3 \pmod 4\). Multipliers \(2^j+1\) with \(j\ge 3\) have not been ruled out. The only truncation small enough to test that has the same residues as 159 modulo 4, 6 and 8 is \(m=15\).
• For P-192 the gap persisted at every truncated size and carried over to full size, giving 202.

Exponents where this work only matched the best known: Curve25519 field inversion (265), P-256 field inversion (266), P-384 field inversion (396), P-224 (234), Goldilocks (460), secp192k1 (205), secp224k1 (238), the Curve25519 \(2^{252}-3\) exponent (262), the secp256k1, P-256, Goldilocks and P-521 square roots, and the former Curve25519 scalar inversion result (283, now superseded by Smith's 275-step chain above).

Neill Clift, neillclift@live.com