====== std.prime — Primzahltest ======
Miller-Rabin für Zahlen beliebiger Größe, mit einer deterministischen Zeugenmenge unterhalb von 3,3·10²⁴ und der Suche nach der nächsten Primzahl.
→ [[lyx_-_programmiersprache:units:mathematik|Mathematik-Units]] · [[lyx_-_programmiersprache:units:bignum|std.bignum]] · [[lyx_-_programmiersprache:units:modmath|std.modmath]]
import std.prime;
Schicht 3 — die Spitze der Sammlung. Hängt an [[lyx_-_programmiersprache:units:bignum|std.bignum]] und [[lyx_-_programmiersprache:units:i128|std.i128]]. 8 Funktionen. Alle Beispiele mit ''lyxc 1.0.21A'' übersetzt und ausgeführt.
----
**Die Zahlen sind Bignum-Zeiger, keine ''int64''-Werte.** Nur ''PrimeSmall(i)'' nimmt einen Index. Alle anderen Funktionen — einschließlich der Basis bei ''PrimeIsWitness'' — erwarten die Adresse einer mit ''BigNew'' angelegten Zahl:
var n: int64 := BigNew(64);
BigSetU64(n, 97);
var prim: bool := PrimeIsPrime(n, 20); // richtig
// PrimeIsPrime(97, 20) → Speicherzugriffsfehler
Wer eine gewöhnliche Zahl übergibt, liest an dieser Adresse und bekommt einen **Speicherzugriffsfehler**.
----
===== Warum nicht einfach teilen =====
Eine Zahl auf Teilbarkeit zu prüfen kostet √n Divisionen. Für eine 2048-Bit-Zahl wären das 2¹⁰²⁴ Stück — mehr Schritte, als das Universum Atome hat. **Probedivision entscheidet über große Zahlen nichts**; sie siebt nur die offensichtlichen Fälle vorab aus, und genau dafür gibt es ''PrimeTrialDivide''.
----
===== Was Miller-Rabin tut =====
Ist ''p'' prim, hat ''1'' modulo ''p'' genau zwei Quadratwurzeln: ''1'' und ''−1''. Bei zusammengesetzten Zahlen gibt es weitere. Der Test sucht solche „falschen Wurzeln".
> **Der Test kann beweisen, dass eine Zahl zusammengesetzt ist — nicht, dass sie prim ist.** Findet er eine falsche Wurzel, steht das Ergebnis fest. Findet er keine, heißt das nur: **diese Basis war kein Zeuge**. Deshalb prüft man mehrere.
>
> Das ist der Grund für den Parameter ''rounds'' und für die Existenz von ''PrimeIsWitness'': ''true'' bedeutet dort „''n'' ist mit Sicherheit zusammengesetzt", ''false'' bedeutet „diese Basis sagt nichts".
----
===== Wann das Ergebnis sicher ist =====
Für kleinere Zahlen ist Miller-Rabin **kein Wahrscheinlichkeitsspiel, sondern ein Beweis**: übersteht ''n < 3 317 044 064 679 887 385 961 981'' (etwa 3,3·10²⁴) die ersten dreizehn Primzahlen als Basen, ist ''n'' prim. Das ist durchgerechnet und lückenlos.
''PrimeIsPrimeCertain(n)'' nutzt genau diese Menge. Darüber hinaus bleibt nur der wahrscheinlichkeitsbasierte Weg über ''PrimeIsPrime(n, rounds)''.
----
===== Ein vollständiges Beispiel =====
unit main;
import std.io;
import std.string;
import std.alloc;
import std.bignum;
import std.prime;
fn ZI(t: pchar, v: int64): void { Print(t); PrintLn(IntToStr(v)); }
fn ZD(t: pchar, p: int64): void {
var b: int64 := alloc(256);
BigToDecimal(p, b, 256);
Print(t); PrintLn(b as pchar);
}
fn Mk(v: int64): int64 { var p: int64 := BigNew(64); BigSetU64(p, v); return p; }
fn main(): int64 {
ZI("PrimeSmall(0) : ", PrimeSmall(0));
ZI("PrimeSmall(10) : ", PrimeSmall(10));
var n561: int64 := Mk(561);
var n97: int64 := Mk(97);
ZI("TrialDivide(561) : ", PrimeTrialDivide(n561));
ZI("TrialDivide(97) : ", PrimeTrialDivide(n97));
ZI("IsPrime(97, 20) : ", PrimeIsPrime(n97, 20) as int64);
ZI("IsPrime(561, 20) : ", PrimeIsPrime(n561, 20) as int64);
var b2: int64 := Mk(2);
ZI("IsWitness(561, Basis 2): ", PrimeIsWitness(n561, b2) as int64);
ZI("IsPrimeCertain(97) : ", PrimeIsPrimeCertain(n97) as int64);
var big: int64 := BigNew(64);
BigFromDecimal("170141183460469231731687303715884105727"c, big);
ZI("IsPrime(2^127-1, 20) : ", PrimeIsPrime(big, 20) as int64);
var m: int64 := Mk(1000000);
var out: int64 := BigNew(64);
PrimeNext(m, 20, out);
ZD("Naechste Primzahl > 1e6: ", out);
ZI("Coprime(9, 28) : ", PrimeCoprime(Mk(9), Mk(28)) as int64);
return 0;
}
PrimeSmall(0) : 2
PrimeSmall(10) : 31
TrialDivide(561) : 3
TrialDivide(97) : 0
IsPrime(97, 20) : 1
IsPrime(561, 20) : 0
IsWitness(561, Basis 2): 1
IsPrimeCertain(97) : 1
IsPrime(2^127-1, 20) : 1
Naechste Primzahl > 1e6: 1000003
Coprime(9, 28) : 1
Drei Zeilen tragen die Aussage:
* **''TrialDivide(561)'' liefert 3** — den kleinsten Faktor. Bei 97 kommt ''0'': kein kleiner Faktor gefunden, was **keine** Primzahlaussage ist, sondern nur das Ergebnis der Vorsiebung.
* **561 ist eine Carmichael-Zahl** (3·11·17) und besteht den einfachen Fermat-Test für jede teilerfremde Basis. Miller-Rabin fällt nicht darauf herein: ''IsPrime'' sagt ''0'', und Basis 2 ist nachweislich ein Zeuge.
* **2¹²⁷−1 wird als prim erkannt** — eine 39-stellige Mersenne-Primzahl, für Probedivision unerreichbar.
----
===== Funktionsübersicht =====
^ Funktion ^ Zweck ^
| ''PrimeSmall(i)'' | die ''i''-te kleine Primzahl (nimmt einen **Index**, keinen Zeiger) |
| ''PrimeTrialDivide(n)'' | kleinster Faktor aus der Vorsiebung, ''0'' wenn keiner |
| ''PrimeIsWitness(n, base)'' | ist diese Basis ein Zeuge für „zusammengesetzt"? |
| ''PrimeIsPrime(n, rounds)'' | Miller-Rabin mit ''rounds'' Basen |
| ''PrimeIsPrimeWithBases(n, bases, count)'' | mit selbst gewählten Basen |
| ''PrimeIsPrimeCertain(n)'' | deterministisch unterhalb 3,3·10²⁴ |
| ''PrimeNext(n, rounds, out)'' | nächste Primzahl größer ''n'' |
| ''PrimeCoprime(a, b)'' | teilerfremd? |
----
===== Offene Punkte =====
> **''PrimeIsPrime'' und ''ModIsPrime'' kennen einander nicht.** Für eine Zahl, die in ''int64'' passt, wäre ''ModIsPrime'' aus [[lyx_-_programmiersprache:units:modmath|std.modmath]] deutlich schneller — ''PrimeIsPrime'' delegiert dorthin bisher nicht. Wer weiß, dass die Zahl klein ist, ruft ''ModIsPrime'' selbst auf.
>
> **Es gibt keine Zufallsquelle für Basen.** ''rounds'' arbeitet mit einer festen Folge. Für eine Schlüsselerzeugung, bei der ein Angreifer die Basen nicht vorhersagen können soll, fehlt eine ''PrimeRandom(bits)''-Funktion samt geprüfter Zufallsquelle.
----
Letzte Aktualisierung: 2026-08-16 · alle Beispiele mit ''lyxc 1.0.21A'' übersetzt und ausgeführt; die Carmichael-Zahl 561 als Negativkontrolle und 2¹²⁷−1 als Positivfall einzeln nachgemessen.