Test di primalità di Proth con testimone
Dimostra che un numero di Proth k × 2^n + 1 è primo con un solo testimone: con k pari a 3 e n pari a 2 si ottiene 13, e il testimone 2 alla 6 lascia 12, cioè −1 modulo 13. Gratis nel suo browser.
- Gratis
- Funziona nel suo browser
- Senza registrazione
- I suoi dati restano sul dispositivo
Esegui gratis nel browser
Esempio risolto
- K
- 3
- N
- 2
- Testimone
- 2
- Numero
- 13
- Esponente
- 6
- Resto
- 12
- Verdetto
- prime
Il test di primalità di Proth verifica un numero scritto come k × 2^n + 1 applicando il teorema di Proth al testimone fornito da Lei. Prima controlla che k sia positivo e dispari, che n sia positivo e che k sia minore di 2^n. Poi calcola esattamente la potenza modulare richiesta. Una congruenza valida dimostra che il numero di Proth è primo; un testimone negativo resta inconcludente, salvo che riveli un fattore.
Inserisca un vero numero di Proth e un testimone
Un numero di Proth ha esattamente la forma N = k × 2^n + 1, dove k è un intero positivo dispari, n è un intero positivo e k è strettamente minore di 2^n. Tutte queste condizioni sono essenziali. Il calcolatore accetta k e il testimone come testo decimale, così i valori grandi rimangono esatti e non subiscono arrotondamenti in virgola mobile.
Inserisca n come intero da 1 a 10,000. Lo strumento costruisce N anziché richiederlo separatamente, impedendo discrepanze tra il numero dichiarato e i parametri che lo definiscono. Verifica inoltre che il testimone sia strettamente compreso tra 1 e N.
Un k pari, un valore non positivo oppure k maggiore o uguale a 2^n fanno rifiutare l’input come non appartenente alla forma di Proth, senza applicare un teorema quando le sue ipotesi non valgono. Il numero, l’esponente, il testimone e il residuo vengono restituiti come stringhe decimali quando necessario, affinché Lei possa controllare il calcolo e copiarlo in un altro strumento di aritmetica esatta.
Comprenda che cosa dimostra la congruenza
Per un numero di Proth valido N, il teorema afferma che N è primo se esiste un intero a per cui a^((N−1)/2) è congruo a −1 modulo N. Il testimone fornito rappresenta a e il calcolatore valuta la potenza modulare mediante quadratura ripetuta, senza costruire prima l’enorme potenza ordinaria. La risposta comprende l’esponente esatto (N−1)/2, così Lei può riprodurre autonomamente la congruenza.
L’algoritmo usa soltanto operazioni intere, non sceglie testimoni casuali e non consulta tabelle o servizi remoti. Pertanto lo stesso input restituisce sempre il medesimo risultato e rende visibili tutti i valori importanti impiegati dal teorema.
Interpreti correttamente un testimone negativo
Un testimone che non produce −1 non dimostra da solo che il numero sia composto. Significa soltanto che quello specifico testimone non soddisfa la condizione sufficiente del teorema di Proth. Lei può quindi provare un altro testimone scelto matematicamente oppure usare un diverso metodo deterministico di primalità.
Esiste un’eccezione utile: prima di interpretare la congruenza, il calcolatore determina il massimo comune divisore tra il testimone e N. Questa distinzione impedisce l’errore comune di trasformare un teorema unidirezionale in un test bidirezionale non valido.
Casi d'uso
Verificare un candidato di una ricerca
Controlli una coppia k e n generata con un testimone scelto prima di registrare il candidato come primo dimostrato.
Insegnare il teorema di Proth
Mostri l’esponente esatto, il residuo modulare e la differenza fra una prova e un testimone inconcludente.
Aggiungere un controllo deterministico
Convalidi le condizioni di Proth e instradi risultati primi, composti o inconcludenti senza aritmetica in virgola mobile.
Domande frequenti
Quali condizioni definiscono un numero di Proth?
Deve essere uguale a k × 2^n + 1, con k positivo e dispari, n positivo e k < 2^n.
Un testimone negativo dimostra che il numero è composto?
No. Di norma il risultato è inconcludente. Viene dichiarato composto solo se il testimone rivela un fattore comune non banale.
Perché k e il testimone sono inseriti come stringhe?
Le stringhe decimali conservano senza arrotondamento interi oltre l’intervallo numerico sicuro di JavaScript.
Un risultato positivo è probabilistico?
No. Dopo la convalida delle condizioni di Proth, la congruenza richiesta costituisce una prova di primalità.
I testimoni vengono scelti automaticamente?
No. Lei fornisce il testimone e la capacità verifica quel valore esatto in modo deterministico.
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/proth-test \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"k":"3","n":3,"witness":"3"}'const res = await fetch("https://api.kit.forhosting.com/numth/proth-test", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"k": "3",
"n": 3,
"witness": "3"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/proth-test",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"k": "3",
"n": 3,
"witness": "3"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/proth-test", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"k":"3","n":3,"witness":"3"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"k":"3","n":3,"witness":"3"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/proth-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
{
"k": "3",
"n": 3,
"witness": "3"
}Esempio di risposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.proth_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.
Limiti
max_n | 10000 |
max_decimal_digits | 3011 |
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
Comprenda che cosa dimostra la congruenza
Nell’output, `residue` è il minimo residuo non negativo e `passes_test` è true esattamente quando coincide con N−1, cioè la rappresentazione modulare di −1. In tal caso `prime_proven` è true e il verdetto è `prime`: con le condizioni di Proth già verificate, questo costituisce un certificato deterministico, non una stima di probabile primalità.
Interpreti correttamente un testimone negativo
Per questo il calcolatore restituisce `inconclusive`, non `composite`, quando il residuo è diverso e il testimone è coprimo con N. Se tale valore è un fattore proprio, il risultato è definitivamente `composite` e viene restituito il fattore. È utile anche nei flussi automatizzati: accetti `prime` come prova, respinga `composite` quando emerge un fattore e invii `inconclusive` a un altro test senza considerarlo silenziosamente un fallimento definitivo.
Domande tecniche
Quanto costa una richiesta API?
Ogni richiesta API costa $0.002. Il calcolo può anche essere eseguito gratuitamente nel browser.