Shor's quantum algorithm can factor integers, compute discrete logarithms in the multiplicative group and compute the same thing on elliptic curves. In 2023 Regev proposed a quantum algoritjm which uses n^(1/2) runs of a quantum procedure which uses n^(!/2)M(n) quantum gates as opposed to nM(n) for Shor. The new algorithm can factor integers and compute discrete logarithms but cannot apply to elliptic curves. In this talk we extend the algorithms to elliptic curves by showing how to find small points. We also discuss what are the rare numbers Regev cannot factor. Since Regev is based on heuristic assumptions we propose a method to certify at the beginning of the calculations that the algorithm will succeed on a particular instance.