Attested & literatureAlgorithmsAlgorithmHidden-period / factoring
Discrete logarithm on a quantum computer
Given three n-bit numbers a, b and N with the promise that b = a^s mod N for some s, recover the exponent s.
Every quantum algorithm worth knowing about, written down the same way: what it takes, what it returns, what it costs, and who proved it.
The Map draws our corpus as one connected structure: Open the Map
Every source behind both surfaces: See the papers
A speedup class on a record is quoted: See whose claim it is
Every record is classified by how it was verified. The badge shows the strongest tier of evidence; the chips list each method that applies.
The defining behavior was checked exactly: a mathematical identity, a full statevector or stabilizer simulation, or an exhaustive basis-state truth table.
The design was verified by construction plus measured evidence: statistical re-execution, small-instance analytic agreement, sub-block, echo, or invariant checks. Scale-specific bugs can still survive.
The record rests on external authority: peer-reviewed papers, standard textbooks, expert review, or evidence carried over from related verified entries. Nothing here was re-executed by this catalog.
Only automated (LLM-assisted) review or an unreviewed community submission backs this record so far. Treat it as a starting point, not evidence.
5 public entries
Atlas stars stay in this public list. Saving an entry to your workspace starts an unstarred private copy.
Given three n-bit numbers a, b and N with the promise that b = a^s mod N for some s, recover the exponent s.
Carry Shor's discrete-logarithm algorithm through concretely for the group of points on an elliptic curve over GF(p), and count the qubits and operations it needs, so that the cost of attacking elliptic-curve cryptography can be compared with the cost of attacking RSA at an equivalent classical security level.
Given black-box access to a finite ring R, not necessarily commutative, together with a list of generators for an ideal I in R, find an additive basis representation for I.
The cryptography-facing quantum algorithm record, with the assumptions that make its security relevance precise.
Give polynomial-time quantum algorithms for three average-case lattice problems in parameter regimes where none was known: the short integer solution problem under the infinity norm, the learning-with-errors problem when the input is supplied as LWE-like quantum states rather than classical samples, and the extrapolated dihedral coset problem.