Hi
Da will ich mich mal nicht lumpen lassen und einige zusätzliche Infos rüberwachsen lassen.
1.) im Ordner \Intf\ des ZIPs findest du alle Interfaces der Units aus dem DECMath. In der Datei NInts.pas findest du dann auch alle Funktionen samt Remarks dazu.
2.) DECMath enthält schon ein Objekt TSmallPrimeSieve in
Unit Prime.pas. Mit diesem Sieb hats du sehr schnell alle Primzahlen zwischen 2 bis 2^32-1 zur Verfügung.
Beispiel für die Benutzung
Delphi-Quellcode:
var
I,P: Cardinal;
begin
// Ausgabe der 100'ten bis 1000'ten Primzahl
for I := 100 to 1000 do
WriteLn( Primes[I] );
// suche Index der Primzahl 13
WriteLn( Primes.IndexOf(13) )
// Überprüfung ob Cardinal eine Primzahl ist
if IsPrime(123456789) then
end;
3.) diese Primzahlsieb wird nun in einigen Faktorizations Funktionen der IInteger benutzt
Beispiel
Delphi-Quellcode:
var
N: IInteger;
F: Cardinal;
begin
NRnd(N, 128); // 128 Bit großen Integer erzeugen
repeat
F := NSmallFactor(N);
if F > 1 then
begin
WriteLn(F);
NDiv(N, F); // N := N / F;
end;
until F <= 1;
WriteLn(NStr(N)); // N ausgeben
if NIsProbablePrime(N) then WriteLn('is prime)
else WriteLn('is composite');
end;
function NSmallFactor(const A: IInteger; Bound: Cardinal): Cardinal;
// Result == 0 if A = 0
// Result == 1 if A is not divisible by all primes <= bound or
// if A is < 2^32 if A is prime
// Result >= 2 small prime divisor
// about <10000 Cycles per digit and Bound = $FFFF and A >= 2^960
// 2.6 times faster as with the use of normal NMod() operation
// about <96 Cycles per digit and Bound = 239 and A >= 2^960
// the growrate isn't linear, bigger A are faster tested per digit
NSmallFactor(N) ermittelt ob eine Zahl N durch eine Primzahl bis < 2^32 teilbar ist. Wenn ja gibt NSmallFactor() diesen Faktor zurück. Dabei arbeitet diese Funktion mit hocheffizienten Verfahren die die modulare Division -> mod -> die normalerweise notwendig wäre ersetzt. Damit dürfte diese Funktion weitaus schneller sein als jeder normale TrialDivisons Ansatz. Gearbeitet wird in dieser Funktion mit einer Multiplikation zum moduarem Inversen der kleinen Primzahlen bis 2^32. Im Bereich bis 2^16 werden zb. durch ein einzigste dieser Multiplikation gleich 2 Primzahlen abgetestet. Ein weitere sehr performanter Test der als erstes durchgeführt wird wird mit einer Addition modulo 2^96-1 gearbeitet. Dieser Test reduziert die Zahl N modulo 2^96-1, was mit reinen Additionen durchführbar ist. Das Resultat (96 Bits Zahl) wird nun mit einer speziellen modularen DIvision ausgewertet und kann in einem Rutsch gleich 12 der kleinen Primzahlen austesten.
NTrialDivision(N) testet N ob es durch ein der kleinen Primzahlen geteilt werden kann. Diese Funktion liefert nur die Antwort ob die Zahl N "teilbar" oder "nicht teilbar" ist.
NIsProbablePrime(N) ist nun ein Pseudo Primzahl Test, so was ähnliches wie das Rabin Miller Verfahren. Damit kann man also jede beliebige Zahl auf Primzahl testen. Die Wahscheinlichkeit das diese Zahl dann auch eine Primzahl ist beträgt 1/N wobei N unser zu testende Zahl ist. Wenn du also zb. ein 512 Bit große Zahl damit testest dann ist die Wahrscheinlichkeit das sie denoch keine Primzahl ist obwohl der Test es meint nur 1/2^512 gruß, also fast unendlich klein. Deshalb nennt man solche getesteten Zahlen auch "industrielle Primzahlen". Nun, NIsProbablePrime() benutzt ein sehr sehr modernes Verfahren, das wesentlich schneller und auch sicherer ist als ein Rabin Miller Test. Das Verfahren das benutzt wird ist ein "Strong Probable Lucas Prime Test" nach "Pomerance, Selfridge, Wagstaff und Bailie". Zusätzlich testet dieses Verfahren auch noch ob N ein perfektes Quadrat ist -> N = X^2.
NIsProbablePrime() ist eine Allround Funktion, d.h. sie benutzt verschiedene Testverfahren um dann ein gutes ergebnis zu liefern. Als erstes eine Trial Divison mit NTrialDivison() und danach den SPP Test -> NSPP().
NSPP(N, array of Primes) -> Example: if NSPP(N, [2,3,5,7]) then
testet mit einem Strong Pseudo Primality Algorithmus die Zahl N. Dabei wird im Array [] die Zahlen angegeben zu denen getestet werden wollen (fast immer Primzahlen). Normalerweise reicht der Auffruf NSPP(N, [1, 2]) aber aus. In diesem Moment wird mit dem moderneren Bailie-Pomerance-Selfridge-Wagstaff-Test gearbeitet.
NMakePrime() erzeugt eine industrielle Primzahl
Delphi-Quellcode:
var
P: IInteger;
begin
NRnd(P, 512); // P zufällige Zahl mit 512 Bit Größe erzeugen
NMakePrime(P, [1,2]); // erzeuge eine starke Pseudo Primzahl
WriteLn( NStr(P) );
end;
So, das als grundsätzliches Handwerkszeug. Interessant sind auch noch die Lucas Funktionen -> NLucasMod() usw.
Aber das ist leider nur der Anfang. Auch deine Methode per Trial Divisionen mit den kleinen Primzahlen zu arbeiten ist wirklich nur der Anfang. Solche Verfahren sind die von der Komplexität her gesehen schlechtesten die es gibt. Dh. bei zahl größer 2^64 wird es weitaus besser Verfahren geben als die Trial Divison. Zb. Faktiorsation mit dem Zahlensieb (das bisher beste Verfahren), es arbeitet mit hoch komplexer Mathematik und sehr oft in Elliptischen Kurven (auch da enthält DECMath in den Units GFPs.pas zb. alles was man für Elliptische Kurven in GF(p) benötigt). Oder die Methoden nach Rabin, Williams+1, Pollard Rho, Pollard PP+1 usw.
Das sind alles Verfahren die weitaus effizienter Zahlen faktorisieren können.
Gruß Hagen