Rechenkraft.net e.V.

Hi,

ich bin durch yoyo@home auf Projekte aufmerksam geworden die u.a. ECM-Software nutzen. Jetzt hab' ich da ne kurze Frage:

Ist es so, dass die Erhöhung des B1-Wertes den ich eingebe die Wahrscheinleichkeit erhöht dass ich in einer Kurve die berechnet wird einen Faktor finde? (Das ganze ist ja anders als Sieve-Software wohl auch vom Zufall ['Sigma'?]abhängig)
Wäre nett wenn mir da jemand weiter helfen könnte.
... es kommen bestimmt noch ein paar weitere Fragen, zur Zeit reicht mir aber die hier *g*

Dann versuch ich als nicht Mathematiker mal so zu erklären wie ich es verstanden habe.

Echte Faktorisierung von Zahlen ist super aufwändig und verlangt enorm viel Rechenzeit, mehrere Monate.

Irgendwann hat dann mal ein Mathematiker heraus gefunden, dass man mit elliptischen Kurven eine Art Trial-Faktorisierung machen kann und damit mit relativ wenig Rechenzeit eine hohe Wahrscheinlichkeit hat bis zu 70-stellige Faktoren zu finden. Also man versucht mal was und hat evtl. Glück. Ich stell mir das wie eine Monte Carlo Methode vor. Das geht mit sehr sehr viel weniger Rechenleistung und wenn es einen bis zu 15 stelligen Faktor gibt, dann findet man ihn mit 80% iger Wahrscheinlichkeit auch mit B1=2000 und 30 Kurven.
- 20stelligen Faktor mit B1=11000 und 80 Kurven.
- 25stelligen Faktor mit B1=50000 und 200 Kurven.
- usw.
Komplette Tabelle und BEschreibung hier: http://xyyxf.at.tut.by/how.html#0

Es macht also Sinn einige ECM Kurven mit den einzelnen B1 laufen zu lassen, bevor man die Zahl mit GNFS, SNFS richtig faktorisiert. Der kleine ECM Aufwand lohnt sich, da man sich dann das monatelange NFS an dieser Zahl spart.

Weiteres zu ECM im MersenneWiki: http://www.mersennewiki.org/index.php/ECM

yoyo

OK,
bedeutet also der B1-Wert gibt die Maximalgröße an die der Faktor haben kann.

mit B1=11000 kann ich also Faktoren finden die 20 und weniger stellen haben.
mit B1=43000000 dann enstprechend Faktoren die 50 und weniger stellen haben (also auch die die man rein theoretisch schon bei B1=11000 finden könnte, so fern es dort einen Faktor gibt).
Entsprechend müssen dann aber mehr Kurven durchlaufen werden, um eine eingermaßen hohe Wahrscheinlichkeit zu haben.

Es geht mir übrigens tatsächlich um XYYXF , war mir mit den Infos auf der Seite aber nicht 100% sicher.

Danke für die schnelle Antwort.

Hallo!
Ganz so einfach ist es nun nicht.

Die Methode mittels elliptischer Kurven zu faktorisieren (ECM) ist i.W. eine Verallgemeinerung einer anderen Methode (p-1-Faktorisierung). Ich gehe zuerst kurz auf diese ein, und dann nochmal kurz zurück zu ECM:

Ohne jetzt auf die math. Feinheiten einzugehen, funktioniert diese p-1-Methode bei der Faktorisierung einer nat. Zahl n so:

Das Verfahren findet einen Primfaktor p von n, wenn in der Primfaktorzerlegung von p-1 jede auftretende Primzahlpotenz kleiner oder gleich B1 ist, oder wenn dies wenigstens für alle bis auf die größte Primzahl zutrifft, und die kleiner oder gleich B2 ist.

Damit hängt die Größe der auffindbaren Faktoren p von n eben NICHT direkt von B1 ab! Aber natürlich können mit größerem B1 auch größere Faktoren gefunden werden. Und "im Normalfall" kann man davon ausgehen, dass ein "typischer" Primfaktor p gegebener Größe sich auch mit einem entspr. gewählten B1 finden lassen...


ECM funktioniert nun recht ähnlich. Nur geht diesmal nicht nur das B1 in die Rechnung ein, sondern auch die Elliptische Kurve, auf der man rechnet. Der Vorteil gegenüber dem P-1-Faktorisiern ist, dass wenn dieses schief geht, man größere Schranken B1 braucht, um weiter nach einem Faktor zu suchen. Bei ECM wechselt man einfach die Kurve und versucht es erneut.

Dabei wird für eine gegebene Größenordnung, die man zzum zu findenden Faktor p erwartet, nicht nur ein "typisches" B1 angegeben, sondern auch eine Anzahl an zu berechnenden Kurven. Diese Anzahl wird so ermittelt, dass die Wsk., dass man einen entspr. Faktor durch diese Rechnung nicht findet, bei 1/e, rund 30% ist. Dies ist insofern ausreichend, weil man dann auf die nächst höhere Stufe (größeres B1) wechselt, und mit den Berechnungen dort, die auch größere Faktoren finden können, den fehlenden Rest (weitestgehend) abgdeckt...

Tja, das dürfte dann soweit meine Fragen geklärt haben! Danke!

Hab ne weitere Frage, die zwar P-1 betrifft, aber das ist ja in der GMP-ECM-Software beinhaltet, bzw. die Frage gilt auch für ECM.
Wie kann ich mir nen gefundenen Faktor im Detail ausgeben lassen?
also nicht nur sondern als
?

bzw. kann ich mir den Faktor so auch über Prime95/mprime anzeigen lassen?