Participé en las conversaciones sobre este tema en el blog Polymath4 (en realidad, mirando hacia atrás, parece que Fui yo que desenterró ese viejo artículo...) y llegué a creer que no existía tal algoritmo (aleatorio, condicional, lo que sea). Ciertamente busqué en la literatura lo mejor que pude y no encontré ninguno. Pero soy pesimista sobre la posibilidad de encontrar una reducción a partir de la factorización, por razones que toqué en el post enlazado.
Iba a mencionar este bonito argumento, pero en realidad no creo que se aplique aquí -- sólo se puede usar la cuadratura para saber si un factor primo $p | N$ ramifica sobre alguna extensión (Edit: I piense en esto es cierto -- ¿pero podría pasar algo raro si la extensión no es Galois? ¿Quizás? Sé tan poco de teoría algebraica de números que ni siquiera me hace gracia), pero eso sólo es posible si p divide al discriminante -- pero eso ya se puede hacer con el algoritmo euclídeo. Así que la cuadratura sólo te permitiría quizás factorizar si por alguna razón pudieras hacer el algoritmo rápidamente en campos numéricos con discriminantes enormes, lo cual hay que admitir que podría ser posible. Editar: Aunque, por supuesto, si el discriminante es lo suficientemente grande como para hacer una diferencia, no está claro cómo se puede extraer información acerca de p de todos modos. Lo cual, modulo un montón de agujeros y manipulaciones, parecería descartar cualquier intento ingenuo de adaptar esa "reducción".
