Este en particular es un número de Mersenne prime, primalidad de lo cual se confirma con el de Lucas-Lehmer de la Prueba. Demostrando estos números prime debe realizarse en un equipo, y que puede tomar meses para realizar los correspondientes cálculos. GIMPS aloja un proyecto de la computación distribuida para la búsqueda de números primos de Mersenne.
La multiplicación modulo $M_p:=2^p-1$ puede ser realizada usando la aritmética de precisión arbitraria. Altamente optimizado bibliotecas por George Woltman (y otros) se utilizan para realizar el cálculo en sí; hacen uso de discretos ponderado transforma para acelerar el cálculo.
R. Crandall y B. Fagin, Discreto ponderado de las transformaciones y de gran aritmética de enteros, de Matemáticas. Comp. 62 (1994) 305-324. (pdf)
De hecho, existen varias pruebas similares a las de Lucas Lehmer de la Prueba. El de Lucas Lehmer de la Prueba se ve favorecida porque es necesario y suficiente (es decir, un pase implica primalidad, y un error implica compositeness).
Lucas Lehmer Prueba: $M_n:=2^n-1$ es primo si y sólo si $S_{n-2} \equiv 0 \pmod {M_n}$ donde$S_0=4$$S_i=S_{i-1}^2-2$$i \geq 1$.
Para comprobar que $2^{19}$ es primo, calculamos el $S_i \pmod {M_{19}}$$0 \leq i \leq 17$, $$4, 14, 194, 37634, 218767, 510066, 386344, 323156, 218526, 504140, 103469, 417706, 307417, 382989, 275842, 85226, 523263, 0.$$
Teorema: Si $n \equiv -1 \pmod 4$, $M_n$ es primo si $T_{n-2} \equiv 0 \pmod {M_n}$ donde$T_0=3$$T_i=T_{i-1}^2-2$$i \geq 1$.
Para comprobar que $2^{19}$ es primo, calculamos el $T_i \pmod {M_{19}}$$0 \leq i \leq 17$, $$3, 7, 47, 2207, 152264, 354554, 244924, 420095, 86240, 326503, 409010, 208425, 132664, 470878, 399999, 439061, 523263, 0.$$
Teorema: Vamos a $U_0=4$, $U_1=52$ y $U_i=14U_i-U_{i-2}$$i \geq 2$. Si $U_{n-2} \equiv \pm 2^{(n+1)/2} \pmod n$ $M_n$ es primo.
Para comprobar que $2^{19}$ es primo, calculamos el $T_i \pmod {19}$$0 \leq i \leq 17$, que es $$4, 14, 2, 14, 4, 4, 14, 2, 14, 4, 4, 14, 2, 14, 4, 4, 14, 2.$$ We now check that $2^{(n+1)/2} \equiv -2 \pmod {19}$.
Hay varios otros teoremas en el siguiente artículo (no todos por los números primos de Mersenne):
D. H. Lehmer, Una Teoría Ampliada de Lucas' Funciones, Ann. Matemáticas. (2), 31 (1930), 419-448. (enlace)
Similar algoritmos eficientes que existen para otros números, como $$k \times 2^n+1$$ with $2^n<k$, which are called Proth numbers (the Brillhart-Lehmer-Selfridge test; see also Proth's Theorem), and $$k \times 2^n-1$$ with $2^n<k$ (el de Lucas–Lehmer–Riesel de prueba).
