Test de primalité de Solovay-Strassen avec une base choisie
Avec 13 et la base 2, les deux restes valent 12 : 13 réussit le test et est probablement premier pour la base 2. Un désaccord prouverait au contraire que le nombre est composé. Gratuit dans votre navigateur.
- Gratuit
- Fonctionne dans votre navigateur
- Sans inscription
- Vos données restent sur votre appareil
Lancer gratuitement
Exemple résolu
- N
- 13
- Premier texte
- 2
- Gcd
- 1
- Symbole de Jacobi
- -1
- Résidu d'Euler
- 12
- Résidu attendu
- 12
Le test de primalité de Solovay-Strassen vérifie si un entier impair se comporte comme un nombre premier pour une base que vous choisissez. Il calcule le symbole de Jacobi de la base modulo le candidat, élève cette base à la moitié du candidat moins un, puis compare les deux valeurs modulo le candidat. Le résultat fournit soit un témoin certain de composition, soit l’indication que le nombre est probablement premier pour cette base. Les entrées sont des chaînes décimales afin de préserver exactement les grands entiers, sans arrondi en virgule flottante.
Comprendre la comparaison
Pour un nombre premier impair n et toute base a non divisible par n, le critère d’Euler affirme que a élevée à la puissance (n - 1) / 2 est congrue modulo n au symbole de Legendre de a. Le symbole de Jacobi étend ce calcul aux candidats composés impairs, sans qu’il soit nécessaire de connaître la factorisation de n. Solovay-Strassen compare la puissance modulaire au symbole de Jacobi représenté comme résidu : 1 reste 1, tandis que -1 devient n - 1.
Une différence prouve mathématiquement que n est composé. Une autre base valide peut révéler la nature composée d’un nombre ayant réussi la première comparaison. La réponse présente les deux résidus, la valeur de Jacobi et leur plus grand commun diviseur, afin que vous puissiez contrôler la décision au lieu de recevoir un booléen inexpliqué.
Choisir et valider les entrées
Fournissez n et a sous forme de chaînes décimales non signées. Le candidat n doit être impair et au moins égal à 3 ; les valeurs paires ou inférieures produisent une erreur d’entrée, car elles sortent du domaine annoncé. La base doit vérifier 1 < a < n.
Vous n’avez pas à vérifier au préalable qu’elle est première avec n : la capacité calcule gcd(a, n), et un facteur commun non trivial établit immédiatement que le candidat est composé. Chaque entrée est limitée à 1,000 chiffres décimaux afin de fixer une borne de calcul explicite. Les signes, espaces, séparateurs décimaux, notations exponentielles et zéros initiaux sont refusés pour éviter toute interprétation ambiguë.
Si vous choisissez les bases manuellement, utilisez plusieurs bases distinctes pour renforcer les éléments probants. Aucune base aléatoire n’est choisie ici : chaque exécution reste reproductible et consigne précisément le témoin contrôlé.
Interpréter le résultat avec prudence
Le champ passes indique si la congruence exacte de Solovay-Strassen est satisfaite pour la paire fournie. S’il vaut false, classification vaut composite et la base constitue un certificat que le candidat ne peut pas être premier. Répétez le test avec des bases sélectionnées indépendamment lorsqu’un exercice ou un protocole impose Solovay-Strassen, et considérez chaque réussite comme un élément probabiliste supplémentaire, jamais comme une preuve.
Pour tout nouveau système sensible à la sécurité, préférez une procédure moderne de test de primalité, précisément définie, avec un nombre adapté de tours et un aléa validé, plutôt qu’une seule base choisie manuellement.
Cas d’usage
Vérifier un témoin de manuel
Reproduisez un exercice de Solovay-Strassen avec le candidat et la base exacts indiqués dans l’énoncé.
Étudier le comportement d’un pseudo-premier
Comparez un candidat composé qui réussit avec une base et échoue avec une autre, tout en conservant les valeurs intermédiaires.
Créer un filtrage reproductible
Consignez le résultat déterministe d’une base avant d’appliquer d’autres bases ou une procédure de primalité plus robuste.
Questions fréquentes
Une réussite prouve-t-elle que n est premier ?
Non. Elle signifie seulement que n est probablement premier pour la base fournie ; une autre base peut prouver qu’il est composé.
Pourquoi n doit-il être impair et au moins égal à 3 ?
La comparaison par symbole de Jacobi utilisée ici est définie pour les candidats impairs au moins égaux à 3.
Que se passe-t-il si a et n ont un facteur commun ?
Le champ gcd révèle le facteur commun et le test classe n comme composé sans considérer la comparaison de Jacobi comme réussie.
La capacité choisit-elle une base aléatoire ?
Non. Vous fournissez la base, ce qui rend le calcul déterministe et reproductible.
Quelle taille peuvent avoir les nombres du test de Solovay-Strassen ?
Chaque nombre peut compter jusqu'à 1 000 chiffres décimaux. Ils sont traités exactement tels que vous les saisissez, sans arrondi : un très grand candidat reçoit la même comparaison exacte qu'un petit.
Outils associés
Pour les développeurs — accès API
Tout sur cette page est disponible par programmation. Cette section s'adresse aux équipes qui veulent l'intégrer à leurs systèmes ; les autres peuvent simplement utiliser l'outil ci-dessus.
Endpoint
Authentification par jeton Bearer : un seul POST met la tâche en file d’attente, et le résultat vous parvient par webhook ou lien signé.
Appeler depuis votre 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)Exemple de requête
{
"n": "561",
"a": "2"
}Exemple de réponse
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.solovay_strassen_test",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L’API est asynchrone : chaque appel renvoie un task_id immédiatement, puis vous interrogez l’état à raison d’une requête par seconde.
Tarifs
Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.
Limites
max_digits | 1000 |
Erreurs
| HTTP | Code | Signification |
|---|---|---|
401 | unauthorized | Clé API absente ou invalide : vérifiez l’en-tête Authorization. |
402 | insufficient_balance | Solde insuffisant : rechargez votre compte pour lancer cette tâche. |
404 | unknown_type | Type de tâche inconnu : vérifiez le champ type de votre requête. |
429 | rate_limited | Trop de requêtes : ralentissez la cadence, puis réessayez. |
Notes techniques
Comprendre la comparaison
Une égalité est moins concluante : elle indique uniquement que n a réussi le test pour la base choisie, d’où la classification probable_prime_to_base.
Choisir et valider les entrées
Ce format est essentiel, car les nombres JSON ordinaires ne représentent pas exactement tous les grands entiers.
Interpréter le résultat avec prudence
S’il vaut true, classification vaut probable_prime_to_base, et non prime. Les champs détaillés expliquent le verdict : gcd révèle un facteur commun immédiat, jacobi_symbol vaut -1, 0 ou 1, euler_residue contient la puissance modulaire calculée et expected_residue normalise la valeur de Jacobi dans l’intervalle modulo n. Les requêtes API utilisent le tarif de base publié $0.002 ; le même calcul déterministe convient aussi à une utilisation interactive dans le navigateur.
Questions techniques
Pourquoi n et a sont-ils des chaînes plutôt que des nombres JSON ?
Les chaînes décimales préservent exactement les entiers au-delà de la plage numérique sûre de JavaScript et évitent les arrondis silencieux.
Quel est le coût d’une requête API ?
Le tarif de base est de $0.002 par requête. Une requête évalue une paire candidat-base.