#!/usr/bin/env python3
"""Independently verify a Voopa Goldbach Lab prime-pair record.

This verifier is intentionally separate from the browser's JavaScript code.
It uses Python's arbitrary-precision integers, built-in modular exponentiation,
and gcd; it does not trust the sieve or certificate generator.
"""

from __future__ import annotations

import json
import math
import sys
import base64
import binascii
import shutil
import subprocess
from pathlib import Path
from typing import Any

MAX_FILE_BYTES = 16 * 1024 * 1024
MAX_CERTIFICATE_NODES = 100_000
MAX_CERTIFICATE_DEPTH = 512
EMBEDDED_DOCUMENT_MARKER = "# VOOPA_GOLDBACH_CERTIFICATE_BASE64:"
MR64_FORMAT = "Voopa Goldbach Lab deterministic 64-bit check v1"
MR64_METHOD = "Deterministic Miller-Rabin, seven fixed bases for n < 2^64"
MR64_BASES = (2, 325, 9375, 28178, 450775, 9780504, 1795265022)
MR64_BOUND = 1 << 64
MR_PROBABLE_FORMAT = "Voopa Goldbach Lab probable-prime screening record v1"
MR_PROBABLE_METHOD = "Strong Miller-Rabin probable-prime screening with independently sampled random bases"
MAX_DECIMAL_DIGITS = 30_000

if hasattr(sys, "set_int_max_str_digits"):
    sys.set_int_max_str_digits(MAX_DECIMAL_DIGITS)


class CertificateError(ValueError):
    """Raised when certificate data is malformed or fails a proof check."""


def _no_duplicate_keys(pairs: list[tuple[str, Any]]) -> dict[str, Any]:
    result: dict[str, Any] = {}
    for key, value in pairs:
        if key in result:
            raise CertificateError(f"duplicate JSON field: {key}")
        result[key] = value
    return result


def _reject_nonstandard_constant(value: str) -> None:
    raise CertificateError(f"non-standard JSON constant is not allowed: {value}")


def _decimal(value: Any, field: str, *, minimum: int = 0) -> int:
    if not isinstance(value, str) or not value or not value.isascii() or not value.isdecimal():
        raise CertificateError(f"{field} must be a decimal string")
    if len(value) > MAX_DECIMAL_DIGITS:
        raise CertificateError(f"{field} exceeds the {MAX_DECIMAL_DIGITS}-digit verifier limit")
    number = int(value)
    if number < minimum:
        raise CertificateError(f"{field} must be at least {minimum}")
    if str(number) != value:
        raise CertificateError(f"{field} must not contain leading zeroes")
    return number


