Guldo

Compete

Submit a solver

Write one Python file with a function called solve. The judge announces which problem is being tested, and the problem decides what solve receives.

What you write

ProblemYour functionWhat it returns
gm
A lattice puzzle: find a short vector in a huge grid of points. Cryptography relies on this being hard.
solve(basis, bound2)Return any nonzero lattice vector, as a list of ints, with squared norm at most bound2 (1.05 x the Gaussian heuristic).
mlwe
The same kind of lattice puzzle, in the shape that modern encryption schemes use.
solve(basis, bound2)The same call on module-LWE-shaped lattices; the target is 1.5 x the planted short vector's norm.
factor
Factoring: split a large number into smaller whole numbers that multiply back to it.
solve(n)Return any nontrivial divisor of n, as an int.
dlog
Discrete logarithm: find the exponent x so that g to the power x leaves the remainder h, modulo a prime p.
solve(p, g, h)Return an integer x with pow(g, x, p) == h, 0 <= x < p - 1. Any valid x counts; return None for no answer.
  • Return a whole number, a list of whole numbers, or None. Anything else counts as a crash, and a failure is charged the full time limit.
  • Give the same output every time, use one process, and do not read files or use the network. Only fpylll, numpy and the standard library exist in the locked box.
  • print() is safe: it goes to the error stream and cannot corrupt your answer.
  • Some rounds count Python instructions instead of seconds (the round's page says so). Then your solver must be plain computation: loops, arithmetic, lists and dictionaries, and only these imports: math, itertools, heapq, bisect, functools, collections, fractions. No files, no sys, no getattr. Only the factoring problem can be counted so far. Try python3 counted.py check my_solver.py --family factor --dim 38 to see whether yours runs.

Check it first

The pre-flight check looks for anything the locked box blocks, runs your file on small public practice questions, checks every answer, and tests that it gives the same output each time. Passing means well-formed, not fast.

python3 submit_check.py solvers/my_solver.py --family gm
python3 submit_check.py solvers/my_solver.py --family factor

See how you'd be measured

Work out the cost of an official run before using machine time, and read the baseline solver for each problem.

python3 official.py plan --family gm
ls solvers/baseline_bkz.py solvers/factor_trial_py.py

From the command line

All of this is also one command, guldo. It checks your file, uploads it, and confirms your receipt in the round's public log using its own copy of the chain. It follows the round, and once the seeds are revealed it downloads your certificate and checks it on your own computer. No browser is needed. The Install page has the download and the three steps; the full guide is SUBMIT.md in the repository.

guldo practice my_solver.py --family dlog
guldo submit my_solver.py --round ROUND --handle NAME --accept-rules
guldo verify --round ROUND --id SUBMISSION_ID

The first command runs your solver on three seeds of your own and certifies the run, with no server involved. It is provisional by construction. Checking a certificate proves the arithmetic and the fairness, and it says whether the timings came from the locked box or from a plain local run.

What wins

Bits of speedup, certified: the cautious number described on the Method page, taken as the lowest over at least three seeds. A fast solver that fails the hard questions earns nothing, and so does one that only wins on trivial questions. A result that cannot be told apart from noise is reported as inconclusive.

Your algorithm can stay private. If you choose to publish your source, your certificate carries it and anyone can re-run it. If you don't, the public certificate carries only your solver's fingerprint: everyone can still check the log, the questions and the arithmetic, but only the operator can run your solver, so your timings rest on the operator's sandbox. If you publish the file later, anyone can check it against that fingerprint and re-run it.