Faster Inversion Modulo 2255 − 19 on AArch64
My latest implementation of inversion modulo \(p=2^{255}-19\) takes about 3,272 cycles on a Raspberry Pi 5. It combines 24-step batching, a final reduction that overlaps output conversion, and scalar lookahead that computes the low bits needed by the next batch.
This post explains these three optimizations and how they work together. The implementation continues my work on accelerating and verifying constant-time modular inversion.
Why pack f, u, and v together?
In SafeGCD / Bernstein–Yang inversion, each divstep updates two integers \(F,G\) by selecting, adding or subtracting, and dividing an even value by two. The choices depend on parity and the control state \(\delta\). For a batch of \(n\) steps, the low \(n\) bits of \(F,G\), together with \(\delta\), are enough to determine all those choices. Each division consumes one bit of precision; the high bits are unnecessary for computing the batch's matrix.
The scalar kernel works with low-bit values \(f,g\), while NEON holds the
full integers \(F,G\). The matrix records the row operations chosen by the
divsteps. This suggests keeping each low-bit value together with its matrix
row: \((f,u,v)\) in
one 64-bit register, called fuv, and \((g,r,s)\) in another,
called grs. An addition of the packed registers then updates
all three components together. Conditional selection, negation, and shifting
can likewise operate on a whole packed row.
To make division by two work for the coefficients as well, the coefficient matrix starts at \(-2^n I\).1 This initial scaling supplies the factors of two needed by the shifts; at the end of the batch, the coefficients give the negative of the desired integer matrix. For example, a step that replaces \(g\) by \((g+f)/2\) simultaneously replaces its scaled coefficient row \((r,s)\) by \(((r+u)/2,(s+v)/2)\). The common arithmetic is what makes packing useful.
From the old 20-step layout to 24 steps
The earlier kernel already used this idea. At batch entry, its 20-step layout stores the low 20 bits of \(F,G\) as \(f_{\mathrm{low}},g_{\mathrm{low}}\):
20-step packing as addition. Each row is one addend; all rows share the same bit positions. Colored spans show the available widths: 21 bits per coefficient and 20 bits for the initial residue. They do not indicate which bits are nonzero. Hatched regions are sign extension, not additional coefficients.
The upper coefficient ends at bit 62, leaving bit 63 for sign redundancy during addition or subtraction before the arithmetic right shift.
Here \(u,v,r,s\) denote the scaled coefficients inside the packed loop. The layout allows 21 bits for each signed final coefficient and enough space below them to run all 20 steps without an intermediate cleanup. The coefficients are rounded and extracted at the end.
Extending the batch from 20 to 24 steps increases the signed coefficient width from 21 to 25 bits. To fit both coefficients in the same register, the 24-step layout moves their starting positions from bits 21 and 42 to bits 13 and 38:
24-step packing. Each colored coefficient span has room for a 25-bit signed value. The amber underline marks bits 23–13, where the initial low residue overlaps the lower coefficient's nominal span.
The initial low residue now reaches into the lower coefficient's span. This works because the coefficients begin as multiples of \(2^{24}\), with their low 24 bits zero. As divsteps proceed, the coefficient scale is gradually consumed, while fewer residue bits are needed to determine the remaining steps.
After 12 divsteps, only the low 12 bits of \(f,g\) are still needed. The higher residue bits no longer affect the remaining divstep decisions, but they still contribute to the packed word. Since \(u,r\) start at bit 13, leaving those bits in place can cause part of the residue to be read as part of \(u\) or \(r\) during coefficient extraction. The final rounding alone cannot always separate them, so the batch can return an incorrect matrix.
Canonicalization removes the no-longer-needed part of the residue while preserving these low bits and the encoded matrix coefficients. This cleans up the packed representation; it does not reduce a value modulo \(p\). The kernel does this by adding a rounding bias of \(2^{24}\) and clearing bits 12 through 24 in each packed register. The resulting representation is:
After canonicalization. The coefficient positions and 25-bit widths are unchanged; both low residues now occupy only bits 11–0. The coefficients still carry a factor of \(2^{12}\), so packed bits 12–24 are zero in both registers at this point.
The kernel can now run the remaining 12 divsteps, then combine the final rounding with coefficient extraction. One intermediate canonicalization thus buys four more steps per batch, reducing the frequency of full multiprecision updates. Increasing the batch size further would require more frequent canonicalization, making this a balance between the two costs.
Once the batch is complete, the extracted coefficients are negated to recover the transition matrix. NEON then applies it to the full-precision \(F,G\):
From this point on, \(u,v,r,s\) denote the entries of this transition matrix after sign correction. The division by \(2^{24}\) is exact. NEON also updates \(V,S\), maintaining \(F\equiv aV\pmod p\) and \(G\equiv aS\pmod p\) for the original input \(a\). For a nonzero input residue, the algorithm ends with \(F=\pm1\), giving the inverse \(FV\bmod p\).
All four values use nine radix-\(2^{30}\) limbs, with a signed top limb. The complete inversion uses 12 initial divsteps followed by 24 batches of 24, for 588 steps in total. The final block converts the internal representation into the output format.
Combining reduction and output conversion
The final result must be reduced to \([0,p)\) and converted from nine radix-\(2^{30}\) limbs into four 64-bit words. If reduction is completed entirely in NEON first, the output conversion has to wait.
These tasks can overlap. As the final update produces the low limbs, the kernel transfers them to scalar registers and begins assembling the output words while NEON continues computing the upper limbs. Once the top limb is ready, a correction to the assembled scalar value finishes the reduction. The following decomposition explains why this works.
Let \(T\) be the updated \(V\), before applying the final sign of \(F\). Write it as
Here \(L\) contains the eight lower limbs, and \(t_8\) is the signed top limb. Since \(p=2^{15}2^{240}-19\), removing a multiple of \(2^{15}\) from \(t_8\) amounts to removing a multiple of \(p\), provided we compensate for the \(-19\). Choose \(q\) by rounding \(t_8/2^{15}\) to the nearest integer:
This leaves a remainder centered around zero, \(-2^{14}\leq\rho<2^{14}\). Subtracting \(qp\) from \(T\) then gives
The lower part \(L\) is unchanged in this expression, so its limbs can be assembled before \(q\) is known. When the top limb arrives, the kernel uses \(\rho\) in its place, then adds the signed correction \(19q\), propagating carries across the four output words. This produces the centered result without a separate reduction pass over the vector limbs.
The centered top limb keeps \(L+\rho2^{240}\) in \([-2^{254},2^{254})\). The final update keeps \(t_8\) within a signed 64-bit value, which bounds the correction by \(|19q|<2^{53}\). Together, these give \(|Y|<2^{254}+2^{53}<p\). Applying the sign of \(F\) preserves this bound: the result is already in \((-p,p)\), so a single conditional addition of \(p\) makes a negative result canonical.
Earlier batches still perform modular corrections and carry propagation, but their bounded intermediate values need not be in \([0,p)\). Only the final output needs that canonical form.
Shortening the divstep feedback path
Without lookahead, scalar divsteps can already overlap much of the NEON update. The next batch still waits for NEON's new low bits of \(F,G\) to be transferred to scalar registers and packed for the divsteps.
The next batch needs only the low 24 bits of each updated value. Computing those bits directly with scalar arithmetic can shorten the wait. This is low-bit lookahead, or fast-forwarding (FF) the divstep feedback.
The update \(F'=(uF+vG)/2^{24}\) divides the numerator exactly by \(2^{24}\), shifting its bits right by 24 places. The bits needed by the next batch are therefore bits 24–47 of \(uF+vG\).
To compute those bits, we can ignore everything above bit 47 in \(F,G\): higher input bits contribute only to higher product bits. Let \(f_{48}=F\bmod2^{48}\) and \(g_{48}=G\bmod2^{48}\). Then
The same calculation applies to \(G'\) and works for signed values and
coefficients as well. Ordinary 64-bit multiply-add arithmetic preserves
the required low 48 bits, so each row needs only a mul, a
madd, and an extraction of bits 24–47.
With lookahead, the matrix feeds two paths. A short scalar calculation prepares the next divstep input, while NEON applies the matrix to the full state.
At loop entry, the low24 input is already prepared, so scalar divsteps can run alongside the full update of the pending matrix. As NEON produces fresh low48 values, they become available for lookahead with the new scalar matrix, preparing the following batch's input.
The implementation uses the packed kernel's negative matrix directly for lookahead, so the prepared input represents the low bits of the next state with both signs reversed: \((-F',-G')\). Negating both values preserves parity and the divstep branch sequence for the same \(\delta\), avoiding a sign conversion on this path.
Lookahead trades a small amount of extra scalar arithmetic for a shorter dependency between batches.
Scheduling with SLOTHY
Lookahead creates opportunities for overlap, but the instruction order and register assignments determine how well the processor can use them. SLOTHY, introduced by Abdulrahman et al., automates this part of assembly development. The programmer supplies the algorithm and instruction choices in readable assembly; SLOTHY searches for register assignments and schedules using a processor model. It uses constraint solving to respect data dependencies and register limits while accounting for instruction latencies and execution resources. [1]
For this inversion kernel, the starting point is symbolic assembly: temporary values have descriptive names, while registers that carry state between blocks are fixed. The lookahead computation is already part of that source. Here, SLOTHY is used in two passes:
- Allocate registers. A first pass assigns physical registers to the symbolic temporaries in the initialization, main loop, and final block. Instruction order is preserved, and spills to memory are forbidden.
- Schedule overlapping windows. A second pass optimizes each block in overlapping windows using SLOTHY's splitting heuristic. This keeps the solver's problems manageable while allowing scalar divsteps, NEON arithmetic, and register transfers to be interleaved. The overlap lets successive windows reconsider earlier scheduling choices. [2]
The A72- and A76-tuned versions below use schedules selected by measurements on each core.
Overall performance
The selected implementations are compared below with the specialized inversion routines from s2n-bignum and lib25519. These are measurements of complete inversion calls, rounded to the nearest cycle; each core favors a different schedule of the same FF implementation.
| Implementation | A72 | A76 |
|---|---|---|
| FF tuned for A72 | 3,917 | 3,316 |
| FF tuned for A76 | 3,998 | 3,272 |
s2n-bignum inv_p25519 [3] | 6,095 | 5,550 |
lib25519 safegcdneon [4] | 7,942 | 5,522 |
Measured on a Pi 400 (A72, 1.8 GHz) and Pi 5 (A76, 2.4 GHz). Results are medians from repeated warm-cache calls, with paired empty-baseline subtraction. All versions use the same fixed input below \(2^{255}\), nonzero modulo \(p\), and include their original wrappers.
Conclusion
Batching 24 divsteps with one intermediate canonicalization reduces the frequency of full multiprecision updates. Combining final reduction with output conversion lets scalar registers assemble the finished low digits while NEON computes the upper digits. Low-bit lookahead shortens the path to the next batch's input, allowing scalar divsteps to overlap more of the full update.
With SLOTHY handling register allocation and instruction scheduling, these three changes bring inversion to 3,917 cycles on Cortex-A72 and 3,272 cycles on Cortex-A76, using a schedule selected for each core.
Code: the public implementation repository contains the Pi 5 implementation, correctness tests, and a benchmark runner.
Related: Measuring SMULL-to-SMLAL Accumulator Forwarding on Cortex-A76.
References
- Amin Abdulrahman, Hanno Becker, Matthias J. Kannwischer, and Fabien Klein. Fast and Clean: Auditable high-performance assembly via constraint solving. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024(1), pp. 87–132. DOI: 10.46586/tches.v2024.i1.87-132. Open-access preprint. Sections 4–5 describe the constraint model and optimization framework.
- SLOTHY contributors. SLOTHY project documentation and official tutorial, including register allocation and the splitting heuristic.
-
s2n-bignum contributors.
AArch64
bignum_inv_p25519implementation. The table abbreviates the routine name asinv_p25519. -
lib25519, release 20260614,
crypto_pow/inv25519/arm64-safegcdneon. The official implementation credits identify Kaushik Nath as its author.