Verification & Certificates

darkreach uses a 3-tier verification pipeline to classify every prime candidate. Results are either proven deterministic (mathematical certainty) or labeled as probable primes (PRP) with explicit confidence bounds.

3-Tier Pipeline

Candidate
    │
    ▼
┌──────────────────────────────┐
│  Tier 1: Deterministic Proof │  Pocklington, Morrison, BLS,
│  (N-1 / N+1 factorization)  │  Proth, LLR, Pepin
│  Result: PROVEN PRIME        │
└──────────┬───────────────────┘
           │ if proof not possible
           ▼
┌──────────────────────────────┐
│  Tier 2: Strong PRP Tests    │  BPSW + 25-round Miller-Rabin
│  + Frobenius (>10K bits)     │  + Grantham RQFT
│  Result: PROBABLE PRIME      │
└──────────┬───────────────────┘
           │ for large candidates
           ▼
┌──────────────────────────────┐
│  Tier 3: External Tools      │  PFGW (50-100x faster)
│  PFGW / GWNUM / PRST         │  GWNUM FFI, PRST subprocess
│  Result: PRP or PROVEN       │
└──────────────────────────────┘

Proof Types

Different prime forms admit different proof strategies, depending on whether the factorization of N-1 or N+1 is sufficiently known:

Proof	Basis	Forms
Proth	N-1 test: if `a^((N-1)/2) = -1 mod N` for some `a`, then N is prime (when `k < 2^n`)	k*b^n+1, Cullen, Gen Fermat
LLR	Lucas-Lehmer-Riesel N+1 test using Lucas sequences	k*b^n-1, Woodall, Carol/Kynea
Pocklington	N-1 partial factorization: if factored portion F > sqrt(N), then N is prime	Factorial (n!+1), Primorial (p#+1)
Morrison	N+1 partial factorization using Lucas sequences	Factorial (n!-1), Primorial (p#-1)
BLS	Brillhart-Lehmer-Selfridge combined N-1/N+1 theorem	Near-repdigit
Pepin	Specialization of Proth for Fermat numbers: `3^((F_n-1)/2) = -1 mod F_n`	Generalized Fermat (base 2)
PRP	No deterministic proof available — 25-round Miller-Rabin + BPSW	Wagstaff, Repunit, Palindromic

Primality Certificates

When a deterministic proof succeeds, darkreach generates a PrimalityCertificate — a machine-verifiable witness that anyone can check independently:

json

{
  "type": "Pocklington",
  "n": "147855! + 1",
  "factors_of_n_minus_1": [
    [2, 147855],
    [3, 71420],
    ...
  ],
  "witness_a": 5,
  "verified": true
}

Certificates are stored in the database alongside the prime record and can be exported for submission to prime databases like The Prime Pages (t5k.org).

Certificate variants

rust

enum PrimalityCertificate {
    Pocklington { a: u64, factors: Vec<(u64, u32)> },
    Morrison    { lucas_v: Integer, factors: Vec<(u64, u32)> },
    BLS         { a: u64, n_minus_factors: ..., n_plus_factors: ... },
    Proth       { a: u64 },
    LLR         { u0: Integer },
    Pepin       { base: u64 },
    PRP         { bases: Vec<u64>, rounds: u32 },
}

Frobenius Test

For candidates exceeding 10,000 bits, the engine adds a Grantham RQFT (Restricted Quadratic Frobenius Test) on top of Miller-Rabin. This test operates over a quadratic extension field and checks both:

Euler criterion — Jacobi symbol consistency
Frobenius automorphism — Conjugation check in Z[x]/(x^2-bx-c)

Combined with BPSW and Miller-Rabin, this provides extremely strong composite detection with no known counterexamples.

Deep Composite Elimination

Before primality testing, candidates pass through a Pollard P-1 filter that catches composites with smooth factors:

Stage 1 — GCD after powering through primes up to B1
Stage 2 — Extended check for one large prime factor up to B2
Adaptive tuning — B1/B2 bounds auto-scale based on candidate size

The P-1 filter runs on all 12 search forms and typically eliminates 10-30% of candidates that would otherwise require expensive primality tests.

External Tool Acceleration

Tool	Speedup	Forms
PFGW	50-100x	All forms (PRP testing for large candidates)
GWNUM	10-50x	k*b^n forms (FFI, feature-gated)
PRST	5-20x	k*b^n forms (subprocess)

External tools are auto-detected at startup. If available, candidates above a size threshold are routed to the external tool instead of GMP-based testing.

Re-verification API

Any prime in the database can be re-verified via the REST API:

bash

# Re-verify a specific prime
curl -X POST https://api.darkreach.ai/api/verify \
  -H "Content-Type: application/json" \
  -d '{"prime_id": 42}'

This re-runs the full verification pipeline and updates the proof status. Useful for auditing results or upgrading PRP results when new proof methods become available.