Yo estaba involucrado en las conversaciones sobre este tema en el Polymath4 blog (en realidad, mirando hacia atrás, parece que yo fui el que cavó hasta que el viejo papel...) y llegué a creer que no existe ningún algoritmo aleatorizado, condicional, lo que sea). Sin duda he buscado en la literatura como mejor he podido y no encontrar uno. Pero soy pesimista sobre la búsqueda de una reducción de factoring, por las razones que he mencionado en el post vinculado.
Yo iba a hablar de este hermoso argumento, pero en realidad no creo que se aplica aquí, que sólo se puede utilizar squarefreeness decir, si el primer factor de $p | N$ ramifies sobre algunos de extensión (Edit: yo creo que esto es cierto ... pero algo extraño que podría suceder si la extensión no está Galois? Tal vez? Sé tan poco de la teoría algebraica de números no es incluso divertido), pero eso sólo es posible si p divide el discriminante, pero usted puede hacer que ya por el algoritmo de Euclides. Así squarefreeness sería sólo permiten factor tal vez si por alguna razón usted podría hacer el algoritmo rápidamente en número de campos con gran discriminante, que por cierto podría ser posible. Edit: Aunque, por supuesto, si el discriminante es lo suficientemente grande como para hacer una diferencia, no es claro cómo se desea extraer información acerca de p de todos modos. Que, modulo un montón de agujeros y handwaving, parece descartar cualquier ingenuo intento de adaptar esa "reducción".
