nx_p256_field_mul.nx

nx_p256_field_mul.nx -- P-256 prime field multiplication. Phase 0b §I.3 piece 1c of the ECDSA-P256 arc. Composes: - u256_mul_wide (commit ddb0994a) for the 256x256 -> 512 - NIST P-256 Solinas fast reduction mod p (THIS version) FAST REDUCTION (Solinas, FIPS 186-4 / Hankerson Alg. 2.29): p = 2^256 - 2^224 + 2^192 + 2^96 - 1 has a special form that lets the 512-bit product be reduced with a fixed sequence of 32-bit-word permutations + a handful of 256-bit add/sub, instead of the bit-serial 257-iteration long division. ~10-15x fewer limb ops. Given product words c0..c15 (c0 = least significant 32-bit word): s1 = (c7,c6,c5,c4,c3,c2,c1,c0) s2 = (c15,c14,c13,c12,c11, 0, 0, 0) s3 = ( 0,c15,c14,c13,c12, 0, 0, 0) s4 = (c15,c14, 0, 0, 0,c10,c9,c8) s5 = (c8,c13,c15,c14,c13,c11,c10,c9) s6 = (c10,c8, 0, 0, 0,c13,c12,c11) s7 = (c11,c9, 0, 0,c15,c14,c13,c12) s8 = (c12, 0,c10,c9,c8,c15,c14,c13) s9 = (c13, 0,c11,c10,c9, 0,c15,c14) r = s1 + 2*s2 + 2*s3 + s4 + s5 - s6 - s7 - s8 - s9 (mod p) (tuples are (word7..word0); word7 is the most significant.) The previous bit-serial reducer is RETAINED as p256_field_mul_slow: it is the trivially-correct gold-standard ORACLE the fast path is validated against (nx_p256_field_mul_oracle_test.nx checks fast == slow over many random inputs). Per Cardinals 13 + 25: additive -- the reference is never stripped. Public API: u256_wide_shr_1(buf) -- in-place 1-bit right shift u256_wide_sub(out, a, b) -- 16-limb subtract w/ borrow p256_field_mul(out, a, b) -- (a*b) mod p, canonical (FAST) p256_field_mul_slow(out, a, b) -- (a*b) mod p, canonical (oracle) p256_field_sq(out, a) -- (a*a) mod p, canonical Aliasing: out MAY alias a or b (computation uses fresh scratch).