frage mit saugrossen zahlen

borg schrieb:

allerdings dauert das schon bei 2 "mittelgroßen" ( 10^20 bis 10^25 ) primzahlen so lange, dass du nicht fertig bist, bevor unsere universum schon längst nicht mehr existiert :p

Falsch. 80-stellige Zahlen gehen ganz schnell. http://mathworld.wolfram.com/news/2003-12-05/rsa/

TheTester

allgemein
*********

Der "repeated squaring Algorithmus" erinnert mich so ziemlich an das "binäre Potenzieren".

Mich würde jetzt mal interessieren welchen Algorithmus die Compilerbauer implementiert haben um Potenzen zu berechnen, die pow funktion übernimmt ja doubles also auch schon recht große Zahlen.

bye

tt

TheTester schrieb:

Mich würde jetzt mal interessieren welchen Algorithmus die Compilerbauer implementiert haben um Potenzen zu berechnen, die pow funktion übernimmt ja doubles also auch schon recht große Zahlen.

das sind ja keine exakten Werte. Dann gehts mit a^b = exp(b*ln(a)) für a != 0.

borg

Quatsch schrieb:

Falsch. 80-stellige Zahlen gehen ganz schnell. http://mathworld.wolfram.com/news/2003-12-05/rsa/

dann definier mir bitte "ganz schnell".
es gibt 2 möglichkeiten einen mit rsa verschlüsselten text zu entschlüsseln.
1. raten der faktorisierung
und 2. raten vom schlüssel den der jenige besitzt, der den text verschlüsselt hat.

also sagen wir mal p,q haben 20 bis 30 stellen. p*q habe 50 stellen.
jetzt stellt sich die frage wieviele primzahlen gibt es zwischen 1 und 10^50?

dafür gibt es eine annäherung die besagt: "Es gibt unterhalb von x ca. x/ln(x) primzahlen. diese annäherung heißt "PI"
PI(10^30) ~= 10^30/ln(1030) = 10^30/30*ln(10) > 10^28

jetzt hab ich also 2 möglichkeite
1. ich probiere 10^28 zahlen
2. ich gehe 10^50 zahlen durch und probiere ob es zufällig der schlüssel ist.

alter der erde in sekunden: 1.5*10^17
wenn du es also schafst einen algorithmus zu schreiben, der in 0,000000000001 sekunden aus einer primzahl einen schlüssel macht und diesen mit dem text ausprobiert, dann bist du fertig wenn unsere erde doppelt so alt ist, wie sie atm ist.

man unterschätzt die größe einer zahl wie "10^30" schnell.

borg schrieb:

Quatsch schrieb:

Falsch. 80-stellige Zahlen gehen ganz schnell. http://mathworld.wolfram.com/news/2003-12-05/rsa/

dann definier mir bitte "ganz schnell".

Gib mir eine 60-stellige Zahl (60 Stellen im Dezimalsystem) mit 2 Primfaktoren, und ich faktorisiere sie dir in max. 3 Stunden.

borg schrieb:

jetzt hab ich also 2 möglichkeite
1. ich probiere 10^28 zahlen
2. ich gehe 10^50 zahlen durch und probiere ob es zufällig der schlüssel ist.

alter der erde in sekunden: 1.5*10^17
wenn du es also schafst einen algorithmus zu schreiben, der in 0,000000000001 sekunden aus einer primzahl einen schlüssel macht und diesen mit dem text ausprobiert, dann bist du fertig wenn unsere erde doppelt so alt ist, wie sie atm ist.

man unterschätzt die größe einer zahl wie "10^30" schnell.

Man hat diese zwei Möglichkeiten, aber nicht nur diese zwei Möglichkeiten. Es gibt viel schnellere Faktorisierungsalgorithmen als Brute Force.

volkard

borg schrieb:

jetzt hab ich also 2 möglichkeite
1. ich probiere 10^28 zahlen
2. ich gehe 10^50 zahlen durch und probiere ob es zufällig der schlüssel ist.

google doch mal nach "pollard rho" und vor allem nach "a tale of two sieves".

borg

ok, vergesst meine letzten beiden beiträge. ich hab grad mit mathematica eine 39 stellige zahl in 4 sekunden faktorisiert. auf meinem laptop (celeron 1ghz!). da war ich wohl einfach nicht up2date, vor ~5 jahren war das imo noch völlig sicher mit zahlen in dieser größenordnung.
asche auf mein haupt

Jester

Eine andere Möglichkeit das Problem zu knacken wäre auch modulo 2 und modulo 5 zu lösen. Dann hat man's mit dem chineischen Restsatz schon modulo 10.

MfG Jester

use fucking LONGLONG! bastard

Genau das hat er ja vor, mit long long auszukommen, du Spaten.