q-Seudoprimalidad vs w-primalidad

Abstract

Desde sus orígenes, la Teoría de Números ha tratado de resolver dos grandes problemas: el primero de estos es determinar si un número es compuesto o no y el segundo es, sabiendo que el número es compuesto, encontrar su descomposición en factores primos. En el artículo 329 de las DISQUISITIONES ARITHMETICAE de Carl F. Gauss, se destaca la importancia de resolver estos problemas, pero además se menciona que los métodos desarrollados para la solución de estos han sido laboriosos y algo tediosos para números grandes . A través del desarrollo tecnológico y la llegada de los computadores el ser humano se ha interesado por implementar algoritmos que se acercan a la solución de dichos problemas basados en teoremas como el Teorema de Pocklington, Teorema de Lucas-Lehmer, entre otros, pero a pesar de estos avances, en términos generales el problema sigue sin solución, ya que siempre es posible encontrar números para los cuales ni los algoritmos actuales, ni la capacidad de computo desarrollada hasta el momento pueden determinar su primalidad. Este hecho ha motivado el desarrollo de teorías que permitan por lo menos saber si un número es compuesto sin saber cuáles son sus factores, o decir con una alta probabilidad que un número es primo.