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.

→ Mathematik-Units · std.bignum · std.modmath

import std.prime;

Schicht 3 — die Spitze der Sammlung. Hängt an std.bignum und std.i128. 8 Funktionen. Alle Beispiele mit lyxc 1.0.21A übersetzt und ausgeführt.

<WRAP alert> 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. </WRAP>

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.

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„.

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).

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.

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.