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 chains that are shorter than the best previously published for several standard exponents. Every chain can be downloaded and checked.
Preliminary results, October 2026.
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 column \(s(n)\ge\) is the best known lower bound (currently from an older program called crouton).
| Exponent | \(n\) | Previous best | New length | Squarings + mults | \(s\) | \(s(n)\ge\) | Chain |
|---|---|---|---|---|---|---|---|
| secp256k1 field inversion | \(p-3 = 2^{256}-2^{32}-980\) | 269 [1,2] | 268 | 255 + 13 | 13 | 10 | download |
| NIST P-192 field inversion | \(p-2 = 2^{192}-2^{64}-3\) | 203 [2] | 202 | 190 + 12 | 11 | 9 | download |
| M-221 field inversion | \(p-2 = 2^{221}-5\) | 231 [2] | 230 | 220 + 10 | 10 | 10 | download |
| E-222 field inversion | \(p-2 = 2^{222}-119\) | 233 [2,3] | 232 | 220 + 12 | 11 | 10 | download |
| Curve1174 field inversion | \(p-2 = 2^{251}-11\) | 263 [2] | 261 | 250 + 11 | 11 | 10 | download |
| E-382 field inversion | \(p-2 = 2^{382}-107\) | 395 [2,3] | 393 | 381 + 12 | 12 | 10 | download |
| M-383 / Curve383187 field inversion | \(p-2 = 2^{383}-189\) | 396 [2] | 395 | 381 + 14 | 13 | 10 | download |
| Curve41417 field inversion | \(p-2 = 2^{414}-19\) | 426 [2] | 424 | 413 + 11 | 11 | 10 | download |
| M-511 field inversion | \(p-2 = 2^{511}-189\) | 525 [2,3] | 524 | 509 + 15 | 14 | 10 | download |
| NIST P-521 field inversion | \(p-2 = 2^{521}-3\) | 533 [3,4] | 532 | 520 + 12 | 12 | 10 | download |
| NIST P-384 square root | \((p+1)/4\) | 395 [4] | 394 | 381 + 13 | 13 | 9 | download |
| NIST P-256 scalar inversion | \(q-2\), \(q\) the group order | 292 [1] | 286 | 247 + 39 | 31 | 9 | download |
| NIST P-384 scalar inversion | \(q-2\), \(q\) the group order | 433 [1] | 431 | 369 + 62 | 48 | 10 | download |
[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.
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.
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, so these chains come from a dictionary method: \(n\) is written as a sum of terms \(d_i 2^{e_i}\) and all the \(d_i\) are built with one addition sequence. The decomposition was optimised by simulated annealing over splitting and merging digits, with each candidate costed by building the full chain using the addchain library. These are heuristic results and are probably not optimal.
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 over 30 for the scalars, which is beyond what exact search can currently settle. The truncation experiments give evidence for some of them:
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 secp256k1 (290) and Curve25519 (283) scalar inversions.
Neill Clift, neillclift@live.com