Prueba de primalidad de Solovay-Strassen con base elegida
Con 13 y base 2, ambos restos salen 12, así que 13 supera la prueba y es probable primo para la base 2. Si no coincidieran, quedaría demostrado que el número es compuesto. Gratis en su navegador.
- Gratis
- Funciona en su navegador
- Sin registro
- Sus datos no salen de su equipo
Ejecutar — gratis
Ejemplo resuelto
- N
- 13
- Primer texto
- 2
- Gcd
- 1
- Símbolo de Jacobi
- -1
- Residuo de Euler
- 12
- Residuo esperado
- 12
La prueba de primalidad de Solovay-Strassen comprueba si un entero impar se comporta como primo para una base que usted selecciona. Calcula el símbolo de Jacobi de la base módulo el candidato, eleva esa base a la mitad del candidato menos uno y compara ambos valores módulo el candidato. El resultado identifica un testigo definitivo de composición o indica que el número es probablemente primo para esa base. Las entradas son cadenas decimales, por lo que los enteros grandes se conservan exactamente y no sufren redondeo de coma flotante.
Qué significa la comparación
Para un primo impar n y cualquier base a que no sea divisible por n, el criterio de Euler establece que a elevada a (n - 1) / 2 es congruente módulo n con el símbolo de Legendre de a. El símbolo de Jacobi amplía el cálculo a candidatos compuestos impares, de modo que puede obtenerse con poco coste sin conocer la factorización de n.
Solovay-Strassen compara la potencia modular con el símbolo de Jacobi expresado como residuo: 1 permanece como 1, mientras que -1 se convierte en n - 1. Una discrepancia demuestra matemáticamente que n es compuesto. Otra base válida puede revelar que un número compuesto que superó la primera comparación no es primo.
La respuesta incluye ambos residuos, el valor de Jacobi y el máximo común divisor para que usted pueda inspeccionar la decisión en lugar de recibir un booleano sin explicación.
Cómo elegir y validar las entradas
Proporcione n y a como cadenas decimales sin signo. El candidato n debe ser impar y al menos 3; los valores pares y menores generan un error de entrada no válida porque quedan fuera del dominio de esta prueba. La base debe cumplir 1 < a < n.
No es necesario comprobar previamente que sea coprima: la capacidad calcula gcd(a, n), y un factor común no trivial determina de inmediato que el candidato es compuesto. Cada entrada admite como máximo 1,000 dígitos decimales, lo que impone un límite computacional claro. Se rechazan signos, espacios, puntos decimales, notación exponencial y ceros iniciales para evitar interpretaciones ambiguas.
Si usted elige bases manualmente, emplee varias bases distintas para obtener evidencia más sólida. La capacidad no selecciona bases al azar; así, cada ejecución es reproducible y queda registrado exactamente qué testigo se comprobó.
Cómo interpretar el resultado con rigor
El campo passes indica si la congruencia exacta de Solovay-Strassen se cumple para el par suministrado. Si es false, classification vale composite y la base proporcionada certifica que el candidato no puede ser primo. Repita la prueba con bases seleccionadas de forma independiente si un ejercicio o protocolo exige Solovay-Strassen, y considere cada ronda superada como evidencia probabilística adicional, nunca como una demostración.
Para sistemas nuevos sensibles a la seguridad, use un procedimiento moderno de primalidad cuidadosamente especificado, con rondas apropiadas y aleatoriedad revisada, en vez de confiar en una única base elegida manualmente.
Qué puede hacer con ella
Comprobar un testigo de un manual
Reproduzca un ejercicio de Solovay-Strassen con el candidato y la base exactos indicados en el enunciado.
Examinar el comportamiento de un pseudoprimo
Compare cómo un candidato compuesto supera la prueba con una base y falla con otra, conservando todos los valores intermedios.
Crear una etapa de cribado reproducible
Registre resultados deterministas para una sola base antes de aplicar más bases o un procedimiento de primalidad más fuerte.
Preguntas frecuentes
¿Un resultado superado demuestra que n es primo?
No. Solo significa que n es probablemente primo para la base proporcionada; otra base puede demostrar que es compuesto.
¿Por qué n debe ser impar y al menos 3?
La comparación mediante el símbolo de Jacobi empleada aquí está definida para candidatos impares de al menos 3.
¿Qué ocurre si a y n comparten un factor?
El valor gcd devuelto muestra el factor común y la prueba clasifica n como compuesto sin considerar superada la comparación de Jacobi.
¿La capacidad elige una base aleatoria?
No. Usted proporciona la base, por lo que el cálculo es determinista y reproducible.
¿Qué tamaño pueden tener los números en la prueba de Solovay-Strassen?
Cada número admite hasta 1.000 cifras decimales. Se tratan exactamente como usted los escribe, sin redondeo, de modo que un candidato enorme recibe la misma comparación exacta que uno pequeño.
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/solovay-strassen-test \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":"561","a":"2"}'const res = await fetch("https://api.kit.forhosting.com/numth/solovay-strassen-test", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": "561",
"a": "2"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/solovay-strassen-test",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": "561",
"a": "2"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/solovay-strassen-test", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":"561","a":"2"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":"561","a":"2"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/solovay-strassen-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": "561",
"a": "2"
}Ejemplo de respuesta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.solovay_strassen_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.
Límites
max_digits | 1000 |
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
Qué significa la comparación
Una coincidencia es una conclusión más débil: solo indica que n superó la prueba para la base elegida, por lo que la clasificación es probable_prime_to_base.
Cómo elegir y validar las entradas
Este formato es importante porque los números JSON ordinarios no representan con exactitud todos los enteros grandes.
Cómo interpretar el resultado con rigor
Si es true, classification vale probable_prime_to_base, no prime. Los campos detallados explican el resultado: gcd muestra un factor común inmediato; jacobi_symbol es -1, 0 o 1; euler_residue es la potencia modular calculada; y expected_residue normaliza el valor de Jacobi al intervalo módulo n. Las solicitudes mediante API usan el precio base publicado $0.002; el mismo cálculo determinista también puede ejecutarse de forma interactiva en el navegador.
Preguntas técnicas
¿Por qué n y a son cadenas y no números JSON?
Las cadenas decimales conservan con exactitud los enteros que superan el intervalo numérico seguro de JavaScript y evitan redondeos silenciosos.
¿Cuánto cuesta una solicitud mediante API?
El cargo base es $0.002 por solicitud. Cada solicitud evalúa un par de candidato y base.