# CLAUDE.md

**cnfy-uint** — A pure Rust 256-bit modular arithmetic library (edition 2024, no external dependencies). Provides mathematical primitives built around a `U256` 256-bit unsigned integer type. All hot-path methods are `#[inline]` for cross-crate inlining.

## U256 Internal Layout

`U256([u64; 4])` in **little-endian** order: `[w0, w1, w2, w3]` where `w0` is the least significant limb and `w3` is the most significant. Uses a manual `Ord` impl that compares from MSB (`w3`) downward for correct numerical ordering. The `from_be_limbs` API reverses input internally, so call sites are unchanged.

## Modular Arithmetic Strategy

Two reduction paths exist for modular operations like `mul_mod` and `square_mod`:
- **Sparse prime fast path**: When `2^256 - modulus` fits in a single `u64` (e.g. secp256k1's P where complement = `0x1000003D1`), uses folding reduction with ~5 u64 multiplies.
- **Generic path**: Knuth's Algorithm D with MG10 reciprocal-based quotient estimation (`rem_wide`).

`mod_inv` uses Lehmer's extended GCD algorithm with two-phase inner loop (u64/u128), wrapping 256-bit coefficient tracking, and local `sub4`/`add4` helpers on raw `[u64; 4]` arrays. With `--features ct-inv`, switches to SafeGCD (Bernstein-Yang divsteps).

## Extended Types

`U320`, `U384`, `U512` for intermediate calculations (wide multiplies, carries). Follow the same struct-per-directory pattern.

## Internal Algorithm Structs

- **`GcdState`** — Lehmer's GCD state machine (extended GCD with cofactor tracking).
- **`KnuthD`** — Algorithm D division (generic modular reduction path).
- **`LehmerStep`** — GCD inner loop (approximate quotient via leading limbs).

## U256Batch

`U256Batch<const N: usize>` — Montgomery's trick for batch modular inversion. Three phases: forward sweep (prefix products), single inversion, backward sweep. Cost: 1 `mod_inv` + 3(N-1) `mul_mod`. Amortizes inversion from ~800ns to ~44ns/element at large N.

## Constant-Time Feature Flags

Granular compile-time feature flags switch dispatchers to constant-time paths:
- `ct-field`: `add_mod`, `sub_mod`, `mul_mod_sparse`, `square_mod_sparse`, `sparse_reduce`, `modulo`
- `ct-inv`: `mod_inv` (SafeGCD); implies `ct-field`
- `ct-pow`: `pow_mod` (always 256 iters); implies `ct-field`
- `ct`: umbrella enabling all of the above

## Reference Implementations

The `.ar/` directory contains working reference implementations that need to be rewritten idiomatically with a focus on performance:

- **`.ar/bytes/`** — Byte-level operations: bit manipulation, conversions (`into_array`, `into_bits`, `as_u128`, `as_u256`), arithmetic helpers (`double`, `halve`, `negate`), utilities (`leading_zeros`, `is_zero`, `is_even`, `trim`, `shrink`, `fill`, `shift`, `scale`, `chunk`), and point operations.
- **`.ar/math/`** — Modular arithmetic: `add`, `sub`, `mul_mod`, `pow_mod`, `mod_inv`, `div_mod`, `div_rem`, `sqrt_mod`, `quadratic_residue`, `extended_gcd`, `karatsuba`, and related operations.

Use these as functional references for correctness and test vectors, but rewrite from scratch following the project's architecture and performance constraints.
