Prueba de primalidad de Lucas

Proporcione un entero impar n, un testigo de Lucas propuesto y la factorización prima completa de n menos uno. La calculadora valida la propia factorización, evalúa las potencias modulares y los máximos comunes divisores requeridos, y solo certifica n cuando se cumplen todas las condiciones del teorema de Lucas. Las cadenas decimales conservan enteros exactos, incluso más allá del intervalo seguro habitual de JavaScript.

Prepare un certificado completo

Comience con el entero impar que desea certificar y factorice por completo n menos uno. Introduzca n y cada factor primo como cadena decimal canónica, ya que las cadenas conservan valores exactos hasta el límite de 64 bits. Cada factor aparece una sola vez con su exponente positivo. Por ejemplo, n = 29 tiene n menos uno = 28 = 2 al cuadrado por 7, de modo que la lista contiene 2 con exponente 2 y 7 con exponente 1. También debe proporcionar una base a que cumpla 1 < a < n. Esta base es el testigo de Lucas propuesto. El verificador exige deliberadamente el testigo en vez de buscarlo: verificar un certificado es rápido, acotado y repetible, mientras que una búsqueda puede tener una duración dependiente de la entrada. Si aún no dispone de un testigo, pruebe bases pequeñas con una herramienta independiente de raíces primitivas y envíe después el certificado obtenido. Se rechazan espacios, signos, ceros iniciales, notación de coma flotante, primos duplicados, factores compuestos y factores ausentes, en lugar de normalizarlos silenciosamente; así, el certificado resulta apropiado para registros de auditoría y procesos automatizados.

Comprenda las dos condiciones de Lucas

El primer cálculo comprueba que a elevado a n menos uno sea congruente con 1 módulo n. Es la conocida condición de Fermat, pero por sí sola no demuestra primalidad porque algunos pseudoprimos pueden cumplirla. La segunda etapa decisiva usa cada primo distinto q que divide n menos uno. Para cada q, el verificador calcula a elevado a (n menos uno) dividido por q módulo n, resta uno y verifica que el resultado tenga máximo común divisor 1 con n. Superar todas estas comprobaciones demuestra que el orden multiplicativo de a módulo n es exactamente n menos uno. Ningún elemento módulo n puede tener ese orden salvo que n sea primo, y esta es la esencia del teorema de Lucas. Los registros devueltos muestran el residuo modular y el máximo común divisor para cada q distinto, mientras que el exponente permanece visible como parte de la factorización validada. La exponenciación modular emplea cuadrados sucesivos y aritmética BigInt exacta, por lo que el cálculo nunca depende del redondeo de coma flotante, bases aleatorias, servicios de red ni confianza probabilística.

Interprete los fallos y la salida correcta

Una respuesta correcta constituye el resultado de un certificado de primalidad, no una simple etiqueta de primo probable. Repite n, identifica el testigo aceptado, informa del residuo de Fermat y enumera una comprobación correcta del máximo común divisor para cada factor distinto de n menos uno. Conserve la entrada original junto con la respuesta cuando otro sistema necesite reproducir la prueba. Los fallos son específicos de forma intencionada. Si las potencias de los factores no multiplican exactamente n menos uno, la factorización está incompleta o es incorrecta. Si un factor indicado es compuesto o el mismo primo aparece dos veces, la factorización está mal formada aunque el producto bruto coincida. El fallo de una condición modular significa que la base proporcionada no es un testigo de Lucas; por sí solo no distingue entre un n compuesto y un primo acompañado de una base inadecuada. Pruebe otro testigo con justificación matemática si aún espera que sea primo. Las entradas se limitan a enteros impares desde 3 hasta 2^64 menos 1, lo que permite validar determinísticamente los factores primos indicados antes de evaluar el certificado. El precio de la API es $0.002 por solicitud.