Risolutore logaritmo discreto
Chiedendo quale potenza di 2 dà 5 modulo 13 ottiene 9, perché 2^9 ≡ 5 (mod 13). Inserisca una base, un obiettivo e un modulo primo per trovare il più piccolo esponente, con un'uguaglianza da verificare. Gratis nel suo browser.
- Gratis
- Funziona nel suo browser
- Senza registrazione
- I suoi dati restano sul dispositivo
Esegui gratis nel browser
Esempio risolto
- G
- 2
- H
- 5
- Potenza (W)
- 13
- X
- 9
- Equazione
- 2^9 ≡ 5 (mod 13)
Il problema del logaritmo discreto chiede un intero x tale che una data base g elevata a x sia congruente a un obiettivo h modulo un primo p. È alla base dello scambio di chiavi Diffie–Hellman, della cifratura ElGamal e di molti esercizi da manuale di crittografia algebrica. Questa capacità implementa il classico algoritmo baby-step giant-step: una ricerca deterministica in tempo radice quadrata che o recupera il più piccolo esponente non negativo o dimostra che h non è una potenza di g nel gruppo moltiplicativo modulo p.
Cosa chiede il logaritmo discreto
Dati gli interi g, h e un primo p, il logaritmo discreto di h in base g modulo p è un qualsiasi intero x che soddisfa g elevato a x congruente a h modulo p. Quando una soluzione esiste, il più piccolo rappresentante non negativo nell'intervallo da zero a p meno due è unico una volta fissato quell'intervallo, ed è il valore che questo strumento restituisce.
A differenza degli ordinari logaritmi reali, non esiste una formula elementare in forma chiusa che funzioni per primi arbitrari; la difficoltà di recuperare x per primi grandi scelti con cura è esattamente il motivo per cui la crittografia a logaritmo discreto è utile. Nell'insegnamento e negli esperimenti a piccoli parametri, tuttavia, serve comunque un risolutore corretto e ispezionabile: uno che valida l'ipotesi di primalità, riduce gli input nel sistema di residui canonico, cerca sistematicamente e o stampa un esponente verificabile o dichiara chiaramente che nessuna soluzione esiste.
Come baby-step giant-step trova x
Baby-step giant-step riscrive l'esponente incognito come x uguale a i per m più j, dove m è all'incirca la radice quadrata dell'ordine del gruppo p meno uno, ed entrambi i e j vanno da zero fino a m. L'algoritmo prima memorizza ogni valore baby g elevato a j modulo p in una mappa hash indicizzata per residuo, poi cammina a passi giant moltiplicando ripetutamente l'obiettivo per l'inverso modulare di g elevato a m, cercando ogni residuo intermedio nella mappa. Una corrispondenza fornisce sia i sia j e quindi x.
Basi e obiettivi fuori da zero fino a p meno uno vengono ridotti modulo p, e la risposta restituisce i g, h e p ridotti così i chiamanti possono verificare l'istanza esatta che è stata risolta.
Input, limiti, prezzo e quando non c'è soluzione
I campi obbligatori sono g (base), h (residuo obiettivo) e p (modulo primo). Le stringhe di cifre sono accettate per interi grandi entro il limite del modulo. Se h non è nel sottogruppo ciclico generato da g modulo p—per esempio quando g genera solo un sottogruppo proprio e h giace al di fuori di esso—il risolutore restituisce solved false con un esponente null e un messaggio esplicativo invece di fabbricare un x sbagliato.
Quell'esito è un calcolo riuscito, non un errore del client, perché l'input era ben formato e la risposta matematica è che nessun logaritmo esiste. Gli errori del client coprono campi mancanti, non interi, moduli fuori dall'intervallo consentito e p composto. Lo strumento nel browser esegue la libreria identica gratuitamente senza un account.
Usi il risultato per verificare i compiti, generare test a risposta nota per librerie crittografiche, o esplorare l'appartenenza a un sottogruppo prima di scalare i parametri in una vera progettazione di protocollo.
Casi d'uso
Verifica di compiti ed esami
Studenti e docenti verificano esercizi di logaritmo discreto come 2^x ≡ 5 (mod 13) e ricevono sia l'esponente sia una congruenza stampabile per il solutore.
Test a risposta nota per codice crittografico
Gli autori di librerie inseriscono piccole istanze di campo primo nella CI così che l'esponenziazione modulare e le funzioni di inverso restino coerenti con un riferimento BSGS indipendente.
Esperimenti di appartenenza a sottogruppi
I ricercatori provano basi e obiettivi candidati modulo un piccolo primo per vedere se h giace nel sottogruppo generato da g prima di passare a parametri di dimensione produttiva.
Domande frequenti
Quale algoritmo usate?
Baby-step giant-step (Shanks). Trova il più piccolo x non negativo con g^x ≡ h (mod p) in tempo e memoria all'incirca O(√p), dopo un controllo di primalità deterministico su p.
E se nessun esponente esiste?
Ottiene solved: false e x: null con un breve messaggio. È un esito matematico valido (h non è una potenza di g mod p), non un errore di fatturazione o validazione.
Come risolvo 2^x ≡ 5 (mod 13)?
Inserisca 2 come base, 5 come obiettivo e 13 come modulo primo. La risposta è 9: elevando 2 alla nona potenza e dividendo per 13 resta 5, e nessun esponente più piccolo ci riesce.
Cosa succede se il modulo non è primo?
La ricerca non parte. Il modulo viene prima controllato e, se è composto, viene rifiutato con un messaggio chiaro invece di produrre un esponente privo di senso.
Quanto può essere grande il modulo primo?
Fino a circa mille miliardi. Basta per compiti, dimostrazioni di protocolli e piccoli esperimenti con risposta rapida; non è pensato per i primi enormi che proteggono la cifratura reale.
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/discrete-log \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"g":2,"h":5,"p":13}'const res = await fetch("https://api.kit.forhosting.com/numth/discrete-log", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"g": 2,
"h": 5,
"p": 13
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/discrete-log",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"g": 2,
"h": 5,
"p": 13
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/discrete-log", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"g":2,"h":5,"p":13}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"g":2,"h":5,"p":13}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/discrete-log", 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
{
"g": 2,
"h": 5,
"p": 13
}Esempio di risposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.discrete_log",
"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_p | 1000000000007 |
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
Lei fornisce tre interi—g, h e un modulo primo p—e riceve una risposta JSON strutturata con la soluzione, i residui ridotti e un'equazione di verifica quando esiste una soluzione.
Cosa chiede il logaritmo discreto
Questo è il contratto di questo endpoint: pura aritmetica modulare, nessuna euristica e nessuna chiamata di rete.
Come baby-step giant-step trova x
Il metodo usa dell'ordine di radice quadrata di p moltiplicazioni e voci di mappa, ed è per questo che questa capacità limita il modulo primo vicino a mille miliardi: abbastanza grande per compiti, illustrazioni di protocolli e stress test di piccoli sottogruppi, eppure limitato affinché memoria e latenza restino prevedibili su un Worker. Prima di cercare, il risolutore esegue un test di primalità deterministico di Miller–Rabin su p; se p è composto, la chiamata fallisce con invalid_input anziché inventare un logaritmo in una struttura che non è il gruppo moltiplicativo del campo primo.
Input, limiti, prezzo e quando non c'è soluzione
Il prezzo per l'API è un forfait di $0.002 per richiesta riuscita nell'unità elemento; la validazione fallita non viene addebitata.
Domande tecniche
Come risolvo un logaritmo discreto con questa API?
Invii in POST gli interi g, h e il primo p all'endpoint del logaritmo discreto (o usi il modulo gratuito del browser). La risposta include solved, l'esponente x quando esiste, i residui ridotti e un'equazione di verifica.
Cosa succede se p non è primo?
La richiesta fallisce con invalid_input. Questo strumento definisce il logaritmo discreto nel gruppo moltiplicativo di un campo primo e non funzionerà in silenzio modulo un composto.
Quanto costa l'API?
Lo strumento nel browser è gratuito. L'API addebita $0.002 per richiesta riuscita dal suo saldo prepagato del KIT; l'input non valido non viene addebitato. Non è richiesto alcun abbonamento.