Module programs 

The elliptic-curve programs the field machines run.

Program	Bundles	Multiplies	Use
fixed_base	392	378	[r]B for signing and key expansion
fixed_base_affine	657	645	[r]B plus its own inversion (fused mode)
batch_compress(32)	423	422	affine x, y of 32 points with one inversion

Each is plain Rust against Builder, compiled to bundles, and checked against curve25519-dalek through the interpreter in this module’s tests. The verification and key-loading programs (verify_known_key, decode_candidate, table_bases, digit_table) are built the same way.

The fixed-base walk

[r]B = Σ dᵢ · (2^offsetᵢ · B): one table per digit, so no doublings. Each digit costs one 7-multiply mixed addition, and each lookup costs one table scan step per entry pair. Choosing the digit sizes balances the two:

The chosen recoding (host::recode) has 39 signed radix-32 digits and 15 signed radix-16 digits (255 bits; every scalar here is reduced mod l first, so the top digit stays small). How the program went from 492 to 392 bundles:

Change	Bundles
Dalek’s radix-16 walk: 64 additions, 4 doublings, two interleaved chains	492
one table per digit (no doublings); chains start from their first lookup (3 multiplies, not 7)	458
mixed radix 32/16, digits in order	435
radix-16 lookups interleaved among radix-32 ones	399
lookup order from a search with the real scheduler (LOOKUP_ORDER)	392

Additions commute, so the order is free. In digit order the long scans come first and starve the multiplier; interleaving keeps both busy. The result fills the multiply, add and scan slots 96 %, 97 % and 95 %.

Batch compression

Encoding needs 1/Z (265 multiplies by Fermat’s little theorem). Montgomery’s trick inverts the product of 32 Zs once and recovers each inverse with three more multiplies: 13.2 per point instead of 265.

Key loading

A verification key A arrives as a 32-byte encoding, and verification needs the fixed-base table of -A. Three programs build it, none of them branching: decode_candidate computes both square-root candidates (the controller picks one), table_bases walks the 54 bases 2^offset(i) · (-A) by doubling, and digit_table turns each base into its 8 or 16 affine Niels entries with one shared inversion.

Constants

LOOKUP_ORDER

Lookup order of the fixed-base walk (see the module docs).

Functions

batch_compress

Batch affine conversion of g points held in bank I as X, Y, Z triples.

decode_candidate

Key loading, step 1: square-root candidate for a point with y in input 0. Outputs x (0), x * sqrt(-1) (1), v * x^2 (2) and u (3) with u = y^2 - 1, v = d y^2 + 1. The controller takes x if v x^2 = u, x sqrt(-1) if v x^2 = -u, and rejects the point otherwise, then applies the sign bit; the program never branches.

digit_table

Key loading, step 3: the entries table entries e * Q (e = 1..) of a projective base Q (inputs 0..4 = X, Y, Z, T) in affine Niels form, normalized with one shared inversion. Output 3(e-1) + c is coordinate c (y+x, y-x, 2dxy) of entry e.

fixed_base

Fixed-base scalar multiplication. Outputs projective X, Y, Z (indices 0..3).

fixed_base_affine

Fixed-base multiplication followed by its own inversion: outputs affine x (index 0) and y (index 1). Used when no batch-compress machine exists.

table_bases

Key loading, step 2: the 54 table bases 2^offset(i) * P of an affine point P = (x, y) (inputs 0, 1), as projective X, Y, Z, T, in digit order (output 4i + c, counted by the controller).

verify_known_key

verify_known_key_ordered with the key chain in LOOKUP_ORDER.

verify_known_key_ordered

Known-key verification core: [S]B + [k](-A) as two fixed-base walks.