ForHosting KIT · Mathématiques

Factorisation de Pollard p−1

Trouve un facteur d'un nombre composé lorsqu'un de ses premiers p a un p − 1 friable : 1003 avec une borne de 16 se scinde en 17 et 59, car 17 − 1 vaut 16. Si rien n'apparaît, augmentez la borne. Gratuit dans votre navigateur.

Gratuit
Fonctionne dans votre navigateur
Sans inscription
Vos données restent sur votre appareil

Lancer gratuitement Voir l’API

Utilisez-le depuis WebAPIE-mailTelegramApp bientôt

Exemple résolu

Si vous saisissez

N: 1003
Borne: 16

Vous obtenez

Facteur: 17
Cofacteur: 59
Base: 2

La méthode p moins un de Pollard est un algorithme classique de factorisation d'entiers qui trouve un facteur non trivial d'un module composé n lorsqu'au moins un facteur premier p de n a la propriété que p moins un est friable par rapport à une borne B choisie — chaque puissance première dans la factorisation de p moins un est au plus B. Les étudiants en théorie élémentaire des nombres, les concurrents CTF et les apprenants en cryptographie rencontrent cet algorithme en étudiant pourquoi les modules RSA doivent éviter les premiers à totients friables. Cette capacité exécute une recherche déterministe de stade un de Pollard p−1 : elle construit le produit des puissances premières jusqu'à B, élève une petite base à cet exposant modulo n, et renvoie le pgcd de cette puissance moins un avec n lorsque le pgcd est un facteur propre.

Comment Pollard p−1 trouve un facteur à partir d'un p−1 friable

Fixez un entier composé n et une borne de friabilité positive B. L'observation de Pollard est simple : si p est un diviseur premier de n et que chaque puissance première divisant p moins un est au plus B, alors le plus petit commun multiple des entiers de un à B est un multiple de p moins un.

Par le petit théorème de Fermat, toute base a première avec p satisfait a à la puissance p moins un congruente à un modulo p, et donc a élevée à ce grand ppcm est aussi congruente à un modulo p. Calculer la même puissance modulo n et prendre le plus grand commun diviseur du résultat moins un avec n produit souvent p ou un autre facteur non trivial.

En pratique l'implémentation ne construit jamais le ppcm complet explicitement ; elle crible les premiers jusqu'à B et, pour chaque premier q, élève l'accumulateur courant à la plus haute puissance de q ne dépassant pas B, le tout modulo n. Après chaque étape de puissance première elle évalue le pgcd de l'accumulateur moins un avec n. Un pgcd intermédiaire non trivial est renvoyé immédiatement.

Si le pgcd s'effondre à n, un parcours de récupération plus fin sur de plus petits exposants tente d'isoler un seul facteur premier avant d'abandonner cette base. Plusieurs petites bases sont essayées pour que des ordres malchanceux de la base deux ne masquent pas un facteur autrement B-friable. La méthode n'est pas un algorithme de factorisation complète : elle renvoie un facteur non trivial et le cofacteur correspondant.

Qui a besoin de la factorisation première complète peut alimenter chaque pièce composée à un outil de factorisation en premiers ou augmenter B et relancer. Le succès n'est garanti que dans le cadre d'un p−1 friable ; de grands facteurs premiers de p moins un imposent une B plus grande ou un autre algorithme, comme la méthode des courbes elliptiques ou le crible quadratique.

Quand cette méthode de factorisation est utile

Les cours de cryptographie utilisent Pollard p−1 pour montrer pourquoi les premiers à prédécesseurs friables sont dangereux dans la génération de paramètres RSA et Diffie–Hellman ; un outil vivant qui accepte n et B permet à l'instructeur de démontrer une scission en classe sans écrire à la main l'exponentiation modulaire.

Les plateformes CTF et de devoirs ont besoin d'un oracle déterministe qui soit renvoie un facteur documenté pour des semi-premiers classiques tels que mille trois avec borne seize, soit rejette les bornes trop petites pour que les correcteurs puissent noter à la fois les facteurs corrects et les raisonnements d'échec corrects. Les ingénieurs sécurité qui auditent la génération de clés héritée peuvent cribler des modules candidats pour des facteurs à p−1 friable avant qu'ils n'atteignent la production.

Les auteurs de notebooks qui ont déjà une routine générale de factorisation en premiers bénéficient encore d'un point de terminaison p−1 explicite lorsque la leçon porte sur la méthode elle-même plutôt que sur la liste complète des facteurs. Gardez n dans la limite de chiffres, choisissez B assez grand pour couvrir le plus grand facteur premier de p moins un pour un premier p divisant n, et vous obtenez des facteurs reproductibles pour l'enseignement, les write-ups CTF et les audits légers sans déployer une pile complète d'algèbre computationnelle.

Cas d’usage

Hygiène des modules candidats

Criblez les modules candidats RSA ou Diffie–Hellman pour des facteurs à p−1 friable avant le déploiement, sans importer une suite complète de factorisation.

Questions fréquentes

Qu'est-ce que la méthode de factorisation p−1 de Pollard ?