def _verify_pratt(node: Any, *, depth: int, budget: list[int]) -> int:
    if depth > MAX_CERTIFICATE_DEPTH:
        raise CertificateError("certificate recursion is too deep")
    budget[0] += 1
    if budget[0] > MAX_CERTIFICATE_NODES:
        raise CertificateError("certificate contains too many proof nodes")
    if not isinstance(node, dict):
        raise CertificateError("each prime certificate must be a JSON object")
    if set(node) != {"kind", "n", "witness", "factors"}:
        raise CertificateError("prime certificate has missing or unexpected fields")
    if node["kind"] != "PrattPrimeCertificate":
        raise CertificateError("unsupported prime certificate kind")

    n = _decimal(node["n"], "certificate n", minimum=2)
    factors = node["factors"]
    if not isinstance(factors, list):
        raise CertificateError(f"factor list for {n} must be an array")

    if n == 2:
        if node["witness"] is not None or factors:
            raise CertificateError("the base certificate for 2 must have no witness or factors")
        return n

    if not factors:
        raise CertificateError(f"certificate for {n} has no factors for n − 1")

    product = 1
    previous_q = 1
    prime_factors: list[int] = []
    for factor in factors:
        if not isinstance(factor, dict) or set(factor) != {"prime", "exponent", "certificate"}:
            raise CertificateError(f"malformed factor record for {n}")
        q = _decimal(factor["prime"], "factor prime", minimum=2)
        exponent = factor["exponent"]
        if type(exponent) is not int or exponent < 1:
            raise CertificateError(f"factor exponent for {q} must be a positive integer")
        if q <= previous_q:
            raise CertificateError(f"prime factors for {n} must be unique and in increasing order")
        previous_q = q
        child_n = _verify_pratt(factor["certificate"], depth=depth + 1, budget=budget)
        if child_n != q:
            raise CertificateError(f"nested certificate proves {child_n}, not factor {q}")
        product *= q**exponent
        prime_factors.append(q)

    if product != n - 1:
        raise CertificateError(f"listed prime powers do not multiply to {n} − 1")

    witness = _decimal(node["witness"], "Pratt witness", minimum=2)
    if witness >= n:
        raise CertificateError(f"Pratt witness for {n} must be smaller than n")
    if pow(witness, n - 1, n) != 1:
        raise CertificateError(f"Fermat congruence failed for {n}")
    for q in prime_factors:
        residue = pow(witness, (n - 1) // q, n)
        if math.gcd(residue - 1, n) != 1:
            raise CertificateError(f"gcd condition failed for {n} at prime factor {q}")

    # Pratt's criterion: with all prime factors of n−1 themselves proved,
    # these modular conditions force the multiplicative order to be n−1,
    # which is possible only when n is prime.
    return n


def _is_prime_u64(n: int) -> bool:
    """Deterministic Miller–Rabin for n < 2^64 using the fixed proven base set."""
    if n < 2 or n >= MR64_BOUND:
        return False
    for small in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n == small:
            return True
        if n % small == 0:
            return False
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for base in MR64_BASES:
        a = base % n
        if a == 0:
            continue
        x = pow(a, d, n)
        if x in (1, n - 1):
            continue
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                break
        else:
            return False
    return True


def _verify_mr64_document(document: dict[str, Any]) -> tuple[int, int, int]:
    required = {"format", "sum", "pair", "method", "bases", "upper_bound_exclusive"}
    if set(document) != required:
        raise CertificateError("deterministic-check record has missing or unexpected fields")
    if document["method"] != MR64_METHOD:
        raise CertificateError("unexpected deterministic primality method")
    if document["upper_bound_exclusive"] != str(MR64_BOUND):
        raise CertificateError("record does not state the supported n < 2^64 bound")
    if document["bases"] != [str(base) for base in MR64_BASES]:
        raise CertificateError("record has an unexpected Miller–Rabin base set")
    total = _decimal(document["sum"], "sum", minimum=4)
    pair = document["pair"]
    if not isinstance(pair, list) or len(pair) != 2:
        raise CertificateError("pair must contain exactly two prime values")
    p = _decimal(pair[0], "first pair value", minimum=2)
    q = _decimal(pair[1], "second pair value", minimum=2)
    if p > q:
        raise CertificateError("pair values must be ordered smallest first")
    if p + q != total or total % 2:
        raise CertificateError("pair does not sum to the stated even input")
    if not _is_prime_u64(p):
        raise CertificateError(f"first pair value {p} failed the deterministic 64-bit primality check")
    if not _is_prime_u64(q):
        raise CertificateError(f"second pair value {q} failed the deterministic 64-bit primality check")
    return total, p, q


def _passes_miller_rabin_bases(n: int, bases: list[int]) -> bool:
    if n < 2:
        return False
    small_primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)
    for prime in small_primes:
        if n == prime:
            return True
        if n % prime == 0:
            return False
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for base in bases:
        a = base % n
        x = pow(a, d, n)
        if x in (1, n - 1):
            continue
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                break
        else:
            return False
    return True


