Prueba de primalidad de Proth con testigo

Primero verifica que k sea positivo e impar, que n sea positivo y que k sea menor que 2^n. Después calcula exactamente la potencia modular requerida. Una congruencia válida demuestra que el número de Proth es primo; un testigo fallido se declara inconcluso, salvo que revele un factor.

Introduzca un número de Proth auténtico y un testigo

Un número de Proth tiene la forma exacta N = k × 2^n + 1, donde k es un entero positivo impar, n es un entero positivo y k es estrictamente menor que 2^n. Todas estas condiciones son necesarias. La calculadora recibe k y el testigo como texto decimal para conservar valores grandes sin el redondeo propio de la coma flotante. Introduzca n como entero entre 1 y 10,000. La herramienta construye N en lugar de solicitarlo por separado, evitando discrepancias entre el número declarado y sus parámetros. También exige que el testigo esté estrictamente entre 1 y N. Si k es par, algún valor no es positivo o k es mayor o igual que 2^n, la entrada se rechaza como ajena a la forma de Proth, sin aplicar un teorema cuyas premisas no se cumplen. El número, el exponente, el testigo y el residuo se devuelven como cadenas decimales cuando corresponde, para que usted pueda auditarlos y copiarlos en otra herramienta de aritmética exacta.

Interprete correctamente lo que demuestra la congruencia

Para un número de Proth válido N, el teorema afirma que N es primo si existe un entero a tal que a^((N−1)/2) sea congruente con −1 módulo N. El testigo suministrado representa a, y la calculadora evalúa la potencia modular mediante cuadrados sucesivos, sin construir primero la inmensa potencia ordinaria. En la salida, `residue` es el residuo no negativo mínimo y `passes_test` vale true exactamente cuando coincide con N−1, la representación modular de −1. En ese caso, `prime_proven` vale true y el veredicto es `prime`: se trata de un certificado determinista bajo las condiciones de Proth ya validadas, no de una estimación de primo probable. La respuesta incluye el exponente exacto (N−1)/2 para que usted reproduzca la congruencia de manera independiente. El algoritmo solo usa operaciones enteras, no elige testigos al azar ni consulta tablas o servicios remotos. Por ello, una misma entrada siempre genera el mismo resultado y muestra todos los valores esenciales usados por el teorema.

Trate de forma correcta un testigo fallido

Que un testigo no produzca −1 no demuestra por sí solo que el número sea compuesto. Únicamente indica que ese testigo concreto no satisface la condición suficiente del teorema de Proth. Por eso la calculadora devuelve `inconclusive`, y no `composite`, cuando el residuo difiere y el testigo es coprimo con N. Usted puede probar después otro testigo elegido con criterio matemático o emplear otro método determinista de primalidad. Existe una excepción útil: antes de interpretar la congruencia, se calcula el máximo común divisor del testigo y N. Si el valor es un factor propio, el resultado es concluyentemente `composite` y se devuelve dicho factor. Esta distinción evita convertir por error un teorema unidireccional en una prueba bidireccional inválida. También facilita la automatización: acepte `prime` como demostración, rechace `composite` cuando aparezca un factor y derive `inconclusive` hacia otra prueba, sin tratarlo silenciosamente como un fallo definitivo.