C'est un algorithme de stade un qui calcule une grande puissance friable d'une base modulo n et renvoie gcd(a^M − 1, n). Il trouve un facteur p lorsque p−1 est B-friable pour la borne B choisie.

Quand la méthode échoue-t-elle à trouver un facteur ?

Lorsque n est premier, lorsque chaque facteur premier p de n a un diviseur premier de p−1 plus grand que B, ou lorsque la récupération ne peut isoler un facteur propre.

Renvoie-t-elle la factorisation première complète ?

Non. Elle renvoie un facteur non trivial et le cofacteur n/factor (le plus petit en premier). Factorisez chaque pièce avec un outil de factorisation en premiers si vous avez besoin de toutes les puissances premières.

Quelle borne dois-je choisir ?

Commencez petit et augmentez si aucun facteur n'apparaît. La borne doit couvrir chaque puissance de premier de p − 1 pour au moins un facteur premier p de votre nombre. Tout entier de 2 à 50 000 est accepté.

Combien de chiffres le nombre peut-il avoir ?

Jusqu'à 18 chiffres, écrit comme un entier sans espaces ni séparateurs. Un nombre pair renvoie aussitôt le facteur 2, et un nombre premier ne donne aucun facteur, car il n'y a rien à scinder.

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

POSThttps://api.kit.forhosting.com/numth/pollard-p-minus-one

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/pollard-p-minus-one \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":"1003","bound":16}'

const res = await fetch("https://api.kit.forhosting.com/numth/pollard-p-minus-one", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "n": "1003",
    "bound": 16
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/pollard-p-minus-one",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "n": "1003",
    "bound": 16
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/pollard-p-minus-one", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"n":"1003","bound":16}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"n":"1003","bound":16}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/pollard-p-minus-one", 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": "1003",
  "bound": 16
}

Exemple de réponse

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.pollard_p_minus_one",
  "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

par requête$0.002

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

Si la borne est trop serrée, n est premier, ou chaque facteur résiste à la méthode, la tâche échoue avec invalid_input au lieu d'inventer un facteur. Le chemin gratuit du navigateur et l'API payante partagent le même module BigInt pur, de sorte que les contrôles de devoirs et l'automatisation ne divergent jamais.

Contrat d'entrée, forme de la réponse et modes d'échec

Le champ n est l'entier à factoriser : un entier JavaScript sûr ou une chaîne décimale simple sans virgules, espaces ni notation scientifique, d'au moins deux et au plus dix-huit chiffres décimaux. Exemple : n égal à mille trois et bound égal à seize renvoie le facteur dix-sept et le cofacteur cinquante-neuf car dix-sept moins un égale seize, qui est seize-friable. Si n est pair le facteur deux est renvoyé immédiatement sans recherche complète de stade un. Cet échec est un choix produit intentionnel : un succès silencieux avec facteur un ou n casserait les automatisations qui traitent toute réponse deux-cents comme une scission réelle. Envoyez en POST un objet JSON avec deux champs obligatoires. Le champ bound est la borne de friabilité B, un entier de deux à cinquante mille ; les alias B, b, smoothness_bound et smoothness sont acceptés par commodité. En cas de succès le corps répète n comme chaîne décimale et bound comme entier, puis rapporte factor et cofactor comme chaînes décimales avec le plus petit facteur en premier, la base qui a produit le facteur, et method fixé à la chaîne pollard_p_minus_one. Champs manquants, non-entiers, n inférieur à deux, bound hors de la plage publiée et n de plus de dix-huit chiffres échouent avec invalid_input et ne sont pas facturés. Lorsque le stade un termine toutes les bases sans facteur propre — par exemple n est premier, ou chaque facteur premier p a un diviseur premier de p moins un plus grand que B — le gestionnaire échoue aussi avec invalid_input et un message indiquant que Pollard p−1 n'a trouvé aucun facteur non trivial dans la borne, invitant à augmenter B ou essayer un autre n.

Où une API de facteur p−1 apporte de la valeur

Comme l'implémentation est parse pur de niveau A, chaque appel réussi coûte le prix de base publié $0.002 sans jetons de modèle ni réseau sortant, et la validation échouée ne consomme jamais le solde.

Cas d'intégration

Démonstrations en classe de p−1 friable

Montrez comment une borne B qui couvre p−1 pour un facteur premier d'un semi-premier produit une scission non triviale, avec des exemples classiques comme n=1003 et B=16.

Correcteurs automatiques CTF et devoirs

Notez les exercices de Pollard p−1 avec un oracle déterministe qui renvoie le facteur lorsque B suffit et invalid_input lorsque la borne est trop serrée.

Questions techniques

Quelles entrées l'API exige-t-elle ?

Le champ n (entier ≥ 2, ≤ 18 chiffres) et le champ bound (friabilité B de 2 à 50000). Les alias incluent number/value pour n et B/smoothness_bound pour bound.

Combien coûte la factorisation de Pollard p−1 ?

L'outil navigateur est gratuit. Les requêtes API utilisent le solde prépayé KIT à $0.002 par appel réussi ; l'entrée invalide et les bornes en échec ne sont pas facturées.

Consulter la documentation complète du KIT →

Lancer gratuitement