Test di primalità Pocklington
Dimostra che un numero è primo partendo da una fattorizzazione parziale di n − 1: per 31, i primi 2, 3 e 5 di 30 danno una parte fattorizzata di 30, e poiché 900 è almeno 31, un testimone per primo lo certifica. Gratis nel suo browser.
- Gratis
- Funziona nel suo browser
- Senza registrazione
- I suoi dati restano sul dispositivo
Esegui gratis nel browser
Esempio risolto
- N
- 31
- Fattori
- 2, 3, 5
- N
- 31
- N meno 1
- 30
- F
- 30
- R
- 1
Il criterio di Pocklington–Lehmer trasforma una fattorizzazione parziale di n meno uno in un certificato rigoroso di primalità. A differenza della sola divisione per tentativi o di un’unica congruenza di Fermat, basta fattorizzare abbastanza di n−1 affinché la parte fattorizzata F soddisfi F al quadrato almeno n, più un breve testimone modulare per ogni primo che divide F. Studenti, tutor di crittografia e quaderni di teoria dei numeri usano questo test di primalità di Pocklington per dimostrare primi piccoli e medi senza setacciare fino alla radice quadrata di n. Lei fornisce il candidato n e i primi il cui prodotto è F; il motore verifica il vincolo di dimensione, cerca o convalida basi a e restituisce un certificato strutturato oppure un errore chiaro quando la parte fattorizzata è troppo piccola.
Cosa afferma il criterio di Pocklington–Lehmer
Scriva n meno uno come il prodotto F per R, dove F è completamente fattorizzato nei primi che Lei già conosce e R è il cofattore restante.
Il teorema classico di Pocklington afferma: se F è abbastanza grande da rendere F al quadrato almeno n, e per ogni primo q che divide F esiste una base intera a tale che a elevato a n meno uno è congruente a uno modulo n, e il massimo comun divisore di a elevato a (n meno uno) diviso q, meno uno, con n, vale uno, allora n è primo.
In modo intuitivo, quelle due condizioni modulari costringono l’ordine moltiplicativo di a modulo n a essere multiplo di q per ciascuno di tali primi, quindi l’ordine è multiplo di F; combinato con F maggiore della radice di n, nessun n composto può nascondere un fattore proprio nel modo usuale. È più forte del solo piccolo teorema di Fermat, che controlla un unico residuo di potenza e può essere ingannato da pseudoprimi.
È anche più economico della fattorizzazione completa di n o della divisione fino a sqrt(n) quando Lei già conosce molti fattori di n−1—ad esempio se n è un numero di Proth, una costruzione di primo sicuro, o un intero da compito costruito perché n−1 si fattorizzi con facilità.
Dimostrazioni in aula, demo crittografiche e automazione
I corsi di teoria dei numeri usano un test di primalità di Pocklington affinché gli studenti certifichino primi come trentuno, sessantuno o novantasette dopo aver fattorizzato n−1 a mano, invece di premere solo un pulsante opaco is-prime. Gli autori di librerie che scrivono property test affermano che certified true implica che la propria routine di primalità concorda sullo stesso n, e che un F insufficiente solleva sempre l’errore documentato di parte troppo piccola.
Mantenga n e factors entro i limiti di cifre e lunghezza, preferisca interi in stringa oltre gli interi sicuri JavaScript e tratti certified come il booleano autorevole per «Pocklington ha dimostrato primo». Quando ha solo una sottile fetta di n−1 fattorizzata, fattorizzi di più prima oppure usi un verificatore di primalità generale; questa pagina resta dedicata all’intento di ricerca Pocklington–Lehmer così SEO, esempi e forma della risposta restano mirati.
Casi d'uso
Certificati di primalità per compiti ed esami
Gli studenti fattorizzano n−1, inviano n e i primi di F e ricevono testimoni che dimostrano che n è primo sotto Pocklington–Lehmer quando F è abbastanza grande.
Correttori di concorsi e LMS
Valuti voci di teoria dei numeri con un oracolo di certificato deterministico che rifiuta F troppo piccolo e elenchi di fattori non primi invece di falsi positivi silenziosi.
Domande frequenti
Che cos’è il test di primalità di Pocklington?
Un criterio che certifica che n è primo a partire da una fattorizzazione parziale n−1=F·R con F completamente fattorizzato, F²≥n e testimoni modulari a per ogni primo q che divide F.
Quando la parte fattorizzata è troppo piccola?
Quando F² < n (equivalente a F ≤ R nella scomposizione n−1=F·R).
Quali input devo inviare?
Obbligatori n (≥3) e factors (array di primi con molteplicità il cui prodotto è F).
Se certified è false, n è composto?
No. Significa che non è stato trovato un testimone valido con il F e le bases dati. n può ancora essere primo; provi più basi, una parte fattorizzata maggiore o un altro metodo di primalità.
Posso scegliere io le basi testimoni?
Sì. Indichi numeri interi di almeno 2: una sola base per tutti i primi oppure una per ogni primo distinto, in ordine. Se non ne indica nessuna, il test cerca da solo basi da 2 a 200.
Strumenti correlati
Per sviluppatori — accesso via API
Tutto quello che vedi in questa pagina è disponibile anche via API. Questa sezione è per i team che vogliono integrarlo nei propri sistemi; chi non ne ha bisogno può semplicemente usare lo strumento qui sopra.
Endpoint
Autenticazione con Bearer token: un POST mette in coda l'attività e il risultato arriva via webhook o link firmato.
Chiamala dal tuo 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)Esempio di richiesta
{
"n": 31,
"factors": [
2,
3,
5
]
}Esempio di risposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.pocklington_test",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L'API è asincrona: ricevi subito un task_id e puoi fare polling fino a 1 richiesta al secondo.
Prezzi
Prezzo pubblicato, senza token né crediti. Se l'attività fallisce, non paghi.
Errori
| HTTP | Codice | Significato |
|---|---|---|
401 | unauthorized | Chiave API mancante o non valida: controlla l'header Authorization. |
402 | insufficient_balance | Credito esaurito: ricarica per continuare a eseguire attività. |
404 | unknown_type | Tipo di attività sconosciuto: controlla il campo type della richiesta. |
429 | rate_limited | Troppe richieste in poco tempo: rallenta e riprova tra qualche secondo. |
Note tecniche
La stessa logica pura BigInt alimenta lo strumento gratuito del browser e il percorso API a $0.002 per richiesta riuscita.
Cosa afferma il criterio di Pocklington–Lehmer
Questa capacità implementa esattamente quella checklist: il prodotto dei Suoi factors diventa F, R è (n−1)/F, si impone la soglia F² ≥ n, e ogni primo distinto q di F riceve un testimone a (cercato automaticamente da due in su, o preso dall’elenco opzionale bases). Quando ogni primo passa, la risposta imposta certified e is_prime a true e elenca i testimoni così Lei può ricontrollare l’aritmetica a mano o in un altro sistema.
Contratto di ingresso, errori di dimensione e lettura del certificato
Esempio: n uguale a trentuno e factors uguale a due, tre, cinque perché trenta è due per tre per cinque; allora F è trenta, R è uno e F al quadrato supera ampiamente trentuno. Il campo opzionale bases è un array di interi almeno due—un testimone condiviso per ogni primo, oppure un testimone per primo distinto in ordine ordinato—oppure lo ometta e il motore cerca a da due a duecento. Se il prodotto F non divide n−1, l’attività fallisce perché la fattorizzazione parziale è inconsistente. Se F al quadrato è strettamente minore di n, l’attività fallisce con un messaggio che la parte fattorizzata è troppo piccola—è l’errore duro intenzionale quando non ha fattorizzato abbastanza di n−1 per applicare Pocklington–Lehmer. Invii con POST un corpo JSON con l’intero obbligatorio n (almeno tre) e l’array obbligatorio factors: i fattori primi, con molteplicità, della parte fattorizzata F di n−1. Ogni fattore elencato deve essere primo; le voci composte falliscono con invalid_input affinché un elenco contraffatto non finga un certificato. Le risposte di successo ripetono n, n_minus_1, F, R, F_squared, floor_sqrt_n, i primi distinti, il multinsieme dei fattori e un array witnesses con a per primo, il residuo di potenza, il controllo gcd e i flag ok. Il booleano certified è true solo quando ogni primo ha un testimone valido; is_prime rispecchia certified qui perché un passaggio completo di Pocklington è una prova di primalità, mentre un fallimento nella ricerca del testimone non dimostra da solo la compositeness. Il prezzo è un fisso $0.002 per chiamata riuscita sull’unità item; i fallimenti di validazione non vengono addebitati. Interi grandi possono essere inviati come stringhe decimali entro il limite di cifre pubblicato così JSON non li tronca mai.
Dimostrazioni in aula, demo crittografiche e automazione
Gli strumenti di preparazione ai concorsi generano candidati con n−1 liscio, inviano i fattori noti a questo endpoint e memorizzano i testimoni restituiti come un breve oggetto di prova accanto alla chiave di risposte. Poiché l’implementazione è parse pura di livello A, ogni chiamata riuscita costa il $0.002 pubblicato senza token di modello né rete in uscita; il percorso gratuito del browser esegue la stessa funzione solve.
Casi di integrazione
Controlli in quaderni critto e CAS
Fissi certificati golden di Pocklington per primi fissi nei test unitari senza reimplementare modPow e controlli gcd in ogni linguaggio.
Domande tecniche
Quanto costa il test di primalità di Pocklington?
Lo strumento del browser è gratuito. Le richieste API usano il saldo prepagato KIT a $0.002 per chiamata riuscita; l’input non valido non viene mai addebitato.