Module primality 

Deterministic Miller-Rabin primality plus tabled fast paths for the power-of-two-aligned cases that dominate ruvector’s hot paths.

Designed for ADR-151 (PIAL — Prime-Indexed Acceleration Layer). Five consumers (shard router, HNSW buckets, sparsifier strides, mincut LSH, pi-brain witness chain) get one shared utility and zero new external dependencies.

Determinism

Range	Witnesses	Result
n < 2^32	{2, 7, 61} (Pomerance/Selfridge/Wagstaff)	Deterministic
n < 2^64	{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} (Sinclair, 2011)	Deterministic
n < 2^128	40 random rounds (unstable-u128 feature)	Pr[err] < 2⁻⁸⁰

Pinned-pseudoprime regressions in tests/primality_pseudoprimes.rs protect the deterministic ranges from witness-set “optimizations”.

Hot vs cold paths

Three of PIAL’s five sites request primes near fixed power-of-two sizes. Those calls hit prev_prime_below_pow2 / next_prime_above_pow2 — a single L1-cached load, ~1 ns. The two unpredictable sites (LSH universe, witness ephemeral primes) use the general MR descent at ~250 ns. Both are cold.

Crucially the table is generated at build time from this very module’s is_prime_u64, so MR remains the source of truth.

Constants

PRIMES_ABOVE_2K

Smallest prime strictly greater than 2^k for k in [8, 64], indexed by k - 8.

PRIMES_BELOW_2K

Largest prime strictly less than 2^k for k in [8, 64], indexed by k - 8.

Functions

ephemeral_prime

Derives a deterministic ephemeral prime from seed, suitable for the pi-brain witness chain (ADR-151 §4.4).

is_prime_u32

Returns true iff n is prime. Deterministic for all u32.

is_prime_u64

Returns true iff n is prime. Deterministic for all u64.

next_prime_above_pow2

Smallest prime strictly greater than 2^k, for k ∈ [8, 63].

next_prime_u64

Smallest prime strictly greater than n. Returns 0 if n is at or above the largest u64 prime (u64::MAX - 58).

prev_prime_below_pow2

Largest prime strictly less than 2^k, for k ∈ [8, 64].

prev_prime_u64

Largest prime strictly less than n. Returns 0 if no such u64 prime exists (i.e. n <= 2).