Mathematik: Faktorisierung großer Zahlen
Released by matroid on Sa. 15. März 2008 17:35:02 [Statistics]
Written by Kay_S - 18316 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Faktorisierungsverfahren



Bekannterweise ist das klassische Problem, die Primzahlen von den zusammengesetzten Zahlen zu unterscheiden, nach heutigem Kenntnisstand sehr effizient lösbar. Als viel schwieriger erweist es sich aber, die komplette Faktorzerlegung einer natürlichen Zahl anzugeben. Obwohl dieses Problem sehr alt und grundlegend ist, muss man tief in die mathematische Trickkiste greifen, um selbst Primfaktoren moderater Länge bestimmen zu können.
Der Artikel beleuchtet klassische und aktuelle Verfahren zur Faktorisierung. Neben den Verfahren selbst stehen Laufzeitanalyse und Hinweise zur effizienten Realisierung auf dem Computer im Mittelpunkt. Am Ende soll auch eine Beispielimplementation einiger dieser Verfahren vorgestellt werden.


0. Überblick


Dass eine natürliche Zahl eine (bis auf die Reihenfolge der Faktoren) eindeutige Primfaktorzerlegung besitzt, hatte schon Euklid etwa 300 v. Chr. gezeigt. Lange Zeit haben sich die meisten Mathematiker auch mit diesem Wissen begnügt; die konkreten Faktoren zu bestimmen war meist die damit verbundene Arbeit nicht wert.
Das änderte sich schlagartig Mitte der 60er Jahre des vorigen Jahrhunderts, als leistungsfähige Computer verfügbar wurden und - etwas später - das RSA-Kryptosystem erfunden wurde. Daraufhin wurde viel Energie in die Erforschung der Problematik und die Entwicklung "guter" Faktorisierungsalgorithmen gesteckt - mit mäßigem Erfolg. Bis heute ist es niemandem gelungen, das Faktorisierungsproblem als effizient lösbar nachzuweisen. Dennoch sollen einige der Ergebnisse bzw. Verfahren in den nachfolgenden Kapiteln besprochen werden:


1. Probedivision
2. Fermat-Faktorisierung
3. Lehman-Algorithmus
4. Pollard-Rho-Verfahren
5. (p-1)-Verfahren
6. Elliptische-Kurven-Methode
7. Quadratisches Sieb
8. Ein Faktorisierungs-Programm in C


Ohne Vollständigkeit zu garantieren sollte der Artikel insgesamt einen guten Überblick liefern.

1. Probedivision


fed-Code einblenden

Verbesserungen

fed-Code einblenden

2. Fermat-Faktorisierung


fed-Code einblenden

Beispiel

fed-Code einblenden

Bild


fed-Code einblenden

Verbesserungen

fed-Code einblenden

Laufzeit

fed-Code einblenden

3. Lehman-Algorithmus


fed-Code einblenden

Laufzeit

fed-Code einblenden

4. Pollard-Rho-Verfahren


fed-Code einblenden

Eine Geburtstagsfolge

fed-Code einblenden

Floyd's Zyklenalgorithmus

fed-Code einblenden

Bild

fed-Code einblenden

Beispiel

fed-Code einblenden

Bild


fed-Code einblenden

Verbesserungen

fed-Code einblenden

Laufzeit

fed-Code einblenden

5. (p-1)-Verfahren


fed-Code einblenden

Beispiel

fed-Code einblenden

Bild


fed-Code einblenden

Eine schnellere Version

fed-Code einblenden

Weitere Verbesserungen

fed-Code einblenden

Laufzeit

fed-Code einblenden

6. Elliptische-Kurven-Methode


fed-Code einblenden

Bild


fed-Code einblenden

Beispiel

fed-Code einblenden

Erweiterungen / Verbesserungen

fed-Code einblenden

Laufzeit

fed-Code einblenden

7. Quadratisches Sieb


fed-Code einblenden

Siebschritt

fed-Code einblenden

Bild


fed-Code einblenden

Auswahlschritt

fed-Code einblenden

Beispiel

fed-Code einblenden

Erweiterungen / Verbesserungen

fed-Code einblenden

Laufzeit

fed-Code einblenden

8. Ein Faktorisierungs-Programm in C


