El problema de primalidad está en P

Abstract

El problema de saber si un número es o no primo de manera eficiente fue durante bastantetiempo un problema abierto y clave desde varios puntos de vista, tanto de teoría de la complejidadcomo de la algoritmia matemática. El trabajo consistirá en revisar el trabajo de Agrawal, Kayal ySaxena (2002) desarrollando un algoritmo con complejidad polinómica que resolvía de formadefinitiva el conocido problema Primes is in P?. Un detalle relevante es que, desde el punto de vistapráctico, el algoritmo no es especialmente útil, ya que hay algoritmos probabilistas muy rápidos ypotentes que cubren las necesidades de aplicación.