Elamur Groupants⌕
☰

algorithm-miller-rabin-tests

The groupant beside algorithms/src/miller_rabin/tests.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

Facts

Implementation material. A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

Components

componentlabelwhere
approximantpartialForward
astpartialsyntax.json
costconditionalCost
descriptantpresentdescriptant
invariantpartialInvariant
testsbounded executedevidence

Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

idtypelabelwhere
behavior_complementbehavior_complementpartial relational specificationbehavior_complement
reverse_reconstructionreverse_reconstructionpartial relational specificationreverse_reconstruction
divisor_oracledivisor_oraclepartial relational specificationdivisor_oracle
pseudoprime_strengthpseudoprime_strengthpartial relational specificationpseudoprime_strength
prime_fiberprime_fiberpartial relational specificationprime_fiber
oracle_controloracle_controlpartial relational specificationoracle_control

Model text

descriptant

algorithm-miller-rabin-tests

Epoch 2026-10-30: original exact implementation and independent fixtures.

Run independent trial division on n=0..99999; compare the Boolean classifier. Check literal pseudoprime and product composites, large prime fixtures, and literal prime fiber below50. Test assertions report exact disagreement input.

Prospective model: O(N sqrt N) upper bound for trial enumeration with N=100000; constant-size boundary arrays and O(50) fiber vector. This is bounded test work, not an exhaustive-u64 proof. No optimization or speed claim is made. The small-prime enumeration and full-width boundary fixtures are complementary: the former is independent but finite, the latter stresses arithmetic without exhausting the domain. Primality depends on the cited deterministic witness-set result. Root search has a finite but potentially large worst-case bound; no randomized efficiency inference is made.

Partial syntax is source-bound and generated twice identically. Macro bodies are opaque, semantic AST and general mathematical proof remain absent. No executable approximate surrogate is introduced because these exact scalar APIs require exact outputs.

model

algorithm-miller-rabin-tests

Forward

Run independent trial division on n=0..99999; compare the Boolean classifier. Check literal pseudoprime and product composites, large prime fixtures, and literal prime fiber below50. Test assertions report exact disagreement input.

Invariant

Trial oracle divides integers directly; d<=n/d avoids squared-divisor overflow. Product fixtures are selected to fit u64. Expectations do not reuse modular exponentiation.

Cost

O(N sqrt N) upper bound for trial enumeration with N=100000; constant-size boundary arrays and O(50) fiber vector. This is bounded test work, not an exhaustive-u64 proof.

behavior_complement

For each enumerated n, acceptance of an is_prime(n) value opposite to the trial-divisor truth is forbidden. Literal fiber checks also forbid omitting a prime or inserting a composite below50. Failure does not by itself localize implementation versus fixture defects.

reverse_reconstruction

A passing test summary is compatible with any implementation agreeing on all exercised inputs, including implementations wrong on an unexercised u64. Thus success cannot recover source or establish universal correctness; failing n narrows the compatible disagreement location.

divisor_oracle

For n>=2 trial returns false iff an integer d in [2,floor(sqrt n)] divides n. This elementary characterization is independent of strong probable-prime witnesses.

pseudoprime_strength

Boundary fixtures include 2047,1373653,3215031751,341550071728321 and3825123056546413051: composite values that expose insufficient fixed-witness testing. The array is finite and not a complete pseudoprime catalog.

prime_fiber

The explicit below50 prime list is a second observation of the Boolean output fiber. All other integers below50 map false; no inverse identification of a unique prime follows.

oracle_control

Replacing the trial oracle initial n<2 branch with n<3 yields the concrete disagreement at2. This compiled test-only control must fail exhaustive_trial_division while restored bytes pass.

evidence

Evidence

Source SHA-256: 2d8f0f017ba230eb9ac41a7020598a4c711cddbfc0d3b169857f99f8a09ae1c8.

Eight named tests total: four per algorithm. Each focused set passes twice in debug and twice in release with equal normalized named outcomes. Primality checks100000 consecutive integers by independent trial division plus finite pseudoprime and full-width fixtures. Roots exhaust every a<3p and root candidate for every prime p<200, plus large-field square identities.

Compiled production controls: odd-prime acceptance changed to false in Miller-Rabin; canonical min changed to max in Tonelli-Shanks. Named assertions reject both. Test-only false trial/root oracles also fail their named exhaustive assertions. Exact source bytes are restored before positive rechecks. Raw logs and normalized receipts remain in the external wave14 numeric run bundle.

Strict all-target algorithm Clippy and narrow rustfmt checks executed. Finite evidence does not establish all-u64 correctness, worst-case practical runtime, or full-system behavior.

Evidence bindings

12681 exhaustive root cases across46 primes below200;100000 independent trial-division cases. Production control witnesses: n=3 and (a=1,p=3). All four restored sources passed the repeated profiles.

This page in Markdown → https://md.groupants.elamur.ai/free/en/mova/algorithms/src/miller_rabin/tests.rs.groupant/