nx_u2048_smallops.nx

nx_u2048_smallops.nx -- F103e RUNG 6: big-by-SMALL arithmetic (mul, div, mod, add). WHY THIS SHAPE, and not a general extended GCD: RSA needs d = e^-1 mod lambda(n). The textbook route is a binary extended GCD over 2048-bit values, which needs (x + m) >> 1 -- and x + m OVERFLOWS 2048 bits, while u2048_shr1 has no carry-in. That is a real trap, not a style choice. The route taken instead exploits the fact that **e is small** (65537). Write: k*lambda + 1 = d*e with k in [1, e-1] Then k = -(lambda mod e)^-1 mod e -- an inverse of a SMALL number modulo a SMALL number, solvable in plain i64 -- and d = (k*lambda + 1)/e, which is a big-by-small multiply and a big-by-small divide. Every intermediate fits in an i64 because the limbs are 32-bit: divide: rem < m <= 2^31, so (rem << 32) | limb < 2^63 -- proven by the bound, not hoped multiply: (2^32-1)*(2^31-1) + carry < 2^63 ★★★★★★ **THE PRIMITIVE YOU NEED IS OFTEN NARROWER THAN THE ONE THE TEXTBOOK NAMES — AND THE NARROW ONE CAN BE EXACTLY THE ONE THAT FITS IN THE REGISTERS YOU HAVE.** A general u2048 modinv is a much larger, more dangerous organ than this, and RSA does not need it. ★THE ORACLE IS PLAIN i64 ARITHMETIC. Every tooth loads a value that fits in 64 bits, runs the u2048 path, and demands agreement with the `*`, `/`, `%` the compiler already gives us. Two independent implementations; no recalled constants anywhere. Usage: nx_u2048_smallops selftest Exit: 0 GREEN | 1 RED. Log -> knowledge/status/nishi_os.log, verdict= LAST. license_tier: ORIGINAL