Fragen zu "ECM"

GIMPS, Riesel, SOB, PrimeGrid, etc.
Nachricht
Autor
Benutzeravatar
Rincewind
Vereinsmitglied
Vereinsmitglied
Beiträge: 1166
Registriert: 25.08.2006 14:42
Wohnort: Mannheim

Fragen zu "ECM"

#1 Ungelesener Beitrag von Rincewind » 05.11.2009 19:01

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*

Benutzeravatar
yoyo
Vereinsvorstand
Vereinsvorstand
Beiträge: 8045
Registriert: 17.12.2002 14:09
Wohnort: Berlin
Kontaktdaten:

Re: Fragen zu "ECM"

#2 Ungelesener Beitrag von yoyo » 05.11.2009 22:08

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
HILF mit im Rechenkraft-WiKi, dies gibts zu tun.
Wiki - FAQ - Verein - Chat

Bild Bild

Benutzeravatar
Rincewind
Vereinsmitglied
Vereinsmitglied
Beiträge: 1166
Registriert: 25.08.2006 14:42
Wohnort: Mannheim

Re: Fragen zu "ECM"

#3 Ungelesener Beitrag von Rincewind » 06.11.2009 06:41

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.

test123
XBOX360-Installer
XBOX360-Installer
Beiträge: 68
Registriert: 26.02.2008 21:45

Re: Fragen zu "ECM"

#4 Ungelesener Beitrag von test123 » 13.11.2009 15:44

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...

Benutzeravatar
Rincewind
Vereinsmitglied
Vereinsmitglied
Beiträge: 1166
Registriert: 25.08.2006 14:42
Wohnort: Mannheim

Re: Fragen zu "ECM"

#5 Ungelesener Beitrag von Rincewind » 14.12.2009 12:13

Tja, das dürfte dann soweit meine Fragen geklärt haben! Danke!
Ihr sagt DC ist schlecht für die Umwelt? Ich hab Öko-Strom!

Bild

Benutzeravatar
Rincewind
Vereinsmitglied
Vereinsmitglied
Beiträge: 1166
Registriert: 25.08.2006 14:42
Wohnort: Mannheim

Re: Fragen zu "ECM"

#6 Ungelesener Beitrag von Rincewind » 17.02.2010 21:07

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

Code: Alles auswählen

P-1 found a factor in stage #1, B1=25000.
2^6286456+40291 has a factor: 6830498069971913
sondern als

Code: Alles auswählen

6830498069971913 - 1 = 2^3 * 7 * 29 * 73 * 167 * 263 * 307 * 4273
?

bzw. kann ich mir den Faktor so auch über Prime95/mprime anzeigen lassen?
Ihr sagt DC ist schlecht für die Umwelt? Ich hab Öko-Strom!

Bild

Antworten

Zurück zu „Primzahlsuche“