| Autor |
Beitrag |
Gammatester
 
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Fr 29.06.12 10:50
 Lelf hat folgendes geschrieben  : | 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  , siehe Prize Problems).
|
|
Mathematiker 
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Fr 29.06.12 11:14
Hallo Gammatester,
| Gammatester hat folgendes geschrieben : | | 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
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Fr 29.06.12 11:37
| Mathematiker hat folgendes geschrieben : | .. 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
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 Narses: Beiträge zusammengefasstIch 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
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Di 03.07.12 11:22
| Mathematiker hat folgendes geschrieben : | 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
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Di 03.07.12 11:28
| Gammatester hat folgendes geschrieben : |
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
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Di 03.07.12 12:27
| Mathematiker hat folgendes geschrieben : | | Gammatester hat folgendes geschrieben : |
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
  Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| var n: mp_int;
s:array[0..255] of 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
|
|
|
