Número pseudoprimo de Lucas

Si n es compuesto, entonces esta congruencia generalmente no se cumple.

Ejemplos: si P = 3, Q = −1 y D = 13, la secuencia de U es (sucesión A006190 en OEIS): U0 = 0 , U1 = 1, U2 = 3, U3 = 10, etc. Primero, sea n = 19.

En este caso, 19 es primo, por lo que no es un pseudoprimo de Lucas.

De hecho, 119 es el pseudoprimo más pequeño para P = 3, Q = −1.

Como se analiza más abajo, para verificar la ecuación (2) para una n dada, no se necesita calcular todos los primeros n + 1 términos en la secuencia U.

Sea Q = −1, entonces, los pseudoprimos de Lucas más pequeños para P = 1, 2, 3, ... son Aquí se factoriza

Antes de iniciar una prueba de primos probables, generalmente se verifica que n, el número del que se va a probar su primalidad, es impar, no es un cuadrado perfecto y no es divisible por ningún primo pequeño menor que un límite conveniente.

Es una buena idea comprobar que n no tiene factores primos en común con P o Q.

Este método de elegir D, P y Q fue sugerido por John Selfridge.

Esta búsqueda nunca tendrá éxito si n es un cuadrado y, por el contrario, si tiene éxito, es una prueba de que n no es un cuadrado.

Dados D, P y Q, existen relaciones de recurrencia que permiten calcular rápidamente

También se calculan los términos del mismo número en la secuencia V, junto con Q1, Q2, Q4, Q5, Q 10, Q11, Q22 y Q44.

Al final del cálculo, se habrán obtenido Un+1, Vn+1 y n+1X, (mod n).

A continuación se verifica la congruencia (2) usando el valor conocido de Un+1.

Cuando se eligen D, P y Q como se describe anteriormente, los primeros 10 pseudoprimos de Lucas fuertes son: 5459, 5777, 10877, 16109, 18971, 22499, 24569 , 25199, 40309 y 58519 (sucesión A217255 en OEIS).

Con este método para seleccionar D, P y Q, los primeros 10 pseudoprimos de Lucas extra fuertes son 989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059 y 72389 (sucesión A217719 en OEIS).

Si resulta que n es compuesto, estas condiciones adicionales pueden ayudar a descubrir ese hecho.

Si la congruencia (2) o la (3) es falsa, esto constituye una prueba de que n no es primo.

Si ambas congruencias son verdaderas, entonces es aún más probable que n sea primo que si se hubiera verificado solo la congruencia (2).

permanezcan sin cambios y P = Q = 5 (véanse las Relaciones algebraicas en el artículo sucesión de Lucas).

Si se usa este método mejorado para elegir P y Q, entonces 913 = 11·83 es el único compuesto menor que 108 para el cual la congruencia (3) es verdadera (véase la página 1409 y la Tabla 6 de;[1]​).

Cálculos más extensos demuestran que, con este método de elegir D, P y Q, solo hay cinco números compuestos impares menores que 1015 para los cuales la congruencia (3) es verdadera.

, entonces se puede establecer una condición de congruencia adicional que implica muy pocos nuevos cálculos.

La otra se produce cuando n = p(p+2) es el producto de dos primos gemelos.

Tal n es fácil de factorizar, porque en este caso, n+1 = (p+1)2 es un cuadrado perfecto.

Un pseudoprimo de Fibonacci suele ser[2]​: 264,  [3]​: 142,  [4]​: 127 definido como un número compuesto n no divisible por 5 para el cual se cumple la congruencia (1) con P = 1 y Q = −1 (pero n lo es).

[4]​: 129  Hoggatt y Bicknell estudiaron las propiedades de estos pseudoprimos en 1974.

[12]​ Jacobsen enumera todos los 111.443 de estos pseudoprimos menores que 1013.

[13]​ Se ha demostrado que ni siquiera existen pseudoprimos de Fibonacci tal como los define la ecuación (5).

[14]​[15]​ Sin embargo, los pseudoprimos de Fibonacci sí que existen (sucesión A141137 en OEIS) bajo la primera definición dada por (1).