def _verify_probable_document(document: dict[str, Any]) -> tuple[int, int, int]:
    required = {
        "format", "sum", "pair", "method", "q_bases", "rounds", "candidate_count", "prime_candidates_scanned",
        "candidate_prime_limit", "randomness_source", "false_acceptance_bound",
    }
    if set(document) != required:
        raise CertificateError("probable-prime record has missing or unexpected fields")
    if document["method"] != MR_PROBABLE_METHOD:
        raise CertificateError("unexpected probable-prime screening method")
    if document["randomness_source"] != "Web Crypto crypto.getRandomValues":
        raise CertificateError("record does not identify the browser random-base source")
    rounds = document["rounds"]
    if type(rounds) is not int or rounds != 32:
        raise CertificateError("probable-prime record must contain exactly 32 Miller–Rabin rounds")
    candidate_count = _decimal(document["candidate_count"], "candidate count", minimum=1)
    prime_candidates_scanned = _decimal(document["prime_candidates_scanned"], "prime candidates scanned", minimum=1)
    if candidate_count > prime_candidates_scanned:
        raise CertificateError("randomized-test count exceeds the number of scanned prime candidates")
    candidate_limit = _decimal(document["candidate_prime_limit"], "candidate prime limit", minimum=3)
    if candidate_limit > 1_000_000_000_000:
        raise CertificateError("candidate prime limit exceeds the documented search bound")
    expected_bound = f"At most {candidate_count}/4^{rounds} across the search, assuming independent uniform bases; probabilistic only"
    if document["false_acceptance_bound"] != expected_bound:
        raise CertificateError("probabilistic error-bound description does not match the record")

    total = _decimal(document["sum"], "sum", minimum=4)
    pair = document["pair"]
    if not isinstance(pair, list) or len(pair) != 2:
        raise CertificateError("pair must contain exactly two prime values")
    p = _decimal(pair[0], "first pair value", minimum=2)
    q = _decimal(pair[1], "second pair value", minimum=2)
    if p > q or p + q != total or total % 2:
        raise CertificateError("pair does not sum to the stated even input in increasing order")
    if p > candidate_limit or not _is_prime_trial(p):
        raise CertificateError("first pair value is not a prime within the documented candidate sieve range")

    raw_bases = document["q_bases"]
    if not isinstance(raw_bases, list) or len(raw_bases) != rounds:
        raise CertificateError("large-value record must include all 32 Miller–Rabin bases")
    bases = [_decimal(base, "Miller–Rabin base", minimum=2) for base in raw_bases]
    if any(base >= q - 1 for base in bases):
        raise CertificateError("Miller–Rabin base must be smaller than q − 1")
    if not _passes_miller_rabin_bases(q, bases):
        raise CertificateError("large pair value failed one of the recorded Miller–Rabin rounds")
    return total, p, q


def _is_prime_trial(n: int) -> bool:
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    divisor = 3
    while divisor * divisor <= n:
        if n % divisor == 0:
            return False
        divisor += 2
    return True


def verify_document(document: Any) -> tuple[int, int, int]:
    if not isinstance(document, dict):
        raise CertificateError("top-level certificate must be a JSON object")
    if document.get("format") == MR64_FORMAT:
        return _verify_mr64_document(document)
    if document.get("format") == MR_PROBABLE_FORMAT:
        return _verify_probable_document(document)
    required = {"format", "sum", "pair", "method", "certificates"}
    if set(document) != required:
        raise CertificateError("top-level document has missing or unexpected fields")
    if document["format"] != "Voopa Goldbach Lab Pratt certificate v1":
        raise CertificateError("unsupported certificate document format")
    if document["method"] != "Pratt primality certificates with complete factorization of n − 1":
        raise CertificateError("unexpected certificate method description")

    total = _decimal(document["sum"], "sum", minimum=4)
    pair = document["pair"]
    if not isinstance(pair, list) or len(pair) != 2:
        raise CertificateError("pair must contain exactly two prime values")
    p = _decimal(pair[0], "first pair value", minimum=2)
    q = _decimal(pair[1], "second pair value", minimum=2)
    if p > q:
        raise CertificateError("pair values must be ordered smallest first")
    if p + q != total:
        raise CertificateError("the two pair values do not add to the stated even number")
    if total % 2:
        raise CertificateError("the stated Goldbach input must be even")

    certificates = document["certificates"]
    if not isinstance(certificates, list) or len(certificates) != 2:
        raise CertificateError("exactly two prime certificates are required")
    budget = [0]
    proved_p = _verify_pratt(certificates[0], depth=0, budget=budget)
    proved_q = _verify_pratt(certificates[1], depth=0, budget=budget)
    if (proved_p, proved_q) != (p, q):
        raise CertificateError("prime certificates do not match the stated Goldbach pair")
    return total, p, q


