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

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