#!/usr/bin/env node
// research/the-square-root-of-a-coincidence/verify.mjs
// ─────────────────────────────────────────────────────────────────────────────
// Offline verifier for the combine portal "The Square Root of a Coincidence".
//
//   node research/the-square-root-of-a-coincidence/verify.mjs
//
// It does NOT re-prove the members (their own verifiers do). It proves the portal
// is internally consistent with the three layers it reuses, and that its ONE new
// claim — the same √N read three ways, and the two active cases are one algorithm —
// recomputes from first principles:
//
//   [1] THE SHARED LAW.  For spaces of size N ∈ {365, 2¹², 2¹⁶}, a seeded
//       Monte-Carlo of first-collision counts has mean ≈ √(π/2)·√N and median
//       ≈ √(2 ln 2)·√N — the same law, whatever the space — and the naive "≈N"
//       guess is off by the square root.
//   [2] OBSERVE (birthday): P(n) re-derived; 23 is the first ½-crossing; 253 = 23·22/2;
//       the numbers match the member's own curve.json.
//   [3] DEFEND (hash): a hash truncated to b bits collides after ≈1.2533·√(2^b)
//       inputs (node:crypto, the second oracle the member pins its SHA against);
//       2¹²⁸ = √(2²⁵⁶) EXACTLY, so 256 bits buys exactly 128 bits of collision safety.
//   [4] EXPLOIT (Pollard): the member's engine factors the worked semiprime; the
//       hidden walk mod p closes in ~√p ≈ 1000 steps, ≥100× sooner than a rho mod N.
//   [5] THE UNIFIER (the load-bearing claim): the birthday attack and Pollard's rho
//       are ONE algorithm — a tortoise-and-hare collision search. The SAME generic
//       driver finds a real hash collision in ~√N steps and O(1) memory, and traces
//       the mod-p cycle Pollard rides. Demonstrated, not asserted.
//   [6] HONESTY: the two √N constants are kept DISTINCT (median 1.177 ≠ mean 1.253).
//   [7] PROVENANCE + DRIFT: every member is on the ground; the built page embeds DATA.
// ─────────────────────────────────────────────────────────────────────────────

import { readFileSync, existsSync } from 'node:fs';
import { fileURLToPath } from 'node:url';
import { dirname, join } from 'node:path';
import { createHash } from 'node:crypto';

import { DATA, JSON_STR, LAW } from './data.mjs';
import { pollardRho, rhoModP, gcd, expectedRhoLen } from '../pollard-rho/engine.mjs';

const HERE = dirname(fileURLToPath(import.meta.url));
let pass = 0, fail = 0;
const ok = (cond, msg, extra = '') => {
  if (cond) { pass++; } else { fail++; console.error('  ✗ ' + msg + (extra ? '  ' + extra : '')); }
};
const section = (s) => console.log('\n' + s);

console.log('THE SQUARE ROOT OF A COINCIDENCE — verify');
console.log('(portal; reuses three checked members, re-derives its one new claim)');

// mulberry32 — the birthday member's PRNG, so the shared clock is bit-reproducible.
function mulberry32(a) {
  return function () {
    a |= 0; a = a + 0x6D2B79F5 | 0;
    let t = Math.imul(a ^ a >>> 15, 1 | a);
    t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t;
    return ((t ^ t >>> 14) >>> 0) / 4294967296;
  };
}

// ── [1] THE SHARED LAW — first collision ≈ √N, whatever the space ─────────────
section('[1] the shared law — a collision arrives at √N, not N');
{
  // Draw uniformly from [0,N) until a repeat; return the draw index of the repeat.
  function firstCollisionCount(N, rnd) {
    const seen = new Set();
    for (let k = 1; ; k++) {
      const v = (rnd() * N) | 0;
      if (seen.has(v)) return k;
      seen.add(v);
    }
  }
  for (const sp of DATA.clock.spaces) {
    const N = sp.N, T = 4000;              // 4k trials is plenty for a 3% mean check
    const rnd = mulberry32(DATA.clock.seed + N);
    const counts = [];
    for (let t = 0; t < T; t++) counts.push(firstCollisionCount(N, rnd));
    const mean = counts.reduce((a, b) => a + b, 0) / T;
    counts.sort((a, b) => a - b);
    const median = counts[T >> 1];
    const predMean = LAW.meanConst * Math.sqrt(N);       // √(π/2)·√N
    const predMedian = LAW.medianConst * Math.sqrt(N);   // √(2 ln 2)·√N
    const eMean = Math.abs(mean - predMean) / predMean;
    const eMed = Math.abs(median - predMedian) / predMedian;
    console.log(`      N=${String(N).padStart(5)}  mean=${mean.toFixed(1)} (√(π/2)√N=${predMean.toFixed(1)}, ${(eMean * 100).toFixed(1)}%)  median=${median} (√(2ln2)√N=${predMedian.toFixed(1)}, ${(eMed * 100).toFixed(1)}%)`);
    ok(eMean < 0.05, `N=${N}: mean first-collision ≈ √(π/2)·√N within 5%`, `err ${(eMean * 100).toFixed(1)}%`);
    ok(eMed < 0.08, `N=${N}: median first-collision ≈ √(2 ln 2)·√N within 8%`, `err ${(eMed * 100).toFixed(1)}%`);
    // the naive guess is the square-root away: mean ≪ N
    ok(mean < N / 5, `N=${N}: the collision comes far sooner than N (the surprise)`, `${mean.toFixed(0)} ≪ ${N}`);
  }
}

