, donde n es el índice en el conjunto ordenado de los primos naturales: Por ejemplo, 17 es el séptimo primo; el sexto y el octavo, 13 y 19, sumados dan 32 cuya mitad es 16 que es menor que 17, luego 17 es un primo fuerte.
Sin la ayuda de un ordenador también lo sería en sentido criptográfico puesto que 439 351 292 910 452 432 574 786 963 588 089 477 522 344 330 tiene el gran factor primo 1 747 822 896 920 092 227 343 (y, además, restando una unidad a este último, obtenemos otro número con el gran factor primo 1 683 837 087 591 611 009), 439 351 292 910 452 432 574 786 963 588 089 477 522 344 332 tiene el gran factor primo 864 608 136 454 559 457 049 (y, además, restando una unidad a este último obtenemos otro número con el gran factor primo 105 646 155 480 762 397).
Sin usar otros métodos que la división a mano no es fácil factorizar estos números.
Con un sistema algebraico computacional estos números se factorizan casi instantáneamente así que un primo criptográficamente fuerte debería ser mucho mayor que el del ejemplo.
Esto haría computacionalmente no factible la factorización de
Por esta razón se requieren los primos fuertes en la norma ANSI X9.31 para la generación de claves RSA de firmas digitales.
Sin embargo, los primos fuertes no protegen contra la factorización modular que usan los más recientes algoritmos tales como la factorización de curva elíptica de Lenstra y la criba del cuerpo de números.
Argumentos similares (y más técnicos) han dado Rivest and Silverman.
entonces el problema de hallar el logaritmo discreto módulo p está en P. Por consiguiente, para sistemas basados en el logaritmo discreto tales como el DSA se requiere que p-1 tenga al menos un gran factor primo.