Cipolla-Quadratwurzel modular
Der Cipolla-Algorithmus liefert die Quadratwurzel selbst modulo einer ungeraden Primzahl, nicht nur ein Ja oder Nein: Für 2 modulo 7 erhalten Sie 3 und 4, denn 3 zum Quadrat ist 9, also 2 modulo 7. 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
- A
- 2
- Leistung (W)
- 7
- A modulo
- 2
- Wurzeln
- 3, 4
- Wurzel
- 3
- Omega
- 0
Der Algorithmus von Cipolla ist ein klassisches zahlentheoretisches Verfahren zur Berechnung von Quadratwurzeln modulo einer ungeraden Primzahl. Gegeben ein Ganzzahl a und eine ungerade Primzahl p liefert er eine Ganzzahl x, sodass x zum Quadrat kongruent zu a modulo p ist, sofern a ein quadratischer Rest ist. Kryptografie-Hausaufgaben, Wettbewerbsprogrammierung und Tutorials zur modularen Arithmetik brauchen oft die explizite Wurzel — nicht nur den Ja-oder-Nein-Residuen-Test des Legendre-Symbols.
Was eine modulare Quadratwurzel ist und wann Cipolla gilt
In der modularen Arithmetik fragt die Kongruenz x zum Quadrat kongruent zu a modulo p nach einer Ganzzahl x, deren Quadrat in derselben Restklasse wie a landet. Ist p eine ungerade Primzahl, ist die theoretische Antwort klar: entweder ist a durch p teilbar und die einzige Wurzel ist null, oder genau die Hälfte der nicht nullen Klassen sind quadratische Reste und jeder Rest hat genau zwei Wurzeln r und p minus r. Das Legendre-Symbol sagt, in welchem Fall Sie sich befinden, konstruiert r aber nicht.
Cipollas Algorithmus schließt diese Lücke, indem er in einer sorgfältig gewählten quadratischen Erweiterung des Körpers mit p Elementen arbeitet. Man wählt eine Hilfszahl omega so, dass omega zum Quadrat minus a ein quadratischer Nichtrest modulo p ist; dann fällt das Element omega plus eine formale Quadratwurzel dieses Nichtrests, erhoben zur Potenz (p plus eins) geteilt durch zwei, in den Grundkörper zurück und ist eine Quadratwurzel von a. Sie scheitert auch, wenn p zusammengesetzt oder gerade ist, weil der klassische Algorithmus und Eulers Kriterium einen ungeraden Primmodul voraussetzen.
Gegenüber Tonelli–Shanks ist Cipolla für Lehrdemos und mittelgroße Primzahlen oft kürzer zu implementieren und braucht keine Faktorisierung von p minus eins. Diese Fähigkeit richtet sich an Studierende, Lehrkräfte und Skripte, die einen transparenten Cipolla-Pfad mit stabil geordneten Wurzeln und dokumentiertem Fehlervertrag wollen.
Wo modulare Cipolla-Quadratwurzeln ihren Nutzen zeigen
Unterricht zu quadratischen Resten kann zeigen, dass Residuosität allein nicht genügt, und dann diesen Endpunkt aufrufen, um echte Wurzeln vieler Reste zu zeigen, ohne Erweiterungskörper-Potenzen von Hand zu rechnen. Wettbewerbsplattformen und LMS-Korrektoren brauchen ein deterministisches Orakel, das Nichtreste und zusammengesetzte Moduln ablehnt statt leerer Arrays, die fehlerhafte Clients als Erfolg werten könnten. Kryptografie-Notizen zu Rabin-Verschlüsselung oder Punktdekompression über Primkörpern wollen oft einen Cipolla-Durchgang neben Tonelli–Shanks; ein geteiltes reines Modul hält Browser-Demos und Serverprüfungen identisch.
Halten Sie p in der veröffentlichten Primgrenze, pinnen Sie das Array geordneter Wurzeln in Tests, und Sie erhalten reproduzierbare modulare Quadratwurzeln für Lehre, Automatisierung und Edge-Worker ohne einen vollen Computer-Algebra-Stack.
Anwendungsfälle
Zahlentheorie-Unterricht und Hausaufgaben
Studierende senden a und eine ungerade Primzahl p und vergleichen die geordneten Wurzeln mit handgerechneten Cipolla-Schritten oder Tabellen im Lehrbuch.
Krypto-Lehrdemos und Notebooks
Veranschaulichen Sie Cipolla neben Legendre-Prüfungen in Rabin- oder Elliptische-Kurven-Notizen ohne eine schwere Algebra-Bibliothek zu importieren.
Häufige Fragen
Wie berechne ich eine modulare Quadratwurzel mit Cipollas Algorithmus?
Senden Sie Ganzzahlen a und eine ungerade Primzahl p.
Was passiert, wenn a kein quadratischer Rest modulo p ist?
Es wird keine Wurzel erfunden, und der Aufruf wird nicht berechnet.
Warum muss p eine ungerade Primzahl sein?
Cipollas Algorithmus und Eulers Kriterium sind für ungerade Primzahlen definiert. Gerade oder zusammengesetzte Moduln werden abgelehnt, damit die Antwort nie so tut, als verhalte sich ein Nichtprimkörper wie F_p.
Worin unterscheidet sich das vom Legendre-Symbol-Rechner?
Legendre meldet nur Residuosität (−1, 0 oder 1). Diese Fähigkeit konstruiert die expliziten Quadratwurzeln, wenn sie existieren, über die Potenzierung im Cipolla-Erweiterungskörper.
Worin unterscheidet sich Cipolla vom Tonelli-Shanks-Verfahren?
Beide finden dieselben Wurzeln. Cipolla ist im Unterricht oft kürzer nachzuvollziehen und braucht keine Zerlegung von p minus eins: Es rechnet in einer Erweiterung des Körpers mit p Elementen und erhebt ein Element in die Potenz p plus eins durch zwei.
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/cipolla-algorithm \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":2,"p":7}'const res = await fetch("https://api.kit.forhosting.com/numth/cipolla-algorithm", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 2,
"p": 7
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/cipolla-algorithm",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 2,
"p": 7
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/cipolla-algorithm", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":2,"p":7}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":2,"p":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/cipolla-algorithm", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Beispiel-Anfrage
{
"a": 2,
"p": 7
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.cipolla_algorithm",
"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.
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
Diese Fähigkeit prüft, dass p eine ungerade Primzahl ist, lehnt Nichtreste mit einem klaren invalid_input-Fehler ab, führt eine vollständig deterministische Cipolla-Konstruktion aus (ohne zufällige omega-Ziehungen) und liefert beide Wurzeln, wenn sie existieren.
Was eine modulare Quadratwurzel ist und wann Cipolla gilt
Die Konstruktion scheitert genau dann, wenn a ein Nichtrest ist; dieser Endpunkt meldet das als invalid_input statt eine erfundene Wurzel zu erfinden.
Eingabevertrag, Algorithmusschritte und Antwortform
Der Absolutbetrag von a darf eine Billion nicht überschreiten. Anschließend multipliziert er im Ring der Elemente x plus y mal Wurzel von w und erhebt omega plus Wurzel von w zur Potenz (p plus eins) durch zwei mit exakten modularen BigInt-Multiplikationen. Beispiel: a gleich zwei und p gleich sieben liefert die Wurzeln drei und vier, weil drei zum Quadrat neun ist, also zwei modulo sieben. Senden Sie einen JSON-Körper mit zwei Pflicht-Ganzzahlfeldern: a, die Zahl, deren Quadratwurzel modulo p Sie wollen, und p, eine ungerade Primzahl zwischen drei und einer Billion einschließlich. Jedes Feld darf als JSON-Zahl oder als Ziffernstring mit optionalem Vorzeichen ankommen. Fehlende Felder, Nicht-Ganzzahlen, Werte außerhalb des Bereichs, gerades p und zusammengesetztes p scheitern mit invalid_input und werden nicht berechnet. Ist a_mod null, ist die Antwort die triviale Wurzel null mit method trivial_zero und omega null. Andernfalls wird das Legendre-Symbol von a_mod modulo p über Eulers Kriterium berechnet; der Wert minus eins bedeutet, dass a ein quadratischer Nichtrest ist und die Aufgabe mit einer Meldung scheitert, die die Restklasse nennt. Ist das Symbol plus eins, sucht der Algorithmus das kleinste nichtnegative omega, sodass Legendre von omega zum Quadrat minus a_mod minus eins ist — dieser Scan ist deterministisch, dasselbe Paar nutzt also immer denselben Zeugen. Die Körperkomponente ist eine Quadratwurzel; die API liefert beide geordneten Wurzeln, die bevorzugte kleinere Primärwurzel, den Zeugen omega, method cipolla und verified true nach interner Quadratprüfung.
Wo modulare Cipolla-Quadratwurzeln ihren Nutzen zeigen
Forschungsnotebooks, die bereits Legendre- oder Jacobi-Symbole berechnen, können die Wurzel nur anfordern, wenn das Symbol eins ist, und zahlen $0.002 pro erfolgreichem Item und nichts bei Validierungsfehlern.
Integrationsbeispiele
Wettbewerbsprogrammierung und LMS-Bewertung
Korrektoren prüfen Antworten zu modularen Quadratwurzeln, lehnen Nichtreste und zusammengesetzte Moduln mit invalid_input ab und halten omega über Läufe deterministisch.
Technische Fragen
Was kostet das Werkzeug für modulare Cipolla-Quadratwurzeln?
Das Browser-Werkzeug ist kostenlos. API-Anfragen nutzen das vorausbezahlte KIT-Guthaben zu $0.002 pro erfolgreichem Aufruf; ungültige Eingaben werden nicht berechnet.