Identifying lens spaces using discrete logarithms
Skip to main content
Open Access Publications from the University of California

Department of Mathematics

Faculty bannerUC Davis

Identifying lens spaces using discrete logarithms

  • Author(s): Kuperberg, Greg
  • et al.

Published Web Location
No data is associated with this publication.

We show that if a closed, oriented 3-manifold M is secretly homeomorphic to a lens space L(n,k), then we can compute n and k in randomized polynomial time (in the size of the triangulation of M) with a discrete logarithm oracle. Using Shor's algorithm, a quantum computer can thus identify lens spaces in quantum polynomial time. In addition, k can be computed in functional NP. A given value of k can be certified in randomized polynomial time, specifically in coRP. The idea of the algorithm is to calculate Reidemeister torsion over a prime field that has nth roots of unity.

Item not freely available? Link broken?
Report a problem accessing this item