{"id":"semiprime-factoring","name":"Semiprime factoring throughput","family":"algorithm-throughput","description":"Factor balanced semiprimes faster than a reference Pollard rho, in pure Python. The RSA-flavoured warm-up: real algorithmic ideas score, and the metric is a machine-independent speedup.","metric":"speedup","direction":"maximize","tolerance":0.5,"eval_timeout_seconds":300,"agent_timeout_seconds":900,"mutable":["factor.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, operator, typing, sys, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# Semiprime factoring throughput\n\n## Goal\n\n`factor.py` exposes `factor(n: int) -> int` returning a nontrivial factor of `n`, where `n` is a\nproduct of two distinct primes of roughly equal size (about 40 bits each by default, so `n` is\nabout 80 bits). Make it faster.\n\n## Metric\n\n`eval.py` generates a fixed set of semiprimes from a seed, times a reference Pollard rho\nimplementation on them, times your `factor`, checks every answer, and reports\n\n    metric = reference_seconds / your_seconds\n\nso a metric of 2.0 means twice as fast as the reference on the same machine. This is\nmachine-independent, which is why the hub can re-verify on different hardware. A wrong answer or\nan exception on any number is a failed run.\n\n## Constraints\n\n- Pure Python standard library only. No `gmpy2`, no `sympy`, no subprocess, no C extensions.\n  The eval rejects imports outside the standard library.\n- Deterministic algorithms preferred. If you use randomness, seed it so results replicate.\n- Do not read or modify `eval.py`. The hub scores with its own copy and a held-out seed, so\n  overfitting to the default seed will be rejected at verification.\n\n## Ideas that are known to matter (try things not already in journal.md)\n\n- Brent's cycle detection instead of Floyd; batch gcds (multiply k differences mod n, one gcd).\n- Better polynomial constants; restart strategy when rho finds n itself.\n- Trial division bound tuning; small-prime wheel before rho.\n- Lenstra ECM with Montgomery curves for a real algorithmic jump.\n- SQUFOF (Shanks) is competitive at this size and simple to implement.\n- Reduce Python overhead: local variable binding, avoiding function call overhead in the hot loop.\n\n## What \"novel\" looks like here\n\nAnything that shifts the speedup on the held-out set, reproducibly. Record the idea in one line\nin `NOTES.md` so the next agent (and the ledger) knows what you tried.\n\nSimpler is better: all else equal prefer the shorter solver, and treat removing code for an\nequal score as a win. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for semiprime-factoring. Prints one JSON line: {\"metric\": speedup, ...}.\n\nEnv:\n  ZT_EVAL_SEED   seed for the semiprime set (hub uses a held-out one)\n  ZT_EVAL_COUNT  number of semiprimes (default 8)\n  ZT_EVAL_BITS   bits per prime factor (default 40)\n  ZT_EVAL_REPEATS best-of-N timing (default 2)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport math\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nCOUNT = int(os.environ.get(\"ZT_EVAL_COUNT\", \"8\"))\nBITS = int(os.environ.get(\"ZT_EVAL_BITS\", \"40\"))\n\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"sys\", \"time\", \"collections\", \"operator\", \"typing\"}\n\n\ndef fail(msg: str, kind: str = \"error\") -> None:\n    \"\"\"kind is one of wrong_answer | compile_error | runtime_error | error (hub maps it to a verdict).\"\"\"\n    print(json.dumps({\"metric\": 0.0, \"error\": msg, \"kind\": kind}))\n    sys.exit(1)\n\n\ndef is_probable_prime(n: int, rng: random.Random) -> bool:\n    if n < 2:\n        return False\n    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29):\n        if n % p == 0:\n            return n == p\n    d, s = n - 1, 0\n    while d % 2 == 0:\n        d //= 2\n        s += 1\n    for _ in range(16):\n        a = rng.randrange(2, n - 1)\n        x = pow(a, d, n)\n        if x in (1, n - 1):\n            continue\n        for _ in range(s - 1):\n            x = x * x % n\n            if x == n - 1:\n                break\n        else:\n            return False\n    return True\n\n\ndef random_prime(bits: int, rng: random.Random) -> int:\n    while True:\n        c = rng.getrandbits(bits) | (1 << (bits - 1)) | 1\n        if is_probable_prime(c, rng):\n            return c\n\n\ndef make_semiprimes(seed: str, count: int, bits: int) -> list[int]:\n    rng = random.Random(f\"{seed}|{count}|{bits}\")\n    out = []\n    while len(out) < count:\n        p, q = random_prime(bits, rng), random_prime(bits, rng)\n        if p != q:\n            out.append(p * q)\n    return out\n\n\ndef reference_factor(n: int) -> int:\n    \"\"\"Floyd-cycle Pollard rho with c=1, trial division to 1000. The yardstick.\"\"\"\n    for p in range(2, 1000):\n        if n % p == 0:\n            return p\n    c = 1\n    while True:\n        x = y = 2\n        d = 1\n        while d == 1:\n            x = (x * x + c) % n\n            y = (y * y + c) % n\n            y = (y * y + c) % n\n            d = math.gcd(abs(x - y), n)\n        if d != n:\n            return d\n        c += 1\n\n\ndef check_imports(path: Path) -> None:\n    try:\n        tree = ast.parse(path.read_text(encoding=\"utf-8\"))\n    except SyntaxError as e:\n        fail(f\"syntax error in factor.py: {e}\", \"compile_error\")\n    for node in ast.walk(tree):\n        names = []\n        if isinstance(node, ast.Import):\n            names = [a.name.split(\".\")[0] for a in node.names]\n        elif isinstance(node, ast.ImportFrom) and node.module:\n            names = [node.module.split(\".\")[0]]\n        for nm in names:\n            if nm not in STDLIB_ALLOW:\n                fail(f\"import of '{nm}' is not allowed (stdlib subset only: {sorted(STDLIB_ALLOW)})\", \"compile_error\")\n\n\nREPEATS = int(os.environ.get(\"ZT_EVAL_REPEATS\", \"2\"))\n\n\ndef timed(fn, ns: list[int]) -> float:\n    \"\"\"Best of REPEATS runs, to damp timing jitter; every answer is checked every time.\"\"\"\n    best = float(\"inf\")\n    for _ in range(REPEATS):\n        t0 = time.perf_counter()\n        for n in ns:\n            d = fn(n)\n            if not isinstance(d, int) or d <= 1 or d >= n or n % d != 0:\n                fail(f\"{fn.__name__} returned a non-factor {d!r} for {n}\", \"wrong_answer\")\n        best = min(best, time.perf_counter() - t0)\n    return best\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"factor.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import factor as cand  # noqa: E402\n    except Exception as e:  # pragma: no cover\n        fail(f\"import factor.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"factor\"):\n        fail(\"factor.py must define factor(n) -> int\", \"compile_error\")\n\n    ns = make_semiprimes(SEED, COUNT, BITS)\n    ref_s = timed(reference_factor, ns)\n    try:\n        cand_s = timed(cand.factor, ns)\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"candidate raised {e!r}\", \"runtime_error\")\n    metric = ref_s / max(cand_s, 1e-9)\n    print(json.dumps({\"metric\": round(metric, 4), \"reference_seconds\": round(ref_s, 3),\n                      \"candidate_seconds\": round(cand_s, 3), \"count\": COUNT, \"bits\": BITS}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"factor.py":"\"\"\"Baseline: identical in spirit to the reference. Speedup ~1.0. Make it faster.\"\"\"\n\nimport math\n\n\ndef factor(n: int) -> int:\n    for p in range(2, 1000):\n        if n % p == 0:\n            return p\n    c = 1\n    while True:\n        x = y = 2\n        d = 1\n        while d == 1:\n            x = (x * x + c) % n\n            y = (y * y + c) % n\n            y = (y * y + c) % n\n            d = math.gcd(abs(x - y), n)\n        if d != n:\n            return d\n        c += 1\n"}}