Primfaktorzerlegung bei 151 Stelligem Produkt aus 2 Primzahlen
Hallo erstmal :) In Informatik gab uns unser Lehrer seinen "RSA Public key", den man braucht um Nachrichten zu kodieren. Diese Zahl ist 151 Dezimalstellen lang und ist das Produkt von 2 Primzahlen. Die Aufgabe ist jetzt diese Beiden Primzahlen, welche die Faktoren der 151 stelligen Zahl sind herauszufinden. Hat jemand eine Idee, wie man das anstellen könnte, oder wie viele Bit die Verschlüsselung stark ist? Danke im Voraus! :) P,S; die Zahl lautet: 19149104522157777914518142786658323647594273709216144656238580509691987587413882641662966440441691453
5 Antworten
Nimm die Zahl und zieh daraus die Wurzel und runde ab. Jetzt addiere 1 und quadriere das Ergebnis. Davon ziehst du nun deine Ausgangszahl ab. Wenn es sich beim Ergebnis um ein Quadrat handelt, bist du fertig, ansonsten nochmal 1 addieren und von vorne beginnen. Das könnte so aussehen: Ausgangszahl die du faktorisieren willst : 143, die Wurzel daraus und abgerundet ist 11. jetzt 1 drauf addieren : 12 Das wird nun Quadriert und die Ausgangszahl abgezogen: 12^2 -143 =1 bei der 1 handelt es sich um eine Quadratzahl. dann sind deine beiden Primfaktoren: x= 12-1=11 und y=12+1=13. Das ist ein einfacher Algorithmus, der vor allem dann sinnvoll ist, wenn die beiden Faktoren nah beieinander liegen. Dennoch ist es nicht besonders effektiv. Aber besser als bloßes testen. Natürlich gibt es geeignetere Verfahren, diese würden aber den Rahmen hier sprengen. Effektiver sind die Rho-Methode und die p-1 Methode. Einfach mal danach googeln. Ich denke die Frage deines Lehrers war eher als Scherz gedacht. Selbst Hochleistungsrechner brauchen ewig um große Zahlen zu faktorisieren. Deshalb ist die RSA Verschlüsselung im Moment noch sicher.
Tja, scripte eine for schleife die die zahl immer und immer wieder mit % teilt (so das rest angezeigt wird) und scripte eine if bedingung, dass wenn der rest nulll ist die zahl ausgegeben werden soll, Da die zahl produkt zweier primzahlen ist hat sie auch sonst keine teiler
Würde das so einfach gehen, dann wäre Online-Banking nicht mehr sicher. Hier steckt schließlich die Sicherheit der RSA-Verschlüsselung drin. Das zu knacken ist nur möglich, mit sehr viel Rechenzeit, bzw. einem Quanten-Computer, den es sehr wahrscheinlich im Moment noch nicht gibt.
Die Frage ist zwar schon lange nicht mehr aktuell, aber ich möchte das nicht unwiedersprochen so stehen lassen. Die Aufgabe ist weder unmöglich noch schwierig zu lösen und es war ganz sicher kein 'Gag' des Lehrers. Ja, rsa ist sicher aber es kommt natürlich auf die Schlüssellänge an. Momentan wählt man ca. 600 stellige Primzahlen aus; das Produkt ist dann über 1000 Stellen lang und in der Tat nicht realistisch zu refaktorisieren. Aber wenn das Produkt lediglich eine 151 stellige Zahl ist, ist es gar kein Problem das zu 'hacken'.
Das ist eine theoretische Frage, die überhaupt keine praktische Relevanz hat! Ich würde mich mit solchem Nonsens nicht abgeben. Ausserdem hat Monster1965 absolut Recht!
Eine typische Ulrich-Nagel-Antwort.
Und dann verweist U.N. auch noch auf die Antwort von Monster1965, in der genau drinsteht, warum solche Überlegungen von praktischer Relevanz sind: Außer in Sonderfällen ist so eine Zerlegung nur mit enormem Aufwand möglich (dies zu erkennen war möglicherweise der Sinn der Aufgabe), und dies wiederum ist Grundlage moderner Verschlüsselungsverfaren.