John Conway <conway@math.princeton.edu> wrote:
My feeling is that the methods we used could be converted into a formal proof that one could distinguish between any two given candidate groups of orders < N in a time bounded by some power of log N. [Note that that's weaker than saying "find which group of order < N you have".]
But it's the former problem that Rich is taking N^O(logN) to solve! I suspect you're at least going to have to multiply that log N by the sum of the orders of the generators, in case someone gave you generators of two huge cyclic groups and asked you to test eqality with the black box multiplier. But even doing it in provably O(N^c) would be an advance. I suspect that's going to run into the same sort of problem graph isomorphism has. There are methods that work well on a lot of graphs, and combining them _seems_ to work well on all graphs, but we can't prove there isn't an exception. Dan