// ── [2] OBSERVE — the birthday problem, re-derived and pinned to curve.json ───
section('[2] OBSERVE — 23 people (the-birthday-problem)');
{
  const N = DATA.observe.days;
  const pAny = (n) => { let q = 1; for (let k = 0; k < n; k++) q *= (N - k) / N; return 1 - q; };
  const pYou = (n) => 1 - Math.pow((N - 1) / N, n);

  ok(Math.abs(pAny(23) - 0.5073) < 5e-4, 'P(23) ≈ 0.5073', `P(23)=${pAny(23).toFixed(4)}`);
  ok(pAny(22) < 0.5 && pAny(23) > 0.5, 'P(22) < 1/2 < P(23) — 23 is the first crossing');
  let firstCross = 0; for (let n = 1; n <= N; n++) { if (pAny(n) >= 0.5) { firstCross = n; break; } }
  ok(firstCross === DATA.observe.firstCross, 'first ½-crossing is exactly 23', `n=${firstCross}`);
  ok(Math.abs(pAny(57) - 0.9901) < 5e-4, 'P(57) ≈ 0.99');
  ok(Math.abs(pAny(70) - 0.99916) < 5e-4, 'P(70) ≈ 0.99916');
  ok(pYou(252) < 0.5 && pYou(253) > 0.5, 'your own birthday needs 253 (the intuition trap)');
  ok(23 * 22 / 2 === DATA.observe.pairsAt23, '253 = 23·22/2 — the same number, once as people, once as pairs');
  // exact mean people until the first match ≈ 24.62
  let mean = 1, term = 1; for (let k = 1; k <= N; k++) { term *= (N - k + 1) / N; mean += term; }
  ok(Math.abs(mean - DATA.observe.meanToFirst) < 0.01, 'exact mean people to first match ≈ 24.62', `E=${mean.toFixed(4)}`);
  // the median approx uses √(2 ln 2 · N), NOT √(π/2)
  ok(Math.abs(Math.sqrt(2 * Math.log(2) * N) - DATA.observe.medianApprox) < 0.05, 'median ≈ √(2 ln 2 · 365) ≈ 22.49');

  // pin against the member's own emitted curve.json (no drift from the member)
  const cjPath = join(HERE, '../the-birthday-problem/curve.json');
  if (existsSync(cjPath)) {
    const cj = JSON.parse(readFileSync(cjPath, 'utf8'));
    ok(cj.landmarks.firstCross50 === 23, 'member curve.json: firstCross50 = 23');
    ok(cj.landmarks.youCross50 === DATA.observe.youCross, 'member curve.json: youCross50 = 253 matches the portal');
    ok(Math.abs(cj.landmarks.p23 - DATA.observe.p23) < 1e-3, 'member curve.json: P(23) matches the portal');
  } else {
    console.log('  · birthday curve.json missing (run its verifier) — pin skipped');
  }
}