def load_document(path: Path) -> Any:
    if path.stat().st_size > MAX_FILE_BYTES:
        raise CertificateError(f"file exceeds the {MAX_FILE_BYTES}-byte safety limit")
    with path.open("r", encoding="utf-8") as handle:
        return json.load(
            handle,
            object_pairs_hook=_no_duplicate_keys,
            parse_constant=_reject_nonstandard_constant,
        )


def load_embedded_document(path: Path) -> Any | None:
    """Read a certificate embedded in a downloaded one-file verifier bundle."""
    if path.stat().st_size > MAX_FILE_BYTES * 2:
        raise CertificateError("verifier bundle exceeds the safety limit")
    for line in reversed(path.read_text(encoding="utf-8").splitlines()):
        if line.startswith(EMBEDDED_DOCUMENT_MARKER):
            encoded = line[len(EMBEDDED_DOCUMENT_MARKER):].strip()
            try:
                payload = base64.b64decode(encoded, validate=True).decode("utf-8")
            except (binascii.Error, ValueError, UnicodeError) as exc:
                raise CertificateError("embedded certificate data is not valid base64 UTF-8") from exc
            return json.loads(
                payload,
                object_pairs_hook=_no_duplicate_keys,
                parse_constant=_reject_nonstandard_constant,
            )
    return None


def verify_with_pari(primes: tuple[int, int], output_path: Path) -> None:
    """Generate ECPP certificates, then replay them in a fresh PARI/GP process."""
    gp = shutil.which("gp")
    if not gp:
        raise CertificateError("PARI/GP was not found. Install it and make the `gp` command available on PATH.")

    commands: list[str] = []
    for index, prime in enumerate(primes):
        commands.extend(
            [
                f"n{index} = {prime};",
                f"c{index} = primecert(n{index});",
                f"if (c{index} == 0, error(\"PARI found a composite input\"));",
                f"print(\"VOOPA_ECPP_BEGIN_{index}\");",
                f"print(c{index});",
                f"print(\"VOOPA_ECPP_END_{index}\");",
                f"print(\"VOOPA_PRIMO_BEGIN_{index}\");",
                f"print(primecertexport(c{index}, 1));",
                f"print(\"VOOPA_PRIMO_END_{index}\");",
                f"print(\"VOOPA_MAGMA_BEGIN_{index}\");",
                f"print(primecertexport(c{index}, 2));",
                f"print(\"VOOPA_MAGMA_END_{index}\");",
            ]
        )
    commands.append("quit")
    result = subprocess.run(
        [gp, "-q"],
        input="\n".join(commands) + "\n",
        text=True,
        capture_output=True,
        timeout=None,
        check=False,
    )
    if result.returncode != 0:
        detail = result.stderr.strip() or result.stdout.strip() or f"exit status {result.returncode}"
        raise CertificateError(f"PARI/GP failed: {detail}")

    certificates: list[str] = []
    primo_exports: list[str] = []
    magma_exports: list[str] = []
    for index in range(2):
        try:
            cert = result.stdout.split(f"VOOPA_ECPP_BEGIN_{index}", 1)[1].split(f"VOOPA_ECPP_END_{index}", 1)[0].strip()
            primo = result.stdout.split(f"VOOPA_PRIMO_BEGIN_{index}", 1)[1].split(f"VOOPA_PRIMO_END_{index}", 1)[0].strip()
            magma = result.stdout.split(f"VOOPA_MAGMA_BEGIN_{index}", 1)[1].split(f"VOOPA_MAGMA_END_{index}", 1)[0].strip()
        except IndexError as exc:
            raise CertificateError(f"PARI/GP did not return certificate data for prime {index + 1}") from exc
        if not cert or not primo or not magma:
            raise CertificateError(f"PARI/GP returned empty certificate data for prime {index + 1}")
        certificates.append(cert)
        primo_exports.append(primo)
        magma_exports.append(magma)

    # Persist a replayable checker script so a reviewer can validate the exact
    # certificate data later, independently of this generation run.
    replay_path = output_path.with_suffix(".pari-ecpp.gp")
    replay_commands: list[str] = []
    for index, cert in enumerate(certificates):
        replay_commands.extend([
            f"c{index} = {cert};",
            f"if (!primecertisvalid(c{index}), error(\"invalid ECPP certificate {index + 1}\"));",
            f"print(\"PASS: ECPP certificate {index + 1}\");",
        ])
    replay_commands.append("quit")
    replay_path.write_text("\n".join(replay_commands) + "\n", encoding="utf-8")
    replay = subprocess.run(
        [gp, "-q"], input="\n".join(replay_commands) + "\n", text=True,
        capture_output=True, timeout=None, check=False,
    )
    if replay.returncode != 0 or any(f"PASS: ECPP certificate {i}" not in replay.stdout for i in (1, 2)):
        detail = replay.stderr.strip() or replay.stdout.strip() or f"exit status {replay.returncode}"
        raise CertificateError(f"Fresh PARI/GP certificate replay failed: {detail}")

    output_path.write_text(
        "PARI/GP ECPP certificates generated by primecert and replay-checked in a fresh PARI/GP process with primecertisvalid.\n"
        "Primo and Magma export formats are included for optional cross-implementation review.\n\n"
        f"Prime 1: {primes[0]}\nPARI: {certificates[0]}\nPrimo format 4:\n{primo_exports[0]}\nMagma:\n{magma_exports[0]}\n\n"
        f"Prime 2: {primes[1]}\nPARI: {certificates[1]}\nPrimo format 4:\n{primo_exports[1]}\nMagma:\n{magma_exports[1]}\n",
        encoding="utf-8",
    )


