10.000$ - 200.000$

[hiroki]

hi!

hab auf http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html gesehen, dass man da 10.000 $ bekommt, wenn man die 174 stellige zahl 188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059 in ihre 2 primfaktoren zerlegt. für die 500undpaar-stellige bekommt man 200.000$!!!!

nun, es werden sich schon ganz andere daran versucht haben, aber man darf ja mal träumen. ich hab ein prog, das zahlen in seine primfaktoren zerlegt... jedoch eben nicht 174-stellige [erstmal einen gescheiten datentypen dafür haben mit der entsprechenden genauigkeit!].
wüsste jemand vielleicht einen "optimalen" algorithmus für die primfaktorzerlegung?
im moment prüfe ich alle ungeraden zahlen von 2 bis zur wurzel der zahl darauf ob die zahl dadurch teilbar ist.. wenn ja: ein primfaktor. wenn nicht: weiterprobieren... der algo ist rekursiv aufgebaut..

hätte sonst noch jemand ne gute/bessere idee?

also die 10000$ zu gewinnen wäre zwar toll, aber für ne 140-stellige zahl wurden 1600 pcs und 8 monate gebraucht (steht auch auf der rsa-page)

[Steup]

http://www.google.de/search?q=cache:0JFI3_ZnUfwC:www.informatik.tu-darmstadt.de/ftp/pub/TI/reports/berger.diplom.ps.gz+primfaktor+generator+200+stellen&hl=de&ie=UTF-8

da les dir ma durch dann weisste ob des überhaupt möglich ist.... naja ich hab keine lust zu rechnen... frag ma nen genie

edit: laut diesem text is der grösste primfaktor 43 stellen als dezimalzahl. dann such ma schön. das kann dein rechner theoretisdch gar nich schaffen...

[Codeq]

also klar ist das man mit normalen datentypen nicht weiter kommt, aber man kann seine zahlen in wertebereiche zerlegen und mit zB Mantisse und exponent arbeiten, was hier aber auch nicht mehr aussreichen wird.
bei der astronomie rechnen die auch mit unmöglich langen zahlen und da musses auch genau sein ... :)
wird schon gehen sowas und mehr als 64 bit kisten haben die auch ned da stehen...

es ist halt wichtig die daten mathematisch zu verdichten um dann mit bruchteilen zu rechnen.
kleines Beispiel.
Angenommen man hat nur eine stelle zur verfügung in einem int datentyp und möchte gerne die zahl 27 darstellen...
da könnte man hier die anzahl der zu ziehenden wurzeln durch eine zahl schreiben.
3^(-3) == 27

man kann also mit 2 int speicherzellen auskommen die jeweils eine 3 beinhalten. sollte man eine primzahl darstellen wollen, dann bekommt man arge probleme teiler von teilen der zahl zu finden die man durch einen 32bit datentyp ausdrücken kann.

und wenn nun ein teil von einem teil von einem teil ... usw... sogar benötigt wird, dann klingt das für mich nach differentialgleichungen mit so vielen unbekannten wie man braucht um eine geeignete zahl zu finden die dann in einen datentyp passt. wobei sich diese zahl nach ein paar neuen teilzahlen wieder neu komprimieren lässt.

naja.. viel spass :)

[Tilion]

hmm einen faktor hab ich jetz nach vieleicht ner halben stunde nachdenken und testen schon, überleg grad ob es schneller geht, wenn ich den anderen schriftlich ausrechne oder noch ne funktion dazu schreibe :/

[Codeq]

wozu gibts rechenknechte?? ;)

http://www.inf.fh-flensburg.de/lang/algorithmen/code/krypto/primtest.htm

[Jan Krüger]

für die ermittlung von primfaktoren gibt es optimierte verfahren, die ein bisschen zeit sparen (dauert immer noch ein paar zich jahre, aber besser ein bisschen gespart als gar nix ;)). ich kenne nur die englischen namen, weil ich mein wissen aus einem englischen buch habe. da wurden zum beispiel das "quadratic field sieve" und das "numeric field sieve" erwähnt. eins von den beiden ist die schnellste methode, die man bis jetzt kennt. aber für das knacken eines hinreichend großen RSA-schlüssels reichts immer noch nicht. also vergiss es.
übrigens, meinst du, die würden ihr geld verschenken? :D

PS. das ermitteln von primfaktoren hat mit dem erzeugen von primzahlen ziemlich wenig zu tun, denn bei einer tausendstelligen primzahl dürftest du mit einem primzahlgenerator recht lange brauchen, um zufällig die richtigen primfaktoren zu finden... :D