Manchem ist sicher das Unix-Kommando "factor" ein Begriff, das bei Eingabe einer natürlichen Zahl eine Liste der Primfaktoren ausgibt. Leider hat dieses Programm einige Beschränkungen. Zum Beispiel darf die Eingabe die Größe von 64 Bit nicht überschreiten; bei größeren Zahlen wird noch nicht einmal ein einfacher Primtest gemacht.

Daher möchte ich ein kleines Programm vorstellen, das mit diesen Unzulänglichkeiten (endlich!) aufräumt. Man kann es unter folgendem Link herunterladen: factor.zip

Es verwendet die Verfahren Probedivision, Pollard-Rho und ECM, wobei für die Eingabe (theoretisch) keine Beschränkung existiert. Faktoren dürften hier auch deutlich schneller gefunden werden als mit dem gleichnamigen Unixbefehl.

Die Verwendung erfolgt aus dem Programmverzeichnis heraus mit

./factor [Zahl]

unter Linux bzw.

factor [Zahl]

unter Windows. Das Programm liegt auch als C-Quelltext vor, über Hinweise und/oder Verbesserungsvorschläge freue ich mich daher besonders.

Wer stattdessen einmal das QS-Verfahren ausprobieren möchte, kann ja die interessante LISP-Implementierung testen, die in diesem Thread vorgestellt wurde.





Zitierte Artikel



[1] R. S. Lehman: "Factoring Large Integers", Mathematics of Computation 28, 1974, S. 637-646

[2] P. L. Montgomery: "Speeding the Pollard and Elliptic Curve Methods of Factorization", Mathematics of Computation 48, 1987, S. 243-264

[3] P. L. Montgomery: "An FFT Extension of the Elliptic Curve Method of Factorization", Dissertation, University of California, 1992

[4] C. Pomerance: "The Quadratic Sieve Factoring Algorithm", Lecture Notes in Computer Science 209, 1985, S. 169-182

[5] A. K. Lenstra, H. W. Lenstra, Jr.: "The Development of the Number Field Sieve", Lecture Notes in Mathematics 1554, 1993



 
Dieser Artikel ist enthalten in unserem Buch

Mathematisch für fortgeschrittene Anfänger
Mathematisch für fortgeschrittene Anfänger

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Informatik :: Kryptographie :: Elliptische Kurven :: Primfaktorzerlegung :: Primzahlen :: Zahlentheorie :
Faktorisierung großer Zahlen [von Kay_S]  
Ein Artikel über Faktorisierungsverfahren. Es werden der Reihe nach die meisten wichtigen Verfahren vorgestellt und analysiert: Probedivision, Fermat-Faktorisierung, Lehman-Algorithmus, Pollard-Rho-Verfahren, (p-1)-Verfahren, Elliptische-Kurven-Methode, Quadratisches Sieb.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 18316
 
