Autor Beitrag
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Fr 29.06.12 10:50 
user profile iconLelf hat folgendes geschrieben Zum zitierten Posting springen:
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.

Miller-Rabin hat sich irgendwie festgesetzt, es ist mM ein Überbleibsel aus 20-30 Jahre alten RSA-Specs (wo es verlangt wird). Neuere Matheprogamme benutzen mehr oder weniger den auch in MPArith/ispprime verwendeten BPSW-Algorithmus (1 x Miller-Rabin mit Basis 2 und schließend 1 x starker Lucastest):
Zitat:
(Mathematica) PrimeQ first tests for divisibility using small primes, then uses the Miller-Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test.

(Maple, isprime) It returns false if n is shown to be composite within one strong pseudo-primality test and one Lucas test and returns true otherwise.

(Pari, default BPSW) ispseudoprime(x,{n}): true(1) if x is a strong pseudoprime, false(0) if not. If n is 0 or omitted, use BPSW test, otherwise use strong Rabin-Miller test for n randomly chosen bases.


Gruß Gammatester

PS: Der BPSW-Test kann wie alle Pseudoprimtest nur 'wahrscheinlich' prim sagen. Bisher ist jedoch kein Gegenbeispiel bekannt, wenn Du eines findest, wirst Du mit einem Schlag berühmt (zumindestest in einschlägigen Kreisen) und reich ($620 :wink: , siehe Prize Problems).
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2611
Erhaltene Danke: 1400

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Fr 29.06.12 11:14 
Hallo Gammatester,
user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:
Gibt es einen besonderen Grund, weshalb Du den über drei Jahre alten Quellcode der Version V1.11 verwendest ... und nicht den neuesten veröffentlichten MPArith V1.20.24?

Ich habe gerade 1 Stunde lang die Teilersummenfolge von 840 parallel mit V1.11 und V1.20 rechnen lassen. Das sind über 600 Faktorisierungen von teilweise 40stelligen Zahlen, viele Primzahltests usw.
Genutzt wurde der Miller-Rabin-Test, Lelfs Brent-Rho-Verfahren und die Faktorisierung mit elliptischen Kurven. Alle Parameter waren gleich.
Das Ergebnis ist überraschend: So lange die Glieder der Folge maximal 20 Stellen hatten, war V1.20 vorn. Dann holte die alte Version auf, und als Höhepunkt fand die neue Version für das 400.Glied
18753145125348788607553275398558954818510418200
Primteiler 2, 2, 2, 5, 5, 19, 1257099831268459831417, 3925732919637436942817,
die beiden großen Primteiler nicht, während die alte Version problemlos arbeitete.
Irgendwie komisch.
Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Fr 29.06.12 11:37 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
.. und als Höhepunkt fand die neue Version für das 400.Glied
18753145125348788607553275398558954818510418200
Primteiler 2, 2, 2, 5, 5, 19, 1257099831268459831417, 3925732919637436942817,
die beiden großen Primteiler nicht ...

Merkwürdig. Frisch aus dem Archiv kompiliertes t_pfde.exe liefert bei mir
ausblenden volle Höhe Quelltext
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:
Test of MPArith V1.20.24 (31/32 bit) [mp_calc/pfdu]  (c) W.Ehrhardt 2006-2012
To exit the test program entering an empty expressions string.

Expression to factor: 18753145125348788607553275398558954818510418200
N=18753145125348788607553275398558954818510418200
    2 2344143140668598575944159424819869352313802275
    5 93765725626743943037766376992794774092552091
   19 4935038190881260159882440894357619689081689
SLim: 1073676289
PFD1: 4935038190881260159882440894357619689081689
PRIM: 4935038190881260159882440894357619689081689 - FALSE
Word: ................
PPow:
PP-1: .........................................................................
...........................................................................
WP+1: .........................................................................
...........................................
PRho: .........................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
..............................................
ECM1: ................................................................
ECM2: .........................................................................
...........
PFD1: 3925732919637436942817
PRIM: 3925732919637436942817 - TRUE
PFD1: 1257099831268459831417
PRIM: 1257099831268459831417 - TRUE
2^3 * 5^2 * 19 * 1257099831268459831417 * 3925732919637436942817
Start: 18753145125348788607553275398558954818510418200
Check: 18753145125348788607553275398558954818510418200
 Time: 33.910s


Moderiert von user profile iconNarses: Beiträge zusammengefasst

