Test di primalità Solovay-Strassen con una base scelta
Con 13 e base 2 entrambi i resti valgono 12, quindi 13 supera il test ed è probabile primo per la base 2. Se i resti non coincidessero, il numero risulterebbe certamente composto. Gratis nel Suo browser.
- Gratis
- Funziona nel suo browser
- Senza registrazione
- I suoi dati restano sul dispositivo
Esegui gratis nel browser
Esempio risolto
- N
- 13
- Primo testo
- 2
- Gcd
- 1
- Simbolo di Jacobi
- -1
- Residuo di Eulero
- 12
- Residuo atteso
- 12
Il test di primalità di Solovay-Strassen verifica se un intero dispari si comporta come primo rispetto a una base scelta da Lei. Calcola il simbolo di Jacobi della base modulo il candidato, eleva la base a metà del candidato meno uno e confronta i due valori modulo il candidato. Il risultato individua un testimone certo di compositezza oppure segnala che il numero è probabilmente primo rispetto a quella base. Gli input sono stringhe decimali, così gli interi grandi restano esatti e non subiscono arrotondamenti in virgola mobile.
Significato del confronto
Per un primo dispari n e qualsiasi base a non divisibile per n, il criterio di Eulero stabilisce che a elevata a (n - 1) / 2 è congruente modulo n al simbolo di Legendre di a. Il simbolo di Jacobi estende il calcolo ai candidati composti dispari, rendendolo economico senza conoscere la fattorizzazione di n. Solovay-Strassen confronta la potenza modulare con il simbolo di Jacobi rappresentato come residuo: 1 rimane 1, mentre -1 diventa n - 1.
Una differenza dimostra matematicamente che n è composto. Una base valida diversa può smascherare un composto che aveva superato il primo confronto. La risposta include entrambi i residui, il valore di Jacobi e il massimo comune divisore, permettendoLe di verificare la decisione invece di ricevere un valore booleano privo di spiegazione.
Scelta e convalida degli input
Fornisca n e a come stringhe decimali senza segno. Il candidato n deve essere dispari e almeno pari a 3; valori pari o inferiori generano un errore di input non valido perché non appartengono al dominio dichiarato. La base deve soddisfare 1 < a < n.
Non occorre verificarne prima la coprimalità: la capacità calcola gcd(a, n) e un fattore comune non banale classifica subito il candidato come composto. Ogni input è limitato a 1,000 cifre decimali, imponendo un confine computazionale chiaro. Segni, spazi, punti decimali, notazione esponenziale e zeri iniziali vengono rifiutati per evitare interpretazioni ambigue.
Se sceglie manualmente le basi, ne utilizzi diverse per ottenere evidenze più solide. La capacità non sceglie una base casuale: ogni esecuzione rimane riproducibile e consente di registrare esattamente il testimone verificato.
Lettura responsabile del risultato
Il campo passes indica se l’esatta congruenza di Solovay-Strassen vale per la coppia fornita. Se è false, classification è composite e la base certifica che il candidato non può essere primo. Ripeta il test con basi selezionate indipendentemente quando Solovay-Strassen è richiesto da un esercizio o protocollo, considerando ogni esito positivo come ulteriore evidenza probabilistica e non come prova.
Nei nuovi sistemi sensibili alla sicurezza utilizzi una procedura moderna di verifica della primalità, specificata con cura, con un numero adeguato di iterazioni e casualità sottoposta a revisione, anziché affidarsi a una singola base manuale.
Casi d'uso
Verificare un testimone da manuale
Riproduca un esercizio di Solovay-Strassen con il candidato e la base esatti indicati nel testo.
Esaminare il comportamento degli pseudoprimi
Confronti un candidato composto che supera il test con una base e fallisce con un’altra, conservando tutti i valori intermedi.
Creare uno screening riproducibile
Registri risultati deterministici a base singola prima di applicare altre basi o una procedura di primalità più forte.
Domande frequenti
Un esito positivo dimostra che n è primo?
No. Significa soltanto che n è probabilmente primo rispetto alla base fornita; un’altra base può dimostrare che è composto.
Perché n deve essere dispari e almeno pari a 3?
Il confronto con il simbolo di Jacobi usato qui è definito per candidati dispari almeno pari a 3.
Cosa accade quando a e n condividono un fattore?
Il valore gcd restituito espone il fattore comune e il test classifica n come composto senza considerare superato il confronto di Jacobi.
La capacità sceglie una base casuale?
No. Lei fornisce la base, rendendo il calcolo deterministico e riproducibile.
Quanto possono essere grandi i numeri nel test di Solovay-Strassen?
Ogni numero può avere fino a 1.000 cifre decimali. Vengono trattati esattamente come li scrive, senza arrotondamenti, così un candidato enorme riceve lo stesso confronto esatto di uno piccolo.
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/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)Esempio di richiesta
{
"n": "561",
"a": "2"
}Esempio di risposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.solovay_strassen_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_digits | 1000 |
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
Significato del confronto
Una corrispondenza è più debole: indica soltanto che n ha superato il controllo per la base scelta, quindi la classificazione è prudentemente probable_prime_to_base.
Scelta e convalida degli input
Le stringhe sono importanti perché i normali numeri JSON non rappresentano esattamente ogni intero grande.
Lettura responsabile del risultato
Se è true, classification è probable_prime_to_base, non prime. I campi dettagliati spiegano l’esito: gcd mostra un fattore comune immediato, jacobi_symbol vale -1, 0 o 1, euler_residue è la potenza modulare calcolata ed expected_residue normalizza il valore di Jacobi nell’intervallo modulo n. Le richieste API utilizzano il prezzo base pubblicato $0.002; lo stesso calcolo deterministico può essere usato anche interattivamente nel browser.
Domande tecniche
Perché n e a sono stringhe anziché numeri JSON?
Le stringhe decimali conservano esattamente gli interi oltre l’intervallo numerico sicuro di JavaScript ed evitano arrotondamenti silenziosi.
Quanto costa una richiesta API?
Il costo base è $0.002 per richiesta. Ogni richiesta valuta una coppia candidato-base.