Research note

A 422-operation addition chain for P-384 scalar inversion

By Tommy Tai · Published 2026-09-23T21:49:16Z

Abstract

I report a review candidate for inversion modulo the P-384 scalar subgroup order. Its frozen addition-chain certificate computes the exponent $n-2$ in 422 operations: 382 squarings and 40 multiplications of unequal parents. At a model cost of 0.8 per squaring and 1 per other multiplication, the score is 345.6. Independent Python and Node.js checks reconstruct the exact exponent, operation counts, and certificate digest; a C++ reconstruction passed in the linked GitHub Actions run. This is a reproducible arithmetic candidate. I make no claim of a shortest chain, novelty over all prior work, production speed, or suitability as a drop-in implementation.

Problem and accounting

For a nonzero scalar $a$ modulo the P-384 subgroup order $n$, the target exponent for inversion is $n-2$. An addition chain starts at exponent 1. Each row forms a strictly larger exponent by adding two previously available exponents. Equal parents represent a squaring; unequal parents represent another multiplication. I count those operations separately as $S$ and $M$, and report both the total $S+M$ and weighted cost $0.8S+M$. The weight is an evaluation convention, not a runtime measurement.

Construction and search context

I used AI-assisted evolutionary search to propose chain variants, then used deterministic arithmetic checks to judge them. The search varied short prefixes, retained helpers, and the remaining tail. That process can suggest candidates quickly, but a candidate became a result only when I could freeze its full addition chain and reproduce the target and operation counts. The public packet freezes one survivor; it does not claim that the search covered all possible chains.

The candidate uses a 16-operation star prefix reaching 4095, retains helpers $1947=1755+192$ and $2537=2535+2$, builds the $M12\rightarrow M24\rightarrow M48\rightarrow M96\rightarrow M192$ scaffold, and completes a low-192-bit tail. Its recorded accounting is 10S+6M for the prefix, 2M for the helpers, 180S+4M for the scaffold, and 192S+28M for the tail: 382S+40M = 422, with 0.8(382)+40 = 345.6.

The public search map describes the bounded local directions that led to this construction: prefix variants, retained helpers, scaffold ancestors, and tail reuse. It gives no exhaustive search claim or comparable denominator across all experiments. The reproducible result here is the certificate; the search history is bounded provenance, not evidence that a shorter chain cannot exist.

Certificate and verification

The review object is the 422-row decimal certificate, SHA-256 5228f6c12fda873ebb2eecdb34a858a193e92c718efedf81b2c9de4fd72d3d70. Each row gives output left_parent right_parent; the implicit first exponent is 1. The test vector fixes the scalar order, exact $n-2$ target, counts, weight, and digest.

The review package includes independent Python and Node.js certificate parsers and Python, Node.js BigInt, and C++ Boost.Multiprecision reconstructors. On 2026-09-23 UTC, check.py was rerun for this draft: both parsers accepted the committed certificate, its values projection matched, and all 12 altered-certificate controls were rejected. The Python and Node.js reconstructors were also rerun; both regenerated 422 = 382S+40M and the same SHA-256. GitHub Actions run 35923822281, bound to portfolio head 33eaa828, completed the certificate, Python/Node reconstruction, and C++ reconstruction steps successfully. These checks establish arithmetic consistency and reproducibility of this certificate, subject to the independence of those implementations; they are not external adoption or performance results.

Pinned source comparison

The reviewer packet’s source-level tally of ring at commit 840167e gives 382S+48M for p384_scalar_inv_to_mont under the same operation classification. Against that pinned source tally, this candidate has the same number of squarings and eight fewer unequal-parent multiplications: 422 versus 430 total operations, or 345.6 versus 353.6 weighted units. The comparison is to one source revision and one operation model. It does not imply a faster implementation or replaceability without mapping intermediates, checking representation and aliasing, and benchmarking target platforms.

Scope and next verification

The certificate is open for independent review. A next step is to map its retained intermediates into a concrete scalar implementation and test correctness, constant-time behavior, and performance under that implementation’s constraints. A separate prior-art review is needed before any novelty claim. The public portfolio pull request remains a draft review packet.