Aufrufstatistik des Artikels
Insgesamt 2750 externe Seitenaufrufe zwischen 2012.01 und 2021.04 [Anzeigen]
DomainAnzahlProz
https://google.com542%2 %
https://duckduckgo.com120.4%0.4 %
https://google.de1585.7%5.7 %
http://google.de179565.3%65.3 %
http://google.ru2177.9%7.9 %
http://google.fr1776.4%6.4 %
http://google.rs953.5%3.5 %
http://google.is341.2%1.2 %
http://google.pl341.2%1.2 %
https://google.ru240.9%0.9 %
http://images.google.de210.8%0.8 %
http://google.it190.7%0.7 %
http://google.com80.3%0.3 %
http://www.bing.com341.2%1.2 %
http://www.bookmerken.de70.3%0.3 %
http://avira.search.ask.com80.3%0.3 %
https://www.bing.com100.4%0.4 %
https://www.ecosia.org50.2%0.2 %
http://de.search.yahoo.com90.3%0.3 %
http://m.c-plusplus.net20.1%0.1 %
http://10.0.0.1:191020.1%0.1 %
http://search.conduit.com10%0 %
http://search.tb.ask.com20.1%0.1 %
http://10.101.1.2:191010%0 %
http://ecosia.org20.1%0.1 %
http://de.images.search.yahoo.com10%0 %
http://cc.bingj.com10%0 %
http://suche.t-online.de60.2%0.2 %
http://www.cs.hs-rm.de10%0 %
http://de.yhs4.search.yahoo.com20.1%0.1 %
http://alicesuche.aol.de10%0 %
http://search.snap.do10%0 %
http://10.69.0.1:191010%0 %
http://de.ask.com10%0 %
http://suche.aol.de10%0 %
http://suche.web.de20.1%0.1 %
http://suche.aolsvc.de10%0 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 4 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.04.19 10:32https://google.com
2021.04.02-2021.04.17 (3x)https://google.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 2667 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2018 (572x)http://google.de/url?sa=t&rct=j&q=
201201-01 (144x)http://google.ru/imgres?q=cotangens tabelle
201206-06 (132x)http://google.fr/imgres?q=rho pollard
201210-12 (113x)http://google.de/url?sa=t&rct=j&q=quadratisches zahlensieb
201311-11 (106x)http://google.de/url?sa=t&rct=j&q=faktorisierung x^2-y^2 fermat
201202-02 (95x)http://google.rs/url?sa=t&rct=j&q=mp faktorisierung großer zahlen
201205-05 (87x)http://google.de/url?sa=t&rct=j&q=wurzel faktorisieren
201211-11 (83x)http://google.de/url?sa=t&rct=j&q=primfaktorzerlegung pollard-rho-algorithmus
201204-04 (83x)http://google.de/url?sa=t&rct=j&q=teilbarkeit große zahlen
201209-09 (80x)http://google.de/url?sa=t&rct=j&q=quadratische zahlensieb
201207-07 (78x)http://google.de/url?sa=t&rct=j&q=siebpolynom
202006-10 (77x)https://google.de/
201301-01 (74x)http://google.de/url?sa=t&rct=j&q=quadratisches sieb software
201401-01 (67x)http://google.de/url?sa=t&rct=j&q=faktorisierung natürlicher zahlen
202005-12 (56x)https://google.de/url?sa=t
201405-05 (56x)http://google.de/url?sa=t&rct=j&q=faktorisieren teiler wurzel
201309-09 (56x)http://google.de/url?sa=t&rct=j&q=definition faktorisieren mathe
201203-03 (54x)http://google.de/url?sa=t&rct=j&q=zahlensieb dauer faktorisierung
201208-08 (54x)http://google.de/url?sa=t&rct=j&q=faktorisierung laufzeit
201304-04 (53x)http://google.de/url?sa=t&rct=j&q=primteiler kleiner als dritte wurzel n
2020-2021 (50x)https://google.com/
201306-06 (45x)http://google.fr/imgres?sa=X&biw=1438&bih=734&tbm=isch&tbnid=D7eUk7043V36QM:
201302-02 (43x)http://google.ru/url?sa=i&rct=j&q=
201305-05 (40x)http://google.de/url?sa=t&rct=j&q=problem der faktorisierung großer zahlen
201411-11 (36x)http://google.de/url?sa=t&source=web&cd=1&ved=0CB0QFjAA
201412-12 (34x)http://google.is/url?sa=t&rct=j&q=
201303-03 (34x)http://google.pl/imgres?start=142&um=1&sa=N&biw=1366&bih=643&authuser=0&tbm=i...
201307-07 (33x)http://google.de/url?sa=t&rct=j&q=pollard roh keine lineare funktionen
201505-05 (30x)http://google.ru/url?sa=t&rct=j&q=
201308-08 (25x)http://google.de/url?sa=t&rct=j&q=fermat zahl 7 pollard rho
202102-02 (24x)https://google.ru/
202103-03 (23x)https://google.de/search?biw=853
2016-2017 (20x)http://images.google.de/url?sa=t&rct=j&q=
201404-04 (19x)http://google.it/search?ei=itA-U-rUAcLoswb21YCgAw&q=rho zahl
201504-04 (19x)http://google.de/url?sa=t&source=web&cd=6&ved=0CC4QFjAF
2020-2021 (10x)https://duckduckgo.com/
201409-09 (10x)http://google.de/url?sa=t&rct=j&q=vorperiode und periode einer zufallsfolge
2017-2018 (8x)http://google.com/search
201304-04 (8x)http://www.bing.com/search?q=nullstellen elliptische funktion primzahl&qs=n&f...
201501-01 (7x)http://www.bookmerken.de/
201307-07 (6x)http://avira.search.ask.com/web?apn_dtid=^YYYYYY^YY^DE&apn_dbr=ff_22.0&itbv=1...
2020-2021 (5x)https://www.bing.com/
201604-04 (5x)http://google.de/url?sa=t&source=web&cd=10&rct=j&q=faktorisierungs programm
2020-2021 (5x)https://www.ecosia.org/
2013-2015 (4x)http://www.bing.com/search?q=matroids mathe faktorisierung&qs=n&form=QBRE&pq=...
201512-12 (4x)http://google.de/url?sa=t&rct=j&q=faktorisierung sehr großer zahlen