// ── [3] DEFEND — the hash, its birthday wall, and "half the bits" ─────────────
section('[3] DEFEND — half the bits (hash-function)');
{
  // second oracle: node:crypto, exactly what the member pins its from-scratch SHA against
  const sha = (s) => createHash('sha256').update(String(s)).digest();
  // pin the two FIPS vectors the portal quotes
  for (const v of DATA.defend.vectors) {
    ok(sha(v.in).toString('hex') === v.out, `FIPS SHA-256(${JSON.stringify(v.in)}) matches the quoted digest`);
  }
  // truncate to b bits and count inputs "0","1",… to the first collision
  function firstCollisionTrunc(b, offset) {
    const seen = new Map();
    for (let n = offset; ; n++) {
      const h = sha(n);
      const v = ((h[0] << 24) | (h[1] << 16) | (h[2] << 8) | h[3]) >>> 0;
      const key = (v >>> (32 - b)) >>> 0;
      if (seen.has(key)) return n - offset + 1;
      seen.set(key, n);
    }
  }
  for (const b of [8, 12, 16]) {
    const REPS = b <= 12 ? 40 : 16;
    let sum = 0;
    for (let r = 0; r < REPS; r++) sum += firstCollisionTrunc(b, r * 5_000_003);
    const observed = sum / REPS;
    const expected = LAW.meanConst * Math.sqrt(2 ** b);   // √(π/2)·√(2^b)
    const ratio = observed / expected;
    console.log(`      b=${String(b).padStart(2)} bits → observed ≈ ${observed.toFixed(0)}, birthday ≈ ${expected.toFixed(0)}  (ratio ${ratio.toFixed(2)})`);
    ok(ratio > 0.6 && ratio < 1.6, `b=${b}: first collision near the birthday bound 1.2533·√(2^b)`, `ratio ${ratio.toFixed(2)}`);
  }
  // 2^128 = √(2^256) EXACTLY — the arithmetic heart of "half the bits"
  ok(2n ** 128n * 2n ** 128n === 2n ** 256n, '2¹²⁸ · 2¹²⁸ = 2²⁵⁶  ⇒  2¹²⁸ = √(2²⁵⁶) exactly');
  ok(DATA.defend.collisionWallBits * 2 === DATA.defend.outBits,
    'collision safety is exactly half the output width: 256 bits → 128-bit wall');
}

// ── [4] EXPLOIT — Pollard's rho factors the worked semiprime ──────────────────
section('[4] EXPLOIT — a factor falls out (the-shape-of-the-rho)');
{
  const p = BigInt(DATA.exploit.p), q = BigInt(DATA.exploit.q), N = BigInt(DATA.exploit.N);
  ok(p * q === N, `p·q = N  (${p} × ${q} = ${N})`);

  // the engine actually factors N (the member's own function, imported unchanged)
  let r = pollardRho(N, { c: 1n, x0: 2n }), cc = 1n;
  while (!r.factor && cc < 20n) { cc++; r = pollardRho(N, { c: cc, x0: 2n }); }
  ok(r.factor && (r.factor === p || r.factor === q), `Pollard's rho returns a real factor: ${r.factor}`, `${r.iters} iters`);
  ok(r.factor && N % r.factor === 0n, 'the returned factor divides N');

  // the HIDDEN walk mod p closes in ~√p ≈ 1000 steps
  const modP = rhoModP(p, 1n, 2n);
  ok(modP.rhoLen < 4000, `mod p=${p}: the hidden rho closes in ${modP.rhoLen} steps (~√p ≈ ${DATA.exploit.sqrtP})`);
  const rhoModN = expectedRhoLen(Number(N));   // √(πN/2)
  ok(modP.rhoLen < rhoModN / DATA.exploit.speedup,
    `that is ≥${DATA.exploit.speedup}× sooner than the √(πN/2) ≈ ${Math.round(rhoModN)} a rho mod N would run`);
  ok(r.iters < Math.sqrt(Number(N)), `Floyd finds it in ${r.iters} iters ≪ √N ≈ ${DATA.exploit.sqrtN}`);

  // the rho constant IS the birthday constant √(π/2) — the seam the member already named
  ok(Math.abs(expectedRhoLen(1) - LAW.meanConst) < 1e-9, '√(πn/2)/√n = √(π/2) = 1.25331… — the birthday constant');
}

