Forums Neueste Beiträge
 

Suche nach schneller Faktorisierung

28/06/2009 - 18:14 von Jan B | Report spam
Einen schönen Tag,

ich habe nun die 13. Jahrgangsstufe abgeschlossen und bin seit heute auf
der Suche nach einem Algorithmus der lange Zahlen (Bitlànge > 1000) in
kurzer Zeit (Sekundenbereich) in seine Primfaktoren zerlegen kann. Dies
soll auf einem normalen Windows-PC geschehen.
Welche Auswirkungen hàtte das Finden eines solchen Algorithmus?
Ist es überhaupt möglich, mit meinen mathemtischen Kenntnissen, einen
solchen Algorithmus zu finden?
Wie bzw. wo sollte man derartige Entdeckungen publizieren?

Mit freundlichen Grüßen,
Jan
 

Lesen sie die antworten

#1 Helmut Richter
28/06/2009 - 18:39 | Warnen spam
On Sun, 28 Jun 2009, Jan B wrote:

ich habe nun die 13. Jahrgangsstufe abgeschlossen und bin seit heute auf
der Suche nach einem Algorithmus der lange Zahlen (Bitlànge > 1000) in
kurzer Zeit (Sekundenbereich) in seine Primfaktoren zerlegen kann. Dies
soll auf einem normalen Windows-PC geschehen.
Welche Auswirkungen hàtte das Finden eines solchen Algorithmus?



Für einen ersten Überblick:
http://de.wikipedia.org/wiki/Faktor...sverfahren

und Links dort. Um mal eine konkrete Zahl zu nennen: Im Jahre 2005 wurde
eine 200-stellige Dezimalzahl (also Bitlànge 665) aus der "RSA Factoring
Challenge" mit einem Rechenaufwand zerlegt, der etwa 75 Jahren auf einem
2-GHz-Prozessor entspricht, nur auf einem Verbund vieler Rechner. Um so
viele Größenordnungen schneller zu sein wàre also ein nicht realistisch zu
erwartender Fortschritt.

Ist die Zahl zufàllig, also nicht extra als schwierig zerlegbar
konstruiert wie die aus der Factoring Challenge, oder weiß man gar vorab
etwas über mögliche Faktoren, kann man natürlich Glück haben und findet
bald große Primfaktoren; eine Zahl als prim oder zusammengesetzt
nachzuweisen ist nàmlich *viel* einfacher als von einer zusammengesetzten
Zahl einen Faktor zu finden. So habe ich mal vor gut 10 Jahren 10^486-1
aus Gaudi zerlegt (nein, das war wirlich nur Gaudi und keine Wissenschaft,
auch damals nicht mehr): http://www.lrz-muenchen.de/~hr/numb/fact486.html

Ist es überhaupt möglich, mit meinen mathemtischen Kenntnissen, einen
solchen Algorithmus zu finden?



Realistischerweise nein.

Wie bzw. wo sollte man derartige Entdeckungen publizieren?



Das Problem stellt sich erst, wenn man eine solche Entdeckung gemacht hat,
also ziemlich sicher gar nicht.

Helmut Richter

Ähnliche fragen