Test de primalité Pocklington
Prouve qu'un nombre est premier à partir d'une factorisation partielle de n − 1 : pour 31, les premiers 2, 3 et 5 de 30 donnent une partie factorisée de 30, et comme 900 dépasse 31, un témoin par premier le certifie. Gratuit dans votre navigateur.
- Gratuit
- Fonctionne dans votre navigateur
- Sans inscription
- Vos données restent sur votre appareil
Lancer gratuitement
Exemple résolu
- N
- 31
- Facteurs
- 2, 3, 5
- N
- 31
- N moins 1
- 30
- F
- 30
- R
- 1
Le critère de Pocklington–Lehmer transforme une factorisation partielle de n moins un en un certificat rigoureux de primalité. Contrairement à la seule division d’essai ou à une unique congruence de Fermat, il suffit de factoriser assez de n−1 pour que la partie factorisée F vérifie F au carré au moins n, plus un court témoin modulaire pour chaque premier divisant F. Étudiants, tuteurs en cryptographie et carnets de théorie des nombres utilisent ce test de primalité de Pocklington pour prouver des premiers petits et moyens sans cribler jusqu’à la racine carrée de n. Vous fournissez le candidat n et les premiers dont le produit vaut F ; le moteur vérifie la borne de taille, cherche ou valide des bases a, et renvoie un certificat structuré ou une erreur claire lorsque la partie factorisée est trop petite.
Ce qu’affirme le critère de Pocklington–Lehmer
Écrivez n moins un comme le produit F fois R, où F est complètement factorisé en premiers que vous connaissez déjà et R est le cofacteur restant.
Le théorème classique de Pocklington dit : si F est assez grand pour que F au carré soit au moins n, et pour tout premier q divisant F il existe une base entière a telle que a élevé à n moins un est congruent à un modulo n, et le plus grand commun diviseur de a élevé à (n moins un) divisé par q, moins un, avec n, vaut un, alors n est premier.
Intuitivement, ces deux conditions modulaires forcent l’ordre multiplicatif de a modulo n à être un multiple de q pour chacun de ces premiers, donc l’ordre est un multiple de F ; combiné à F plus grand que la racine de n, aucun n composé ne peut cacher un facteur propre de la façon habituelle. C’est plus fort que le petit théorème de Fermat seul, qui ne contrôle qu’un seul résidu de puissance et peut être trompé par des pseudopremiers.
C’est aussi plus économique qu’une factorisation complète de n ou une division jusqu’à sqrt(n) lorsque vous connaissez déjà beaucoup de facteurs de n−1—par exemple si n est un nombre de Proth, une construction de premier sûr, ou un entier d’exercice conçu pour que n−1 se factorise facilement.
Preuves en cours, démos crypto et automatisation
Les cours de théorie des nombres utilisent un test de primalité de Pocklington pour que les apprenants certifient des premiers comme trente et un, soixante et un ou quatre-vingt-dix-sept après avoir factorisé n−1 à la main, au lieu de se contenter d’un bouton opaque is-prime. Les outils de préparation aux concours génèrent des candidats à n−1 lisse, envoient les facteurs connus à ce point d’accès et stockent les témoins renvoyés comme un court objet de preuve à côté du corrigé.
Les auteurs de bibliothèques qui écrivent des property tests affirment que certified true implique que leur propre routine de primalité s’accorde sur le même n, et qu’un F insuffisant lève toujours l’erreur documentée de partie trop petite. Gardez n et factors dans les limites de chiffres et de longueur, préférez des entiers en chaîne au-delà des entiers sûrs JavaScript, et traitez certified comme le booléen d’autorité pour « Pocklington a prouvé premier ».
Lorsque vous n’avez qu’une fine tranche de n−1 factorisée, factorisez davantage d’abord ou utilisez un vérificateur de primalité général ; cette page reste dédiée à l’intention de recherche Pocklington–Lehmer afin que le SEO, les exemples et la forme de réponse restent focalisés.
Cas d’usage
Certificats de primalité pour devoirs et examens
Les étudiants factorisent n−1, envoient n et les premiers de F, et reçoivent des témoins prouvant que n est premier sous Pocklington–Lehmer lorsque F est assez grand.
Correcteurs de concours et LMS
Notez des items de théorie des nombres avec un oracle de certificat déterministe qui rejette un F trop petit et des listes de facteurs non premiers au lieu de faux positifs silencieux.
Questions fréquentes
Qu’est-ce que le test de primalité de Pocklington ?
Un critère qui certifie que n est premier à partir d’une factorisation partielle n−1=F·R avec F totalement factorisé, F²≥n, et des témoins modulaires a pour chaque premier q divisant F.
Quand la partie factorisée est-elle trop petite ?
Lorsque F² < n (équivalent à F ≤ R pour la décomposition n−1=F·R).
Quelles entrées dois-je envoyer ?
Obligatoires n (≥3) et factors (tableau de premiers avec multiplicité dont le produit est F).
Si certified est false, n est-il composé ?
Non. Cela signifie qu’aucun témoin valide n’a été trouvé avec le F et les bases donnés. n peut encore être premier ; essayez plus de bases, une plus grande partie factorisée, ou une autre méthode de primalité.
Puis-je choisir moi-même les bases témoins ?
Oui. Indiquez des entiers d'au moins 2 : une seule base pour tous les premiers ou une par premier distinct, dans l'ordre. Si vous n'en donnez aucune, le test cherche lui-même des bases de 2 à 200.
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/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)Exemple de requête
{
"n": 31,
"factors": [
2,
3,
5
]
}Exemple de réponse
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.pocklington_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.
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
La même logique pure BigInt alimente l’outil gratuit du navigateur et le chemin API à $0.002 par requête réussie.
Ce qu’affirme le critère de Pocklington–Lehmer
Cette capacité applique exactement cette liste de contrôle : le produit de vos factors devient F, R vaut (n−1)/F, la barrière F² ≥ n est imposée, et chaque premier distinct q de F reçoit un témoin a (recherché automatiquement à partir de deux, ou pris dans votre liste optionnelle bases). Lorsque tous les premiers passent, la réponse met certified et is_prime à true et liste les témoins pour que vous puissiez refaire l’arithmétique à la main ou dans un autre système.
Contrat d’entrée, erreurs de taille et lecture du certificat
Exemple : n égal à trente et un et factors égal à deux, trois, cinq car trente égale deux fois trois fois cinq ; alors F vaut trente, R vaut un, et F au carré dépasse largement trente et un. Le champ optionnel bases est un tableau d’entiers au moins deux—un témoin partagé pour tous les premiers, ou un témoin par premier distinct en ordre trié—ou omettez-le et le moteur cherche a de deux à deux cents. Si le produit F ne divise pas n−1, la tâche échoue car la factorisation partielle est inconsistante. Si F au carré est strictement inférieur à n, la tâche échoue avec un message indiquant que la partie factorisée est trop petite—c’est l’erreur dure intentionnelle lorsque vous n’avez pas assez factorisé n−1 pour appliquer Pocklington–Lehmer. Envoyez en POST un corps JSON avec l’entier obligatoire n (au moins trois) et le tableau obligatoire factors : les facteurs premiers, avec multiplicité, de la partie factorisée F de n−1. Chaque facteur listé doit être premier ; les entrées composées échouent avec invalid_input pour qu’une liste forgée ne prétende pas être un certificat. Les réponses réussies répètent n, n_minus_1, F, R, F_squared, floor_sqrt_n, les premiers distincts, le multiensemble de facteurs et un tableau witnesses avec a par premier, le résidu de puissance, le contrôle gcd et les drapeaux ok. Le booléen certified n’est true que lorsque chaque premier a un témoin valide ; is_prime reflète certified ici car un passage complet de Pocklington est une preuve de primalité, alors qu’un échec de recherche de témoin ne prouve pas à lui seul la compositeness. Le tarif est un forfait $0.002 par appel réussi sur l’unité item ; les échecs de validation ne sont pas facturés. Les grands entiers peuvent être envoyés comme chaînes décimales dans la limite de chiffres publiée pour que JSON ne les tronque jamais.
Preuves en cours, démos crypto et automatisation
Comme l’implémentation est pure parse de niveau A, chaque appel réussi coûte le $0.002 publié sans jetons de modèle ni réseau sortant ; le chemin gratuit du navigateur exécute la même fonction solve.
Cas d'intégration
Contrôles dans carnets crypto et CAS
Figez des certificats golden de Pocklington pour des premiers fixes dans des tests unitaires sans réimplémenter modPow et les contrôles gcd dans chaque langage.
Questions techniques
Combien coûte le test de primalité de Pocklington ?
L’outil navigateur est gratuit. Les requêtes API utilisent le solde prépayé KIT à $0.002 par appel réussi ; une entrée invalide n’est jamais facturée.