def main(argv: list[str] | None = None) -> int:
    args = sys.argv[1:] if argv is None else argv
    pari_requested = "--pari" in args
    args = [arg for arg in args if arg != "--pari"]
    try:
        if len(args) == 0:
            document = load_embedded_document(Path(__file__))
            if document is None:
                print("Usage: python3 verify_pratt.py CERTIFICATE.json")
                print("Or download a one-file verifier bundle from the Lab and run it with no arguments.")
                return 2
        elif len(args) == 1 and args[0] not in {"-h", "--help"}:
            document = load_document(Path(args[0]))
        else:
            print("Usage: python3 verify_pratt.py CERTIFICATE.json")
            return 0 if args and args[0] in {"-h", "--help"} else 2
        total, p, q = verify_document(document)
    except (OSError, UnicodeError, json.JSONDecodeError, CertificateError, RecursionError, ValueError) as exc:
        print(f"FAIL: {exc}", file=sys.stderr)
        return 1

    if document.get("format") == MR64_FORMAT:
        print(f"PASS: {p} and {q} pass deterministic Miller–Rabin for n < 2^64.")
    elif document.get("format") == MR_PROBABLE_FORMAT:
        print(f"PROBABLE PASS: {q} passes the {document['rounds']} recorded Miller–Rabin rounds; primality is not proved.")
        print(f"PASS: {p} is prime by trial division and {p} + {q} = {total}.")
    else:
        print(f"PASS: {p} and {q} are prime by their Pratt certificates.")
    if document.get("format") != MR_PROBABLE_FORMAT:
        print(f"PASS: {p} + {q} = {total}.")
    if pari_requested:
        output_path = (Path(args[0]) if args else Path(__file__)).with_suffix(".pari-ecpp.txt")
        try:
            verify_with_pari((p, q), output_path)
        except (OSError, CertificateError, subprocess.TimeoutExpired) as exc:
            print(f"FAIL: PARI/GP cross-check: {exc}", file=sys.stderr)
            return 1
        print(f"PASS: PARI/GP generated ECPP certificates for {p} and {q}, then replay-checked them in a fresh process.")
        print(f"Saved PARI/GP certificate data to {output_path}")
        print(f"Saved replayable PARI/GP checker to {output_path.with_suffix('.pari-ecpp.gp')}")
    print("This verifies this one Goldbach representation; it does not prove the conjecture.")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())