[Top of page]

"Mathematik: Faktorisierung großer Zahlen" | 11 Comments
The authors of the comments are responsible for the content.

Re: Faktorisierung großer Zahlen
von: Gockel am: Sa. 15. März 2008 20:17:11
\(\begingroup\)
Hallo Kay.

Ein toller Artikel ist dir da gelungen. Inhaltlich sehr interessant, optisch sehr ansprechend, niemals langweilig. Kurzum: Klasse!

mfg Gockel.\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: spitzwegerich am: Mo. 17. März 2008 01:24:34
\(\begingroup\)
Ein schöner Artikel.

An wichtigen Faktorisierungsmethoden wäre noch das allgemeine Zahlkörpersieb zu nennen.\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Gockel am: Mo. 17. März 2008 16:20:24
\(\begingroup\)
Das wurde doch genannt!?


4) Eine Weiterentwicklung: Das Zahlkörpersieb

Ende der 80er Jahre gelang eine deutliche Verbesserung durch Erfindung des Zahlkörpersiebes. Das Verfahren benutzt algebraische Zahlkörper und erzeugt viel glattere Relationen als das originale QS. Wer sich für dieses Verfahren interessiert, lese z. B. in [5] weiter.

mfg Gockel.\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: spitzwegerich am: Fr. 21. März 2008 00:30:48
\(\begingroup\)
Stimmt, da stehts ja. Hab ich wohl überlesen, sorry.\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Ex_Mitglied_40174 am: So. 23. März 2008 17:16:07
\(\begingroup\)
fed-Code einblenden

Unter welchen Voraussetzungen an die Funktion unter
der Summe/Integral kann man so argumentieren?\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Gockel am: So. 23. März 2008 18:30:33
\(\begingroup\)
Es funktioniert z.B. für alle monoton fallenden, positiven Funktionen.

mfg Gockel.\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Ex_Mitglied_40174 am: So. 23. März 2008 18:51:51
\(\begingroup\)
Hm... auch mit Theta?

Ich glaube zu sehen, dass das Integral dann höchstens
so schnell wächst wie die Summe... aber andersrum?

Hast du vielleicht irgendein Literaturtip für solche Sachen,
evtl noch allgemeiner?

Ich nehm natürlich auch gern nen Beweis :)

\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Kay_S am: So. 23. März 2008 18:59:23
\(\begingroup\)
fed-Code einblenden \(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: slurpslerp am: So. 23. März 2008 19:45:31
\(\begingroup\)
Danke.

Ich hatte das noch nie gesehen so... wie gesagt,
wenn jemand gute Bücher weiss wo solche Sachen drinstehen...
her damit :)\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Ex_Mitglied_40174 am: Mi. 16. April 2008 03:49:06
\(\begingroup\)
Das vorgestellte Programm in factor.zip läuft bei mir unter Windows leider nicht. Ich habe mir den c-code mal angeschaut, die Fehlerabfragen, wenn ich zB eine 0 oder Kommazahlen eingebe funktioniert, wenn ich jedoch 11 oder 1111 eingebe, dann bricht die Berechnung mit einem kleinen Windows Fehler ab. Ist das bei euch auch so? Oder stimmt bei meinen Windows Einstellungen etwas nicht?\(\endgroup\)
 

Re: Faktorisierung großer Zahlen
von: Diophant am: Do. 04. Februar 2021 12:55:11
\(\begingroup\)
Diesen sehr gelungenen Artikel kannte ich bisher noch gar nicht und werde ihn in nächster Zeit einmal gründlich durcharbeiten.

Nur zum vorherigen Kommentar (auch wenn er schon 13 Jahre alt ist 😉 ): unter Windows 10 läuft das Programm nach wie vor in der normalen Windows-Konsole problemlos. In der Windows Powershell muss man wie unter Linux "./factor [Zahl]" eingeben, dann funktioniert es ebenfalls.

Gruß, Diophant\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]