Solovay-Strassen-Primzahltest mit gewählter Basis
Für 13 mit Basis 2 ergeben beide Reste 12, also besteht 13 den Test und ist zur Basis 2 wahrscheinlich prim. Stimmen die Reste nicht überein, ist die Zahl nachweislich zusammengesetzt. 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
- N
- 13
- Erster Text
- 2
- Gcd
- 1
- Jacobi-Symbol
- -1
- Euler-Rest
- 12
- Erwarteter Rest
- 12
Der Solovay-Strassen-Primzahltest prüft, ob sich eine ungerade ganze Zahl für eine von Ihnen gewählte Basis wie eine Primzahl verhält. Er berechnet das Jacobi-Symbol der Basis modulo des Kandidaten, potenziert die Basis mit der Hälfte des Kandidaten minus eins und vergleicht beide Werte modulo des Kandidaten. Das Ergebnis liefert entweder einen eindeutigen Nachweis für eine zusammengesetzte Zahl oder meldet, dass die Zahl bezüglich dieser Basis wahrscheinlich prim ist. Dezimalzeichenketten erhalten große ganze Zahlen exakt und vermeiden Gleitkommarundungen.
Bedeutung des Vergleichs
Für eine ungerade Primzahl n und jede nicht durch n teilbare Basis a besagt das Euler-Kriterium, dass a hoch (n - 1) / 2 modulo n zum Legendre-Symbol von a kongruent ist. Das Jacobi-Symbol erweitert diese Berechnung auf ungerade zusammengesetzte Kandidaten und lässt sich ohne Kenntnis der Faktorisierung von n effizient bestimmen. Solovay-Strassen vergleicht die modulare Potenz mit dem als Rest dargestellten Jacobi-Symbol: 1 bleibt 1, während -1 zu n - 1 wird.
Eine Abweichung beweist mathematisch, dass n zusammengesetzt ist. Eine Übereinstimmung ist schwächer. Eine andere gültige Basis kann eine zusammengesetzte Zahl erkennen, die den ersten Vergleich bestanden hat.
Die Antwort enthält beide Reste, den Jacobi-Wert und den größten gemeinsamen Teiler, damit Sie die Entscheidung nachvollziehen können und nicht lediglich einen unbegründeten booleschen Wert erhalten.
Eingaben auswählen und prüfen
Geben Sie n und a als vorzeichenlose Dezimalzeichenketten an. Der Kandidat n muss ungerade und mindestens 3 sein; gerade oder kleinere Werte führen zu einem Fehler wegen ungültiger Eingabe, da sie außerhalb des angegebenen Testbereichs liegen. Die Basis muss 1 < a < n erfüllen.
Sie müssen die Teilerfremdheit nicht vorab prüfen: Die Fähigkeit berechnet gcd(a, n), und ein nichttrivialer gemeinsamer Faktor weist den Kandidaten sofort als zusammengesetzt aus. Jede Eingabe ist auf 1,000 Dezimalstellen begrenzt, sodass der Rechenaufwand eine eindeutige Schranke besitzt. Vorzeichen, Leerzeichen, Dezimalpunkte, Exponentialschreibweise und führende Nullen werden abgelehnt, um mehrdeutige Auslegungen zu vermeiden.
Wenn Sie Basen manuell auswählen, verwenden Sie mehrere verschiedene Basen für stärkere Evidenz. Diese Fähigkeit wählt keine Basis zufällig; dadurch bleibt jede Ausführung reproduzierbar und der geprüfte Zeuge kann präzise dokumentiert werden.
Das Ergebnis verantwortungsvoll deuten
Das Feld passes gibt an, ob die exakte Solovay-Strassen-Kongruenz für das übermittelte Paar gilt. Bei false lautet classification composite, und die angegebene Basis belegt, dass der Kandidat keine Primzahl sein kann. Wiederholen Sie den Test mit unabhängig ausgewählten Basen, wenn Solovay-Strassen durch eine Aufgabe oder ein Protokoll vorgeschrieben ist, und betrachten Sie jeden bestandenen Durchlauf als weitere probabilistische Evidenz, nicht als Beweis.
Für neue sicherheitskritische Systeme sollten Sie ein modernes, sorgfältig spezifiziertes Primzahltestverfahren mit geeigneter Rundenzahl und geprüfter Zufälligkeit verwenden, statt einer einzigen manuell gewählten Basis zu vertrauen.
Anwendungsfälle
Einen Lehrbuchzeugen prüfen
Reproduzieren Sie eine Solovay-Strassen-Aufgabe mit genau dem im Aufgabentext genannten Kandidaten und der genannten Basis.
Pseudoprimzahlverhalten untersuchen
Vergleichen Sie, wie ein zusammengesetzter Kandidat mit einer Basis besteht und mit einer anderen scheitert, einschließlich aller Zwischenwerte.
Reproduzierbare Vorprüfung erstellen
Dokumentieren Sie deterministische Ergebnisse einzelner Basen, bevor Sie weitere Basen oder ein stärkeres Primzahlverfahren anwenden.
Häufige Fragen
Beweist ein bestandener Test, dass n prim ist?
Nein. Er bedeutet nur, dass n bezüglich der angegebenen Basis wahrscheinlich prim ist; eine andere Basis kann die Zusammengesetztheit beweisen.
Warum muss n ungerade und mindestens 3 sein?
Der hier verwendete Jacobi-Symbol-Vergleich ist für ungerade Kandidaten ab 3 definiert.
Was geschieht, wenn a und n einen Faktor teilen?
Der zurückgegebene gcd legt den gemeinsamen Faktor offen, und der Test klassifiziert n als zusammengesetzt, ohne den Jacobi-Vergleich als bestanden zu werten.
Wählt die Fähigkeit eine zufällige Basis?
Nein. Sie geben die Basis an; dadurch ist die Berechnung deterministisch und reproduzierbar.
Wie groß dürfen die Zahlen im Solovay-Strassen-Test sein?
Jede Zahl darf bis zu 1.000 Dezimalstellen haben. Beide werden genau so verarbeitet, wie Sie sie eingeben, ohne Rundung, sodass ein riesiger Kandidat denselben exakten Vergleich erhält wie ein kleiner.
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/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)Beispiel-Anfrage
{
"n": "561",
"a": "2"
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.solovay_strassen_test",
"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_digits | 1000 |
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
Bedeutung des Vergleichs
Sie besagt nur, dass n den Test für die gewählte Basis bestanden hat; deshalb lautet die sorgfältige Klassifizierung probable_prime_to_base.
Eingaben auswählen und prüfen
Zeichenketten sind wichtig, weil gewöhnliche JSON-Zahlen nicht jede große ganze Zahl exakt darstellen können.
Das Ergebnis verantwortungsvoll deuten
Bei true lautet classification probable_prime_to_base und nicht prime. Die Detailfelder erläutern das Ergebnis: gcd zeigt einen unmittelbaren gemeinsamen Faktor, jacobi_symbol ist -1, 0 oder 1, euler_residue enthält die berechnete modulare Potenz und expected_residue normalisiert den Jacobi-Wert in den Restklassenbereich modulo n. API-Anfragen verwenden den veröffentlichten Grundpreis $0.002; dieselbe deterministische Berechnung eignet sich außerdem für die interaktive Nutzung im Browser.
Technische Fragen
Warum sind n und a Zeichenketten statt JSON-Zahlen?
Dezimalzeichenketten erhalten ganze Zahlen jenseits des sicheren JavaScript-Zahlenbereichs exakt und verhindern unbemerkte Rundungen.
Was kostet eine API-Anfrage?
Der Grundpreis beträgt $0.002 pro Anfrage. Eine Anfrage prüft ein Kandidat-Basis-Paar.