Rechenkraft.net e.V.

die erste Adresse für Distributed Computing
Unterstütze Rechenkraft.net e.V.
Mit Suchkraft hier suchen:
 
It is currently 26.11.14 17:07

All times are UTC + 1 hour [ DST ]




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: Fragen zu "ECM"
Unread postPosted: 05.11.09 19:01 
Offline
Vereinsmitglied
Vereinsmitglied
User avatar

Joined: 25.08.06 14:42
Posts: 1165
Location: Mannheim
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*


Top
 Profile  
 
 Post subject: Re: Fragen zu "ECM"
Unread postPosted: 05.11.09 22:08 
Offline
Vereinsvorstand
Vereinsvorstand
User avatar

Joined: 17.12.02 14:09
Posts: 6800
Location: Berlin
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

Image Image


Top
 Profile  
 
 Post subject: Re: Fragen zu "ECM"
Unread postPosted: 06.11.09 06:41 
Offline
Vereinsmitglied
Vereinsmitglied
User avatar

Joined: 25.08.06 14:42
Posts: 1165
Location: Mannheim
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.


Top
 Profile  
 
 Post subject: Re: Fragen zu "ECM"
Unread postPosted: 13.11.09 15:44 
Offline
XBOX360-Installer
XBOX360-Installer

Joined: 26.02.08 21:45
Posts: 68
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...


Top
 Profile  
 
 Post subject: Re: Fragen zu "ECM"
Unread postPosted: 14.12.09 12:13 
Offline
Vereinsmitglied
Vereinsmitglied
User avatar

Joined: 25.08.06 14:42
Posts: 1165
Location: Mannheim
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!

Image


Top
 Profile  
 
 Post subject: Re: Fragen zu "ECM"
Unread postPosted: 17.02.10 21:07 
Offline
Vereinsmitglied
Vereinsmitglied
User avatar

Joined: 25.08.06 14:42
Posts: 1165
Location: Mannheim
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:
P-1 found a factor in stage #1, B1=25000.
2^6286456+40291 has a factor: 6830498069971913


sondern als

Code:
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!

Image


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC + 1 hour [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group