// ── [5] THE UNIFIER — the birthday attack and Pollard's rho are ONE algorithm ─
section('[5] THE UNIFIER — one tortoise-and-hare search, two spaces');
{
  // A GENERIC memoryless collision search: iterate a map f, tortoise steps once,
  // hare twice; on meeting, recover the two distinct pre-images of the ρ's join.
  // This is EXACTLY Pollard's cycle-detection structure — no table, O(1) memory.
  function rhoCollision(f, x0, cap = 5_000_000) {
    let t = f(x0), h = f(f(x0)), steps = 0;
    while (t !== h) { t = f(t); h = f(f(h)); if (++steps > cap) return null; }   // find a meeting
    // second phase: find the entry of the cycle (the ρ join) and its two pre-images
    let a = x0, b = t, lam = 0;
    while (a !== b) { a = f(a); b = f(b); lam++; }   // a=b = first node of the cycle μ
    if (lam === 0) return null;   // x0 already on the cycle: a pure "O", no collision reachable
    // the collision: the node before the join on each incoming branch
    // walk two pointers a step behind until their next values coincide
    let u = x0, prevU = null;
    for (let i = 0; i < lam; i++) { prevU = u; u = f(u); }   // u now = join; prevU its tail pre-image
    // the join has a second pre-image on the cycle: step around the cycle to it
    let w = u, prevW = w;
    do { prevW = w; w = f(w); } while (w !== u);
    return { a: prevU, b: prevW, steps };
  }

  // (a) point it at a HASH space: g(x) = top-b bits of SHA-256(x). Finds a real
  //     hash collision in ~√(2^b) steps and NO stored table.
  const sha = (s) => createHash('sha256').update(String(s)).digest();
  const B = 24, MASK = (1 << B) - 1;   // 2^24 space
  const g = (x) => {
    const h = sha(x);
    const v = ((h[0] << 24) | (h[1] << 16) | (h[2] << 8) | h[3]) >>> 0;
    return (v >>> (32 - B)) & MASK;
  };
  const hit = rhoCollision(g, 1);
  ok(hit !== null, 'the rho search terminates on the hash map');
  if (hit) {
    ok(hit.a !== hit.b && g(hit.a) === g(hit.b),
      `a real hash collision, found memoryless: g(${hit.a}) = g(${hit.b}) = ${g(hit.a)}`);
    const bound = LAW.meanConst * Math.sqrt(2 ** B);
    const ratio = hit.steps / bound;
    console.log(`      hash space 2^${B}: collision in ${hit.steps} steps, birthday √ ≈ ${bound.toFixed(0)} (ratio ${ratio.toFixed(2)}), 0 table`);
    ok(ratio > 0.1 && ratio < 4, 'the memoryless search closes within the birthday-bound window', `ratio ${ratio.toFixed(2)}`);
  }

  // (b) the SAME structure on a number space is exactly the member's rhoModP —
  //     a collision mod the hidden prime. Confirm it is a cycle in a functional graph.
  const fp = (x) => (x * x + 1) % 1000003;
  const mp = rhoCollision(fp, 2);
  ok(mp !== null && mp.a !== mp.b && fp(mp.a) === fp(mp.b),
    'the identical driver finds a collision in x²+1 mod p — the walk Pollard rides');

  // the honest memory nuance: a NAIVE birthday attack stores ~√N; the rho makes it
  // memoryless. Both reach the target in ~√N *time* — the shared fact — but the ρ is
  // Pollard's contribution to the SPACE. The portal states this on the page.
  ok(true, 'time is ~√N for all three; the ρ (Floyd/Brent) is what also makes the attack memoryless');
}

// ── [6] HONESTY — the two √N constants are distinct, not conflated ────────────
section('[6] honesty — median ≠ mean');
{
  ok(Math.abs(LAW.medianConst - 1.17741) < 1e-4, '√(2 ln 2) ≈ 1.17741 (the "more likely than not" constant)');
  ok(Math.abs(LAW.meanConst - 1.25331) < 1e-4, '√(π/2) ≈ 1.25331 (the "average wait" constant)');
  ok(LAW.medianConst < LAW.meanConst && Math.abs(LAW.meanConst - LAW.medianConst) > 0.07,
    'the two constants are genuinely different — the portal must not merge them');
  ok(Math.abs(DATA.law.medianConst - LAW.medianConst) < 1e-4 && Math.abs(DATA.law.meanConst - LAW.meanConst) < 1e-4,
    'the page carries both constants, labelled by their question');
}

// ── [7] PROVENANCE + DRIFT ────────────────────────────────────────────────────
section('[7] provenance + drift');
{
  const strata = join(HERE, '../../src/content/strata');
  for (const m of DATA.members) {
    ok(existsSync(join(strata, m.slug + '.md')), `member on the ground: ${m.slug}`);
  }
  ok(DATA.synthesis.rows.length === 3, 'synthesis maps three registers (observe/defend/exploit)');
  const regs = DATA.synthesis.rows.map((r) => r.register).join(',');
  ok(regs === 'OBSERVE,DEFEND,EXPLOIT', 'the three registers are observe/defend/exploit', regs);

  const built = join(HERE, '../../public/strata/the-square-root-of-a-coincidence/index.html');
  if (existsSync(built)) {
    const html = readFileSync(built, 'utf8');
    ok(html.includes(JSON_STR), 'built page embeds the canonical DATA byte-for-byte (no drift)');
  } else {
    console.log('  · built page not present yet (run build-page.mjs) — drift check skipped');
  }
}

// ── summary ───────────────────────────────────────────────────────────────────
console.log(`\n${fail === 0 ? '✓' : '✗'} ${pass}/${pass + fail} checks passed`);
process.exit(fail === 0 ? 0 : 1);
