Esta es una parte de la computadora teórico de la cuestión, pero es probablemente más cerca de las matemáticas.
Recuerdo que encontrar un papel a partir de la década de 1980 o de modo que tenía una prueba de que el hecho de que encontrar el orden de un elemento de grupo no es más fácil de realizar una factorización de la orden del grupo.
Por no más fácil me refiero a que si existe un polinomio (en $\log(n)$ donde $n$ es el orden del grupo) algoritmo para encontrar el orden de un elemento, entonces existe un algoritmo polinomial para la factorización de $n$. Estoy particularmente interesado en la especial situación en la que el grupo es $\mathbb{Z}^*_p$ pero creo que el resultado podría haber sido más general.
¿Alguien por casualidad sabe el nombre de la ponencia? He estado tratando de encontrarlo, pero no puede. Creo que podría haber tenido alguna relación con la criptografía elíptica, pero no estoy seguro. Gracias por todas las pistas.
ps.: Si conoce a una fácil prueba de ello que también funcionaría.
Editar: Solo para aclarar, es fácil llegar elemento de orden en el poli tiempo si se le da la factorización de la orden de grupo como de entrada. La afirmación me parece recordar es que no hay ningún método que es en general más eficiente que la primera factorización.
No he leído la prueba (ya que no lo necesitaba y no tenía tiempo en ese momento), pero mi conjetura sería que usted podría utilizar elegido al azar de los elementos del grupo para obtener los factores del tamaño del grupo. El truco sería 1) mostrar que vas a tener suerte con la suficiente frecuencia (que es probablemente sólo un recuento argumento de algún tipo) y 2) para deshacerse de la aleatoriedad de alguna manera.
