Probablemente un número primo

En la teoría de números , un número probablemente primo ( ing. probablemente primo , PRP) es un número entero que satisface ciertas condiciones que satisfacen todos los números primos . Diferentes tipos de probablemente simples tienen diferentes condiciones. Dado que un primo probable puede ser compuesto (dichos números se denominan pseudoprimos ), se elige la condición para que estas excepciones sean raras.

La prueba de primalidad de Fermat, basada en el Pequeño Teorema de Fermat , funciona de la siguiente manera: dado n , elija algún a tal que a y n sean coprimos y calcule un n - 1 módulo n . Si el resultado es diferente de 1, entonces n es compuesto. Si el resultado es 1, n puede ser primo, pero no necesariamente; n en este caso se dice que es (débil) probablemente primo en base a .

Propiedades

La simplicidad asequible es la base para crear algoritmos de prueba de primalidad eficientes que encuentran aplicación en la criptografía . Estos algoritmos suelen ser estocásticos. La idea es que mientras haya primos probabilísticos compuestos en base a para cualquier a fijo , podemos esperar que haya algún P < 1 tal que para cualquier n compuesto dado , si elegimos a al azar, la probabilidad de que n sea pseudoprimo base a , no menor que P . Si repetimos esta prueba k veces, eligiendo cada vez un nuevo número a , la probabilidad de que n sea pseudoprimo para todos los a probados es al menos P k . Dado que esta probabilidad decrece exponencialmente, no se necesita un k muy grande para que esta probabilidad sea despreciable (en comparación, por ejemplo, con la probabilidad de que ocurra un error en el procesador).

Desafortunadamente, esto no es cierto para primos probables débiles, ya que hay números de Carmichael , pero es cierto para una selección más estricta de primos probables, como primos probables fuertes ( P = 1/4, prueba de Miller-Rabin ), o Euler probable. primos ( P = 1/2, prueba de Nightingale-Strassen ).

Incluso cuando se requiere un algoritmo de verificación determinista, una prueba de primalidad probable es un primer paso útil. Puede eliminar la mayoría de los multiplicadores rápidamente.

La prueba PRP a veces se combina con una pequeña tabla de pseudoprimos para probar rápidamente la primacía de un número que es menor que un valor de umbral.

Variaciones

Probablemente, el primo de Euler en base a es un entero que satisface condiciones de primalidad más fuertes que el teorema: para cualquier primo p , a ( p − 1)/2 es igual en base p , donde es el símbolo de Legendre . Probablemente los primos de Euler que son compuestos se llaman pseudoprimos de Euler-Jacobi en base a . $({\tfrac{a}{p)))$ $({\tfrac{a}{p)))$

Esta prueba se puede mejorar usando el hecho de que la raíz cuadrada de 1 en una base prima es 1 y −1. Escribimos n = d • 2 s + 1, donde d es impar. Un número n es primo probable fuerte (SPRP) en base a si se cumple una de las siguientes condiciones:

a^{d}\equiv 1{\pmod n},\;

a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}{\text{ para algunos }}0\leq r\leq s-1.

Un primo probable fuerte compuesto en base a se dice que es pseudoprimo fuerte en base a . Todo primo probable fuerte en base a es también un primo probable de Euler en la misma base, pero no al revés.

Véase también

Enlaces

Sistemas numéricos
Conjuntos contables	Números naturales ( ) $\scriptstyle \mathbb {N}$ Enteros ( ) $\scriptstyle \mathbb {Z}$ Racional ( ) $\scriptstyle \mathbb {Q}$ algebraico ( ) $\scriptstyle {\overline {\mathbb {Q} }}$ Períodos Calculable Aritmética
Números reales y sus extensiones.	reales ( ) $\scriptstyle \mathbb {R}$ Complejo ( ) $\scriptstyle \mathbb {C}$ Cuaterniones ( ) $\scriptstyle \mathbb {H}$ Números de Cayley (octavas, octoniones) ( ) $\scriptstyle \mathbb {O}$ Sedeniones ( ) $\scriptstyle \mathbb {S}$ Alterniones Doble Hipercomplejo superrealista hipermaterial surrealista
Herramientas de extensión numérica	procedimiento de Cayley-Dixon teorema de frobenius teorema de Hurwitz
Otros sistemas numéricos	Numeros cardinales Números ordinales (transfinitos, ordinales) p-ádico Números sobrenaturales números de intervalo
ver también	números dobles Numeros irracionales numeros trascendentales haz de números bicuaternión