Test de primalidad Pocklington
Demuestra que un número es primo a partir de una factorización parcial de n − 1: para 31, los primos 2, 3 y 5 de 30 dan una parte factorizada de 30, y como 900 es al menos 31, un testigo por primo lo certifica. Gratis en su navegador.
- Gratis
- Funciona en su navegador
- Sin registro
- Sus datos no salen de su equipo
Ejecutar — gratis
Ejemplo resuelto
- N
- 31
- Factores
- 2, 3, 5
- N
- 31
- N menos 1
- 30
- F
- 30
- R
- 1
El criterio de Pocklington–Lehmer convierte una factorización parcial de n menos uno en un certificado riguroso de primalidad. A diferencia de la sola división por tentativa o de una única congruencia de Fermat, basta con factorizar lo suficiente de n−1 para que la parte factorizada F cumpla F al cuadrado al menos n, más un testigo modular breve por cada primo que divide F. Estudiantes, tutores de criptografía y cuadernos de teoría de números usan este test de primalidad de Pocklington para demostrar primos pequeños y medianos sin cribar hasta la raíz cuadrada de n. Usted aporta el candidato n y los primos cuyo producto es F; el motor comprueba la cota de tamaño, busca o verifica bases a y devuelve un certificado estructurado o un error claro cuando la parte factorizada es demasiado pequeña.
Qué afirma el criterio de Pocklington–Lehmer
Escriba n menos uno como el producto F por R, donde F está completamente factorizado en primos que usted ya conoce y R es el cofactor restante.
El teorema clásico de Pocklington dice: si F es lo bastante grande para que F al cuadrado sea al menos n, y para todo primo q que divide F existe una base entera a tal que a elevado a n menos uno es congruente con uno módulo n, y el máximo común divisor de a elevado a (n menos uno) partido por q, menos uno, con n, vale uno, entonces n es primo.
De forma intuitiva, esas dos condiciones modulares obligan a que el orden multiplicativo de a módulo n sea múltiplo de q para cada uno de esos primos, de modo que el orden es múltiplo de F; al combinarlo con F mayor que la raíz de n, ningún n compuesto puede ocultar un factor propio del modo habitual. Esto es más fuerte que el pequeño teorema de Fermat solo, que revisa un único residuo de potencia y puede engañarse con seudoprimos.
También es más económico que factorizar n por completo o dividir hasta sqrt(n) cuando ya conoce muchos factores de n−1—por ejemplo si n es un número de Proth, una construcción de primo seguro o un entero de deberes diseñado para que n−1 factorice con facilidad.
Esta capacidad implementa exactamente esa lista de control: el producto de sus factores es F, R es (n−1)/F, se impone la cota F² ≥ n, y cada primo distinto q de F recibe un testigo a (buscado automáticamente desde dos en adelante, o tomado de su lista opcional bases).
Demostraciones en clase, demos de cifrado y automatización
Los cursos de teoría de números usan un test de primalidad de Pocklington para que el alumnado certifique primos como treinta y uno, sesenta y uno o noventa y siete tras factorizar n−1 a mano, en lugar de pulsar solo un botón opaco de is-prime. Autores de bibliotecas con property tests afirman que certified true implica que su propia rutina de primalidad coincide en el mismo n, y que un F insuficiente siempre lanza el error documentado de parte demasiado pequeña.
Mantenga n y factors dentro de los límites de dígitos y longitud, prefiera enteros en cadena más allá de los enteros seguros de JavaScript y trate certified como el booleano autoritativo de «Pocklington demostró primo». Cuando solo tenga un trozo minúsculo de n−1 factorizado, factorice más primero o use un comprobador de primalidad general; esta página se centra en la intención de búsqueda Pocklington–Lehmer para que SEO, ejemplos y forma de respuesta sigan enfocados.
Qué puede hacer con ella
Certificados de primalidad en deberes y exámenes
El alumnado factoriza n−1, envía n y los primos de F y recibe testigos que demuestran que n es primo bajo Pocklington–Lehmer cuando F es lo bastante grande.
Correctores de concursos y LMS
Califique ítems de teoría de números con un oráculo de certificado determinista que rechaza F demasiado pequeño y listas de factores no primos en lugar de falsos positivos silenciosos.
Preguntas frecuentes
¿Qué es el test de primalidad de Pocklington?
Un criterio que certifica que n es primo a partir de una factorización parcial n−1=F·R con F totalmente factorizado, F²≥n y testigos modulares a por cada primo q que divide F.
¿Cuándo la parte factorizada es demasiado pequeña?
Cuando F² < n (equivalente a F ≤ R en la descomposición n−1=F·R).
¿Qué entradas debo enviar?
Obligatorios n (≥3) y factors (array de primos con multiplicidad cuyo producto es F).
¿Si certified es false, n es compuesto?
No. Significa que no se halló un testigo válido con el F y las bases dados. n aún puede ser primo; pruebe más bases, una parte factorizada mayor u otro método de primalidad.
¿Puedo elegir yo las bases testigo?
Sí. Indique números enteros de al menos 2: una sola base para todos los primos o una por cada primo distinto, en orden. Si no indica ninguna, la prueba busca bases del 2 al 200 por su cuenta.
Herramientas relacionadas
Para desarrolladores — acceso por API
Todo lo de esta página está disponible por programación. Esta sección es para equipos que quieren integrarlo en sus sistemas; el resto puede usar la herramienta de arriba sin más.
Endpoint de API
¿Prefiere automatizarlo? Un POST autenticado crea la tarea; el resultado llega por webhook o enlace firmado. La misma capacidad también se ejecuta aquí en la web, por email y desde Telegram — y pronto también desde nuestra app.
Llámela desde su stack
curl -X POST https://api.kit.forhosting.com/numth/pocklington-test \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":31,"factors":[2,3,5]}'const res = await fetch("https://api.kit.forhosting.com/numth/pocklington-test", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 31,
"factors": [
2,
3,
5
]
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/pocklington-test",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 31,
"factors": [
2,
3,
5
]
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/pocklington-test", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":31,"factors":[2,3,5]}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":31,"factors":[2,3,5]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/pocklington-test", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Ejemplo de solicitud
{
"n": 31,
"factors": [
2,
3,
5
]
}Ejemplo de respuesta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.pocklington_test",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}La API es asíncrona: la llamada devuelve un task_id al instante y el resultado llega por webhook. El polling está limitado a 1 req/s por tarea.
Precio
Precio publicado — sin tokens ni créditos inventados. Una tarea fallida no se cobra.
Errores
| HTTP | Código | Significado |
|---|---|---|
401 | unauthorized | API key ausente o inválida. |
402 | insufficient_balance | El saldo no cubre el precio de la tarea. |
404 | unknown_type | El tipo de tarea no existe. |
429 | rate_limited | Demasiadas peticiones. Use el webhook en vez de sondear. |
Notas técnicas
La misma lógica pura BigInt alimenta la herramienta gratuita del navegador y la ruta API a $0.002 por solicitud exitosa.
Qué afirma el criterio de Pocklington–Lehmer
Cuando todos los primos pasan, la respuesta pone certified e is_prime en true y enumera los testigos para que usted pueda rehacer la aritmética a mano o en otro sistema.
Contrato de entrada, errores de tamaño y lectura del certificado
Ejemplo: n igual a treinta y uno y factors igual a dos, tres, cinco porque treinta es dos por tres por cinco; entonces F es treinta, R es uno y F al cuadrado supera con creces treinta y uno. El campo opcional bases es un array de enteros al menos dos—un testigo compartido para todos los primos, o un testigo por primo distinto en orden ordenado—o se omite y el motor busca a desde dos hasta doscientos. Si el producto F no divide n−1, la tarea falla porque la factorización parcial es inconsistente. Si F al cuadrado es estrictamente menor que n, falla con un mensaje de que la parte factorizada es demasiado pequeña—ese es el error duro intencional cuando no ha factorizado lo suficiente de n−1 para aplicar Pocklington–Lehmer. Envíe por POST un cuerpo JSON con el entero obligatorio n (al menos tres) y el array obligatorio factors: los factores primos, con multiplicidad, de la parte factorizada F de n−1. Cada factor listado debe ser primo; las entradas compuestas fallan con invalid_input para que una lista falsificada no finja un certificado. Las respuestas correctas repiten n, n_minus_1, F, R, F_squared, floor_sqrt_n, los primos distintos, el multiconjunto de factores y un array witnesses con a por primo, el residuo de potencia, la comprobación gcd y las banderas ok. El booleano certified es true solo cuando todo primo tiene testigo válido; is_prime refleja certified aquí porque un pase completo de Pocklington es una prueba de primalidad, mientras que un fallo al buscar testigos no demuestra por sí solo que n sea compuesto. El precio es un fijo $0.002 por llamada exitosa en la unidad item; los fallos de validación no se facturan. Enteros grandes pueden enviarse como cadenas decimales dentro del límite de dígitos publicado para que JSON no los trunque.
Demostraciones en clase, demos de cifrado y automatización
Las herramientas de preparación de concursos generan candidatos con n−1 suave, envían los factores conocidos a este endpoint y guardan los testigos devueltos como un objeto de prueba breve junto a la clave de respuestas. Como la implementación es parse pura de nivel A, cada llamada exitosa cuesta el $0.002 publicado sin tokens de modelo ni red saliente; la ruta gratuita del navegador ejecuta la misma función solve.
Casos de integración
Comprobaciones en cuadernos de cifrado y CAS
Fije certificados golden de Pocklington para primos fijos en pruebas unitarias sin reimplementar modPow y comprobaciones gcd en cada lenguaje.
Preguntas técnicas
¿Cuánto cuesta el test de primalidad de Pocklington?
La herramienta del navegador es gratuita. Las solicitudes API usan saldo prepago KIT a $0.002 por llamada exitosa; la entrada inválida no se cobra.