Autor |
Beitrag |
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Do 21.06.12 22:46
Hallo,
wieder einmal ein kleines Programm meinerseits. Dieses versucht von etwas größeren, natürlichen Zahlen (20 Stellen und mehr) die Primteiler zu ermitteln.
Grundlage dafür ist nach Probedivision das Pollard-Rho-Verfahren. de.wikipedia.org/wiki/Pollard-Rho-Methode
Außerdem wird ein Primzahltest nach Rabin-Miller durchgeführt.
Das Programm kann sich zwar mit professionellen Faktorisierungsprogrammen (Faktorisierung mit elliptischen Kurven oder quadratischen Sieben) nicht messen, aber bis zu 30stelligen Zahlen geht es schon; wenn man Glück hat. Das Pollard-Rho-Verfahren ist leider "nur" probabilistisch.
Beste Grüße
Mathematiker
Nachtrag: Durch die Mitarbeit von Lelf wurde das Pollard-Rho-Verfahren gegen das wesentlich schnellere Brent-Rho-Verfahren getauscht.
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Zuletzt bearbeitet von Mathematiker am Di 03.07.12 11:30, insgesamt 5-mal bearbeitet
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Fr 22.06.12 07:54
|
|
Lelf
Beiträge: 42
Erhaltene Danke: 21
|
Verfasst: Sa 23.06.12 14:48
was ich mir noch wünschen würde:
- Abfangen von falschen Zeichen in Edit1
- ein Zeitanzeige
- Korrektur in FGIntRabinMiller:
Delphi-Quelltext 1:
| While ((temp1.Number[1] Mod 2) = 0)and(FGIntCompareAbs(temp1, zero) <> eq) Do Begin |
- eine Brent-rho Implementierung:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143:
| unit UBrentRho;
interface
uses FGInt; function BrentRho(var A: TFGInt; var d: integer; var Z: TFGInt): string;
implementation
uses Forms, Math, SysUtils, Windows, ufaktor; function BrentRho(var A: TFGInt; var d: integer; var Z: TFGInt): string; var okay: boolean; s: string; r, i, j, k, m: integer; time, t: cardinal; xx, yy, tt, tmp, temp1, temp2, factorGGT, one: TFGInt;
label neu;
begin if(Length(A.Number) = 0)then exit;
Base10StringToFGInt('0', xx); Base10StringToFGInt('0', yy); Base10StringToFGInt('0', temp1); Base10StringToFGInt('1', temp2); Base10StringToFGInt('1', factorGGT); Base10StringToFGInt('1', one); Base10StringToFGInt('0', tt); Base10StringToFGInt('0', tmp); result:=''; time:= GetTickCount;;
TRY
FGIntRabinMiller(A, 3, okay); if(okay)then begin FGIntToBase10String(A, s); result:= format('%s', [s]); d:=0; end; WHILE not(okay)DO BEGIN neu: d:=0; r:=1; m:=1024;
while(FGIntCompareAbs(factorGGT, one) = eq)do begin
FGIntCopy(yy, xx); for i:=1 to r do begin FGIntSquare(yy, tt); FGIntAdd(tt, Z, tmp); FGIntMod(tmp, A, yy); end;
k:=0; j:= min(m, r);
repeat
for i:=j downto 1 do begin FGIntSquare(yy, tt); FGIntAdd(tt, Z, tmp); FGIntMod(tmp, A, yy);
FGIntSub(xx, yy, temp1); FGIntAbs(temp1); FGIntMul(temp1, temp2, tt); FGIntMod(tt, A, temp2); end;
FGIntGCD(temp2, A, factorGGT); d:=d + 1; k:=k + m;
if(d and 7 = 0)then begin t:= GetTickCount; Application.ProcessMessages; Form1.lblZeit.Caption:= Format('D: %d time: %.1f sec', [d, (t - time)/1000]); if(abbruch)then begin Form1.Memo1.Lines.Add(Format('abgebrochen bei D: %d', [d])); exit; end; end;
until((k >= r) or (FGIntCompareAbs(factorGGT, one) <> eq));
r:= r shl 1; end;
if(FGIntCompareAbs(factorGGT, one) <> eq)then begin
FGIntToBase10String(factorGGT, s); FGIntDiv(A, factorGGT, A);
if(FGIntCompareAbs(A, one) = eq)then begin FGIntCopy(factorGGT, A); FGIntAdd(Z, one, Z); Base10StringToFGInt('1', temp2); Base10StringToFGInt('1', factorGGT); goto neu; end else result:= format('%s%s * ', [result, s]);
FGIntRabinMiller(A, 3, okay); if(okay)then begin FGIntToBase10String(A, s); result:= format('%s%s', [result, s]); end else Base10StringToFGInt('1', factorGGT);
end;
END; FGIntToBase10String(Z, s); Form1.lblZeit.Caption:= Format('D: %d Z: %s time: %.2f sec fertig!', [d, s, (GetTickCount - time)/1000]);
FINALLY FGIntDestroy(xx); FGIntDestroy(yy); FGIntDestroy(temp1); FGIntDestroy(temp2); FGIntDestroy(factorGGT); FGIntDestroy(one); FGIntDestroy(tt); FGIntDestroy(tmp); END; end; end. |
Aufruf in TForm1.Button1Click(Sender: TObject); wäre dann:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| var ... ..., A, Zz: TFGInt; begin ... Base10StringToFGInt(k, A); Base10StringToFGInt('1', Zz); k:= BrentRho(A, d, Zz); ... memo1.lines.add('Teiler = '+k); ... end; |
Gruß Lelf
Moderiert von Christian S.: Delphi-Tags hinzugefügt
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Sa 23.06.12 15:06
Hallo Lelf,
besten Dank für die vielen, guten Hinweise. Ich werde diese einbeziehen.
Danke
Mathematiker
Nachtrag: Auf Grund der Unterstützung durch Lelf ist die überarbeitete Version noch schneller. (siehe neue Version im ersten Eintrag)
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Lelf
Beiträge: 42
Erhaltene Danke: 21
|
Verfasst: Sa 23.06.12 20:46
Hallo Mathematiker,
wenn Du Dein Programm noch wirkungvoller gestalten willst, empfehle ich Dir anstelle der unit FGInt eine effizientere Library zu verwenden wie zum Beispiel:
MPArith package unter http: www.wolfgang-ehrhardt.de
Mit einer ähnlichen Library habe ich folgende Ergebnisse erziehlt:
Faktoren von 347 068 499 990 683 866 034 691 710 961 (30)
98296514606911(14)
3530832210873551(16)
Brent-rho: 1,6976sec d: 132 z: 32
Faktoren von 85 663 386 900 622 087 599 187 757 435 826 763 (35)
48616941244147(14)
1762006919983579059529(22)
Brent-rho: 7,0012sec d: 419 z: 12
Gruß Lelf
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: So 24.06.12 10:15
Lelf hat folgendes geschrieben : | Hallo Mathematiker,
wenn Du Dein Programm noch wirkungvoller gestalten willst, empfehle ich Dir anstelle der unit FGInt eine effizientere Library zu verwenden wie zum Beispiel:
MPArith package unter http: www.wolfgang-ehrhardt.de |
Und wie schaut es diesbzeüglich mit Benny Baumanns BigNum2-Unit (meinem derzeitigen Favoriten) aus? Muß diese den Vergleich zur Wolfgang Ehrhardts Unit nicht scheuen oder doch?
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: So 24.06.12 10:22
Hallo Delphi-Laie,
Delphi-Laie hat folgendes geschrieben : | Und wie schaut es diesbzeüglich mit Benny Baumanns BigNum2-Unit (meinem derzeitigen Favoriten) aus? Muß diese den Vergleich zur Wolfgang Ehrhardts Unit nicht scheuen oder doch? |
Kann ich noch nicht sagen. Im Moment bin ich gerade dabei, die 3 Units FGInt, MPArith und BigNum2 miteinander zuvergleichen. Gegenwärtig liegt MPArith im Vergleich zu FGInt klar vorn, BigNum2 muss ich noch ausprobieren. Dazu muss ich die Verwendung von BigNum2 aber erst einmal verstehen.
MPArith ist zwar superschnell aber schlechter zu handhaben als FGInt. Insbesondere die Freigabe des verwendeten Speichers am Ende ist etwas problematisch.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: So 24.06.12 10:37
Die Frage war vornehmlich an Lelf gerichtet.
Mathematiker hat folgendes geschrieben : | Dazu muss ich die Verwendung von BigNum2 aber erst einmal verstehen. |
Das sollte eigentlich kein Problem sein. Es gibt zwei Schnittstellenfunktionen, die Strings in BigNums bzw. umgekehrt konvertieren. Ein zusätzlicher Parameter muß dabei gesetzt werden, um mitzuteilen, ob Dezimal- oder Hexadezimalen gemeint bzw. gewünscht sind (das war mir auf die Dauer jedoch zu fummelig und unübersichtlich, deshalb kreierte ich neue Funktionen, die auf diesen Parameter verzichten, und noch weitere, die Kovertierung Cardinal<>BigNum vereinfachen - siehe in meinem Langzahlentaschenrechner). Der Rest sind - zum Glück - Funktionen mit selbsterklärenden Bezeichnungen, ich halte die Unit deshalb insgesamt für gut "handhabbar". In seiner BigNum-Diskussionen setzte ich einige meiner Beoachtungen hinein.
Zuletzt bearbeitet von Delphi-Laie am So 24.06.12 13:49, insgesamt 1-mal bearbeitet
|
|
Lelf
Beiträge: 42
Erhaltene Danke: 21
|
Verfasst: So 24.06.12 12:51
Hallo,
Die BigNum2-Unit braucht einen Vergleich zu anderen Libraries keinesfalls zu scheuen. Sie ist wirklich Klasse und schön schlank.
Ich bin gerade dabei die oben beschriebene Brent-Rho-Procedure mit BigNum2 zu implementieren und finde keine Rabin-Miller-Primzahltest. Habe ich etwas übersehen?
Gruß Lelf.
Für diesen Beitrag haben gedankt: Delphi-Laie
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: So 24.06.12 12:55
Hallo Lelf,
Lelf hat folgendes geschrieben : | Ich bin gerade dabei die oben beschriebene Brent-Rho-Procedure mit BigNum2 zu implementieren und finde keine Rabin-Miller-Primzahltest. Habe ich etwas übersehen? |
Hast Du nicht. BigNum2 braucht noch ein paar Routinen für Primzahlen. Vielleicht kannst Du sie ja schreiben.
Übrigens kämpfe ich im Moment mit Deiner Brent-Rho-Methode für FGInt. Sie ist superschnell, nur leider gibt sie ab und an keine Primteiler sondern zusammengesetzte Zahlen zurück. Bis jetzt konnte ich ihr das noch nicht abgewöhnen .
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Lelf
Beiträge: 42
Erhaltene Danke: 21
|
Verfasst: So 24.06.12 14:41
Hallo Mathematiker
Verwende in einem solchen Fall ein anderes z und rechne von vorn oder starte neu mit anderen Anfanfswerten für xx und/oder yy.
Gruß Lelf
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Mo 25.06.12 13:40
Warum neu anfangen? Ein zusammengesetztes Ergebnis ist doch (wenn's nicht gerade der Ausgangswert N ist) viel besser: Du hast dann mindestens zwei Faktoren zu Preis von einem!
Im Übrigen ist das oben implementierte Pollard-Brent-Verfahren nicht Standard. Normalerweise macht macht man eine Kopie des letzten Zwischenergebnisses mit ggt=1 und verwendet dies als Aufsetzpunkt für ein normales Pollard-Rho, wenn der ggt=N ist, siehe zB Pollard-Brent-Code. Dieser Teil ist (soweit ich das sehe) nicht implementiert, und würde einen Neustart für Faktor=N vermeiden.
Aber der Geschwindigkeitsvorteil von Pollard-Brent ist relativ. Wenn nur ein Verfahren verwendet werden soll, ist es idR schneller als Pollard-Rho, aber es gibt andere kompakte Verfahren (p+1, p-1) für spezielle Zahlen oder ECM für allgemeinere Zahlen, die normalerweise schneller sind. Deshalb benutze ich in MPArith ein paar Pollard-Rho-Zyklen (allerdings mit schneller Barret-Reduktion statt mod) nach wenigen Iterationen der 'kleinen Spezial-Verfahren' bevor die Hauptarbeit von ECM gemacht wird.
An ein Quadratisches Sieb wie MPQS oder gar an NFS habe ich mich nicht getraut, wäre wohl nur etwas für Hardcore - Langstrecken - Faktorisierer.
|
|
Lelf
Beiträge: 42
Erhaltene Danke: 21
|
Verfasst: Mo 25.06.12 17:10
Hallo
Daß die oben implementierte Brent-Rho-Methode nur für bestimmte Zwecke zu gebrauchen ist und Teiler von max. 14-15 Dezimalstellen innerhalb einer Minute(wenn es gut geht) finden kann, ist mir durchaus bewusst. Der Rat, mit einem neuen z zu rechnen, war eigentlich ein pädagogischer. Ich wollte die Interessierten dieses Themas dazu bringen, mit verschieden z's zu spielen, damit folgender Zusammenhang zu beobachten wäre:
_____________________________
Brent-rho Number: 26319475462595362139394151429 (29) BitLength: 95
factors: 1056550654801 (L13) * 24910755904602229 (L17)
d: 640 z: 1
time: 8,990 sec
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ 25.06.2012 15:20:37
_____________________________
Brent-rho Number: 26319475462595362139394151429 (29) BitLength: 95
factors: 1056550654801 (L13) * 24910755904602229 (L17)
d: 41 z: 7
time: 0,375 sec
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ 25.06.2012 15:21:17
_____________________________
Brent-rho Number: 26319475462595362139394151429 (29) BitLength: 95
factors: 1056550654801 (L13) * 24910755904602229 (L17)
d: 1050 z: 455357030
time: 16,333 sec
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ 25.06.2012 17:01:27
Gammatester hat natürlich richtig bemerkt, daß ein totaler Neuanfang nicht nötig ist.
Gruß Lelf
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Do 28.06.12 19:47
Hallo Lelf,
Lelf hat folgendes geschrieben : | Nun habe ich noch den Brent-rho-Algorithmus mit mPArith implementiert. |
Sehr schön, ist richtig schnell. Damit ist das Programm deutlich effektiver geworden.
Aber bei meinem gegenwärtigen Problem, 54061288181178547649030354328049287773587228638908640 zu faktorisieren, reicht es auch nicht. Nachdem ich mein eigenes Faktorisieren mit elliptischen Kurven gegen das von MPArith getauscht habe, komme ich trotzdem nicht weiter.
Beste Grüße
Mathematiker
Nachtrag: Kurz nach dem Absenden des Beitrags erhielt ich als Faktorisierung 2, 2, 2, 2, 2, 3, 5, 7, 13, 94788964849717261630343, 13057077434350756882820861.
Dennoch denke ich, dass es ohne quadratische Zahlsiebe bald nicht mehr geht. Kennst Du bessere Beschreibungen über quadratische Zahlkörpersiebe als die allgemeinen Ausführungen, z.B. bei Wikipedia.
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Lelf
Beiträge: 42
Erhaltene Danke: 21
|
Verfasst: Do 28.06.12 21:58
Hallo,
eine gute Beschreibung findest Du z.B. in www.karlin.mff.cuni....o/mpqs/main_file.pdf
oder google einfach mal mit MPQS.
Scott Patric Contini hat ein gute Implementierung(in C und GMP) zum Studieren ins Netz gestellt. Ich bastle auch an einer in Delphi. Da gibt es leider kaum eine Vorlage. Aber gerade desshalb is es sehr spannend:
_____________________________
MPQS_LP Number: 54061288181178547649030354328049287773587228638908640 (53) BitLength: 176
NUMBER has small prime factors: (2^5) * 3 * 5 * 7 * 13 *
new Number: 1237666853964710339950328624726403108369670985323 (49)
1. multiplier: 7 H: 9,166504 d: 0,000000 nn8: 5
2. multiplier: 67 H: 8,509277 d: 0,657227 nn8: 1
---> factorbase created. Bound1: 24.083 (maxprime) FB: 1.376 [*5 = 6.880 (LP-array)] 0,047 sec
multiplier: 7 (7,67) Log(Bound1): 10,089261 Differenz (Log(Bound1) - Hmultiplier) = 0,922758
smallprimes (7) = -1,2,3,5,11,13,17,19,29, 31 = primesFB[9]
logstart: 2,558594 n8: 3 nn8: 5 first g: 3606683099 (10)
TARGET_2: 48,260742 SIEVE_INTER: 40.000 M = 320.000 NUM = 8
First decomposed/sec: 309 k/sec: 1892 mal Bound2: 4.816.600 = Bound1 * 200
---> sieving process finished. k: 7.204
checked: 9.114 Polynome: 451 full relations: 763
largeP found: 5.588 partial relations: 645 (M: 232)
ADDITIONAL: 32 d_g34: 41.228
Ø decomposed/sec: 469,333 3,796 sec
---> built matrix. 0,000 sec
---> matrix solved. 0,156 sec
---> factors found. Versuche: 1 0,016 sec
(2^5) * 3 * 5 * 7 * 13 * 13057077434350756882820861 (Q26) * 94788964849717261630343 (Q23) ok, X is prime, Y is prime
time: 4,068 sec
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ 28.06.2012 21:46:15
Gruß Lelf
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Do 28.06.12 22:04
Hallo,
Lelf hat folgendes geschrieben : | Scott Patric Contini hat ein gute Implementierung(in C und GMP) zum Studieren ins Netz gestellt. |
Ich habe einen C-Quelltext (GNU-Lizenz) von Prof.Forster (München) als Bestandteil seines genialen Aribas-Programms erhalten. Da ich aber von C absolut keine Ahnung habe, komme ich damit überhaupt nicht zurecht.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Lelf
Beiträge: 42
Erhaltene Danke: 21
|
Verfasst: Fr 29.06.12 09:16
Hallo Mathematiker,
Eine Fundgrube findest Du, wenn Du mit "quadratic sieve diplomarbeiten" googelst: z.B.:
elib.uni-stuttgart.d...09/pdf/STUD_2007.pdf
Da es in Delphi kaum Quelltexte in dieser Sparte gibt, geht wohl kein Weg daran vorbei, sich in C und Java (C ähnlich mit eingebauter BigInteger-Klasse) einzuarbeiten. Java ist meiner Meinung nach das "verständlichere" C.
Ein mächtiges Programm (unglaublich schnell) mit Sourcecode in Java findest Du unter:
www.alpertron.com.ar/ECM.HTM
Gruß Lelf
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Fr 29.06.12 09:27
Lelf hat folgendes geschrieben : | Nun habe ich noch den Brent-rho-Algorithmus mit mPArith implementiert. |
Leider hat mich erst jetzt der Beitrag mit Anhang erreicht. Zwei Fragen noch:
Gibt es einen besonderen Grund, weshalb Du den über drei Jahre alten Quellcode der Version V1.11 verwendest (wo hast Du den eigentlich noch saugen können?) und nicht den neuesten veröffentlichten MPArith V1.20.24?
Warum benutzt Du für den Primtest mp_miller_rabin mit t=5? Warum nicht die automatische Wahl mit t=0? Für Deine Größenordnungen würde dann wahrscheinlich t=28 benutzt werden. Warum überhaupt mp_miller_rabin und nicht den Standardprimtest mit mp_is_pprime?
Gruß Gammatester
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Fr 29.06.12 09:28
Hallo Lelf,
das schnellste frei verfügbare Faktorisierungsprogramm soll MSieve 1.50 von Jason Papadopoulos sein.
tuts4you.com/download.php?view.1252
Ebenfalls mit Quellcode, aber natürlich wieder in C.
Mit der Version 1.44 habe ich schon 80stellige Zahlen mit zwei 40stelligen Primteilern zerlegt. Richtig schnell!
Gruß Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Lelf
Beiträge: 42
Erhaltene Danke: 21
|
Verfasst: Fr 29.06.12 10:14
Hallo,
@Gammatester:
Ganz einfach, vor 3 Jahren habe ich zuletzt die mpArith heruntergeladen und seither
meine eigene mit vielen Anregungen daraus weiterentwickelt.
RabinMiller deswegen, damit man auch sehr grosse Zahlen(>80 stellig) auf kleine Primfaktoren untersuchen kann, um dann mit ECM und QS weiterzumachen.
Den Parameter t habe ich offenbar nicht richtig verstanden. Danke für den Hinweis.
@Mathematiker
MSieve und Yafu sind mir wohl Begriffe. Erwähnenswert wäre noch QSieve von Thorsten Reinecke.
80-stellige Zahlen schaffe ich auch so gerade noch, benötige aber mindestens 2 Stunden dafür. Ich will mich vielleicht noch an das siqs wagen. Aber das wird noch Jahre dauern.
Gruss Lelf
|
|
|