Module scalar_ring 

Eight-context digit-serial scalar multiply-add modulo the group order l.

A job computes (X * Y + Z) mod l for a 527-bit X (31 digits of 17 bits, stored least significant first and consumed most significant first), a multiplier Y < l, and an addend Z < l. Signing uses two jobs per signature:

• r = H(prefix || M) mod l with Y = 1, Z = 0;
• S = H(R || A || M) * a + r mod l, which equals k * a + r for k = H(R || A || M) mod l without a separate reduction.

Each Horner step is u = acc * 2^17 + x_d * Y, then, with l = 2^252 + c, acc' = (u mod 2^252) + l - (u >> 252) * c. Because 2^252 = -c (mod l), acc' is congruent to u. The invariant acc < 2^254 keeps every quantity bounded: u < 2^271 + 2^17 * l < 2^272 (sixteen digits), so t = u >> 252 < 2^20 and t * c < 2^145 < l, which makes l - t * c positive and acc' < 2^252 + l < 2^254. A step is an eight-stage pipeline, and eight independent contexts circulate through it, so the datapath retires one step per cycle: 15 + 8 DSP-sized products and no wide fabric multiply.

Final reduction

After 31 steps the finisher forms S = acc + Z (below 2^254 + l) in one clock and reduces it modulo l in two more. Because l = 2^252 + c with c < 2^125, the estimate k0 = S >> 252 is the true quotient or one more, so the first clock computes S - k0·l (one 256-bit subtraction; k0·l is a small constant table, see k_times_l_low) and the second adds l back if that went negative. The earlier single-clock version subtracted four multiples of l at 340 bits and picked one, which Vivado routed at 5.13 ns, 0.27 ns over the 205 MHz period; it was the only failing path in the small core.

The finisher holds one job at a time. A context that completes its last step while the finisher is busy parks: it keeps its slot and its final accumulator, and retries each time it comes around to stage 8.

Structs

ScalarDone

Completed result, held until out_ready.

ScalarJob

One multiply-add job (X * Y + Z) mod l, presented on ScalarRingIn::job.

ScalarRing

Digit-serial scalar ring: eight contexts, one Horner step per cycle, and a two-clock finisher.

ScalarRingIn

Ring inputs.

ScalarRingOut

Ring outputs.

Functions

add_l2

Two-limb addition modulo 2^170.

add_l4

Four-limb addition modulo 2^340.

bytes_from_digits

Host helper: digits back to 32 little-endian bytes. Fifteen digits cover bits 0..255, so the bit < 256 guard never drops a set bit.

digits17

Host helper: split little-endian bytes into D 17-bit digits, least significant first. Bits past the end of bytes read as zero.

k_times_l_low

Low 128 bits of k * l for k = 0..8 (the high 128 bits are k << 124).

limbs_to_w256

Bits 0..256 of four 85-bit limbs as two 128-bit words.

order_c_digits

c = l - 2^252 in eight 17-bit digits, least significant first. The top digit is 41, so c < 2^(7 * 17 + 6) = 2^125.

order_l_digits

l in fifteen 17-bit digits: the digits of c plus 2^252, which is bit 14 of digit 14 (252 = 14 * 17 + 14).

pack16

Sixteen digits into four 85-bit limbs (the last limb holds one digit).

scalar_ring_kernel

State transition for ScalarRing.

sub_l4

Four-limb subtraction; returns a - b mod 2^340 and whether it borrowed.

unpack16

Inverse of pack16: bits above 272 are dropped.

w256_to_digits15

Fifteen 17-bit digits of a value below 2^255 held in two 128-bit words.

widen15

Fifteen digits widened to sixteen (top digit zero), so a 255-bit value can go through pack16.