Ich sehe gerade, daß in der von Leif angehängten MPArith V1.11 einige Manipulation vorgenommen wurden, zB sind aus mp_prng.pas die Includeanweisungen {$i STD.INC} und {$i mp_conf.inc} entfernt worden (warum auch immer??). Dadurch wird der Taus88-Generator verwendet. Wenn nun V1.20.24 aus der Box benutzt wird, werden völlig verschieden Zufallszahlen generiert (standard mäßig wird ISAAC verwendet). Das kann Auswirkungen auf Geschwindigkeit und/oder Mißerfolg haben, man vergleicht dann eventuell Äpfel mit Birnen. Zumindest liefert das einen Ansatz für die festgestellten Unterschiede, da die eigentlichen ECM-Routinen sind unverändert sind.
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2611
Erhaltene Danke: 1400

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 02.07.12 21:44 
Hallo,
mit Hilfe der MPArith-Units von Wolfgang Erhardt enthält das Programm jetzt auch die Faktorisierung mittels elliptischer Kurven. Nach Probedivisionen und dem Brent-Rho-Verfahren wird nun zusätzlich mit dieser sehr schnellen Methode nach Teilern gesucht.
Viel Spaß beim Testen.
Mathematiker

Nachtrag: Da ich nur verkürzte Units im Text hatte, ist der Quelltext vorerst entfernt. Entschuldigung!
Nachtrag 2: Der Quelltext enthält jetzt in den Fremdunits alle Kommentare.
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 18:52, insgesamt 2-mal bearbeitet
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Di 03.07.12 11:22 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Hallo,
mit Hilfe der MPArith-Units von Wolfgang Erhardt enthält das Programm jetzt auch die Faktorisierung mittels elliptischer Kurven.

Hallo Mathematiker, leider habe ich mit Bedauern festgestellt, daß Du total verstümmelte Versionen meiner Units verteilst. Die von mir verwendete Zlib-Lizenz ist zwar sehr liberal, aber auch sehr deutlich:

Englisches Original: Altered source versions must be plainly marked as such, ... und deutsch Geaenderte Quellcodes muessen deutlich als solche gekennzeichnet werden ...

Du hast zB aus den Units mp_base, mp_types etc praktisch alle Kommentare, Dokumentation etc gelöscht, ohne das da Du das jeweis deutlich gekennzeichnet hast. Ich bitte ich, also im Sinne von Opensource dies zu unterlassen, oder bei jedem Entfernen/Löschen das deutlich zu kennzeichnen.

Was hast Du eigentlich für ein Problem mit den Kommentaren und Dokus? Warum kannst Du nicht die Original-Sourcen beipacken?

Mit nachdenklichen Grüßen
Wolfgang Ehrhardt
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2611
Erhaltene Danke: 1400

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Di 03.07.12 11:28 
user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:

Hallo Mathematiker, leider habe ich mit Bedauern festgestellt, daß Du total verstümmelte Versionen meiner Units verteilst.

Sorry, mein Fehler. Ich werde, dies umgehend ändern.
Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Di 03.07.12 12:27 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:

Hallo Mathematiker, leider habe ich mit Bedauern festgestellt, daß Du total verstümmelte Versionen meiner Units verteilst.

Sorry, mein Fehler. Ich werde, dies umgehend ändern.
Beste Grüße
Mathematiker

Danke!

Übrigens sind bei Deiner Aktion (nennt man wohl euphemistisch-denglisch Refaktoring?) gerade die für Delphi interessanten Ansistring-Routinen den Bach 'runtergegangen, zB das schnelle subquadratische mp_radix_astr, Du brauchst also nicht immer über lokale Shortsrings und Pcharszu gehen; aber wenn man alle Hinweise löscht, was die Routinen eigentlich machen, kann sowas schon mal vorkommen :) wie zB in
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
var n: mp_int;
    s:array[0..255of char;
begin
    mp_random_randomize;
    mp_init(n);
    strpcopy(s,bb);
    mp_read_radix(n,s,10);
...
einfach mp_read_decimal_astr(n,bb). Im übrigen scheint das lokale mp_random_randomize genauso kontraproduktiv wie mehrmaliges aufrufen des normalen Delphi randomize. Besser einmal global, oder noch besser die Datei mp_conf.inc beilegen und {$define MPC_Randomize} setzen.

Gruß Gammatester