Babyschritt-Riesenschritt-Rechner für diskrete Logarithmen
2 hoch 9 lässt bei Division durch 13 den Rest 5, also ist der diskrete Logarithmus von 5 zur Basis 2 modulo 13 gleich 9. Geben Sie Basis, Ziel und Modul ein, prim oder zusammengesetzt, und erhalten Sie den Exponenten. Kostenlos in Ihrem Browser.
- Kostenlos
- Läuft in Ihrem Browser
- Ohne Anmeldung
- Ihre Daten bleiben auf Ihrem Gerät
Im Browser ausführen – kostenlos
Rechenbeispiel
- G
- 2
- H
- 5
- N
- 13
- X
- 9
- Gleichung
- 2^9 ≡ 5 (mod 13)
Dieser Babyschritt-Riesenschritt-Rechner findet einen nichtnegativen Exponenten x, für den g hoch x kongruent zu h modulo n ist. Anders als Löser, die auf Primkörper beschränkt sind, verarbeitet er durch vorherige Reduktion auch zusammengesetzte Moduln und nicht teilerfremde Basen. Das Ergebnis enthält normalisierte Reste und eine lesbare Prüfgleichung. Ist das Ziel vom angegebenen Generator aus nicht erreichbar, liefert die Anfrage einen eindeutigen Fehler statt eines missverständlichen leeren Ergebnisses.
Beschreiben Sie die modulare Gleichung genau
Geben Sie drei ganze Zahlen an: g ist der Generator beziehungsweise die Basis, h das Ziel und n der Modul. Der Rechner sucht ein nichtnegatives x, sodass g^x kongruent zu h modulo n ist. Negative Basen und Ziele sind zulässig und werden auf den üblichen Restbereich von null bis n minus eins normalisiert.
Die Antwort gibt diese Werte wieder, damit Sie auch bei ursprünglich außerhalb des Bereichs liegenden Eingaben die tatsächlich gelöste Gleichung erkennen. Der Modul muss mindestens zwei betragen und darf innerhalb der veröffentlichten Grenze prim oder zusammengesetzt sein. Zuerst wird der Exponent null betrachtet, entsprechend der Konvention, dass g^0 modulo n gleich eins ist.
Ein zu eins kongruentes Ziel ergibt deshalb sofort x gleich null. Eine erfolgreiche Antwort enthält x, die normalisierten Operanden, den Methodennamen und eine gut lesbare Prüfgleichung. Damit eignet sie sich für manuelle Kontrollen ebenso wie für automatisierte Assertions, ohne dass jede Clientanwendung den Anzeigetext neu zusammensetzen muss.
Verstehen Sie Baby- und Riesenschritte
Eine direkte Suche prüft Exponenten nacheinander und kann proportional zum Modul viele modulare Multiplikationen verlangen. Babyschritt-Riesenschritt tauscht Speicher gegen Geschwindigkeit. Das Verfahren wählt eine Breite nahe der Quadratwurzel des Suchraums, speichert aufeinanderfolgende kleine Basispotenzen als Babyschritte und durchläuft das Ziel anschließend in Sprüngen dieser Breite.
Stimmen Reste überein, werden der Riesen- und der Babyschrittindex zum Exponenten kombiniert. Tabellengröße und Sprungzahl liegen damit in der Größenordnung der Quadratwurzel von n. Diese Implementierung ist deterministisch: Sie zieht keine Kandidaten, verwendet keine Zufallsstartwerte, kontaktiert keinen Dienst und liest keine Uhr.
Bei nicht teilerfremden Eingaben kommt zunächst die erweiterte Variante zum Einsatz. Gemeinsame Teiler werden einzeln entfernt, während ein Exponentenversatz und ein Multiplikator fortgeschrieben werden. Macht ein Teiler das Ziel unerreichbar, wird die Gleichung sofort abgelehnt.
Sobald die reduzierte Basis invertierbar ist, startet die Tabellensuche; danach wird der Versatz addiert. Vor der Ausgabe wird der Kandidat unabhängig durch modulare Potenzierung geprüft.
Grenzen und Fälle ohne Lösung
Ein diskreter Logarithmus muss nicht existieren. Die Potenzen von g können nur einen Teil der Reste modulo n durchlaufen und h außerhalb der erzeugten Folge lassen. Fehlerhafte Ganzzahlen, fehlende Felder und ein Modul außerhalb der Grenzen erzeugen dieselbe Fehlerkategorie mit genaueren Meldungen.
Der Rechenaufwand wächst mit der Quadratwurzel des reduzierten Moduls, weil der Algorithmus eine Speichertabelle anlegt. Die Grenze verhindert unerwartet große Belegungen und hält die Laufzeit beschränkt. Verwenden Sie überschaubare Parameter für Lehre, Testvektoren, Rätsel und Diagnose.
Geheimnisse realer kryptografischer Gruppen lassen sich damit nicht gewinnen, weil deren Größen absichtlich weit jenseits dieser Grenze liegen.
Anwendungsfälle
Aufgaben zur modularen Arithmetik prüfen
Prüfen Sie eine Übungsgleichung und erhalten Sie den Exponenten samt lesbarer Kongruenz zum Einsetzen in die Aufgabe.
Deterministische Testvektoren erstellen
Erzeugen Sie bekannte Antworten für modularen Potenzierungscode, auch mit zusammengesetzten Moduln und gemeinsamen Faktoren.
Häufige Fragen
Muss der Modul eine Primzahl sein?
Nein. Die erweiterte Reduktion unterstützt Prim- und zusammengesetzte Moduln, auch wenn g und n häufig einen Faktor teilen.
Welcher Exponent wird ausgegeben?
Der Löser sucht nichtnegative Exponenten, behandelt null ausdrücklich und gibt eine durch BSGS geprüfte Lösung zurück.
Warum ist der Modul begrenzt?
Das Verfahren benötigt Quadratwurzel-Speicher und -Zeit. Die Grenze hält Hashtabelle und Ausführung berechenbar.
Was passiert, wenn kein Exponent existiert?
Die Potenzen der Basis erreichen womöglich nur einen Teil der Reste modulo n, sodass das Ziel unerreichbar bleibt. Dann erhalten Sie einen klaren Hinweis, dass kein Exponent existiert, statt einer leeren oder irreführenden Antwort.
Warum ist das schneller, als Exponenten einzeln auszuprobieren?
Eine direkte Suche braucht unter Umständen so viele Schritte, wie der Modul groß ist. Dieses Verfahren speichert eine Tabelle kleiner Potenzen und springt dann in großen Schritten, beide Teile kosten etwa die Quadratwurzel von n.
Darf ich negative Zahlen eingeben?
Ja, für Basis und Ziel. Negative Werte werden vor der Rechnung in den üblichen Bereich von null bis n minus eins umgerechnet, und das Ergebnis zeigt Ihnen die umgerechneten Werte an.
Verwandte Tools
Für Entwickler — API-Zugang
Alles auf dieser Seite ist auch per API verfügbar. Dieser Abschnitt richtet sich an Teams, die es in ihre eigenen Systeme einbinden möchten; alle anderen nutzen einfach das Tool oben.
Endpunkt
Authentifizierung per Bearer-Token. Ein einziger POST stellt die Aufgabe in die Warteschlange; das Ergebnis erhalten Sie per Webhook oder über einen signierten Link.
Aufruf aus Ihrem Stack
curl -X POST https://api.kit.forhosting.com/numth/baby-step-giant-step \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"g":2,"h":5,"n":13}'const res = await fetch("https://api.kit.forhosting.com/numth/baby-step-giant-step", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"g": 2,
"h": 5,
"n": 13
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/baby-step-giant-step",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"g": 2,
"h": 5,
"n": 13
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/baby-step-giant-step", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"g":2,"h":5,"n":13}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"g":2,"h":5,"n":13}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/baby-step-giant-step", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Beispiel-Anfrage
{
"g": 2,
"h": 5,
"n": 13
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.baby_step_giant_step",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}Die API arbeitet asynchron: Sie erhalten sofort eine task_id. Polling ist mit 1 Anfrage pro Sekunde erlaubt.
Preis
Der Preis steht auf der Seite – keine Tokens, keine Credits. Fehlgeschlagene Aufgaben werden nicht berechnet.
Limits
max_n | 1000000000000 |
Fehler
| HTTP | Code | Bedeutung |
|---|---|---|
401 | unauthorized | Der API-Schlüssel fehlt oder ist ungültig – prüfen Sie den Authorization-Header (Bearer). |
402 | insufficient_balance | Ihr Guthaben reicht für diese Aufgabe nicht aus – Aufladungen verfallen nicht. |
404 | unknown_type | Unbekannter Aufgabentyp – prüfen Sie das Feld „type“ gegen den Katalog. |
429 | rate_limited | Zu viele Anfragen – warten Sie kurz; Polling ist mit 1 Anfrage pro Sekunde erlaubt. |
Technische Hinweise
Beschreiben Sie die modulare Gleichung genau
Eingaben dürfen JSON-Ganzzahlen oder Ziffernketten sein; Letzteres hilft, wenn eine Clientsprache einen Wert nicht bequem darstellen kann.
Behandeln Sie Grenzen, Fehler und API-Nutzung
Dann löst diese Fähigkeit einen invalid_input-Fehler aus, dessen Meldung erklärt, dass kein Exponent existiert. Dieses Verhalten ist beabsichtigt und nützlich in Abläufen, in denen das Fehlen einer Lösung den nächsten Schritt stoppen soll: Sie können den Standardcode behandeln, ohne nach Nullfeldern zu suchen. Im Browser läuft derselbe reine Löser wie über die API. Automatisierte Elemente kosten jeweils $0.002; netzabhängige Arithmetik oder zufällige Ergebnisse gibt es nicht.
Integrationsbeispiele
Unerreichbare Zielwerte erkennen
Stoppen Sie mit dem Standardfehler invalid_input einen Ablauf, wenn das Ziel nicht zur von g erzeugten Potenzfolge gehört.
Technische Fragen
Was geschieht, wenn kein diskreter Logarithmus existiert?
Der Aufruf schlägt mit invalid_input und einer Meldung fehl, dass für die angegebenen Werte kein Exponent existiert.
Was kostet ein API-Aufruf?
Jedes Element kostet $0.002. Das Browserwerkzeug nutzt dieselbe reine Bibliothek für interaktive Rechnungen.