frage mit saugrossen zahlen

volkard

hi, ich will gerade für ein primzahlenexperiment, in dem ich mir erlaube, die lezten 9 ziffern bei manchen anlässen fallen zu lassen, die letze ziffer von 2^1000000000 zu finden (nachdem die letzen 9 ziffern wegfielen) (ich rechne intern erstmal stat mit basis 2^32 mit basis 10^9). um genau zu sein, weil ich sogar n*9 zoiffern fallen lassen und erstmal beobachten, wo das sinn macht. aber dazu später, nach den beobachtungen. also ich kann mit karatsuba in einigermaßen gescheiter zeit versuchen, 2^1000000000 zu errechnen. mit fft geht's zwar schneller aber ich habe irgendwie die genauigkeit nicht in der hand. fremde libs mag ich nur ungern anfassen, aber mir bleibt wohl keine andere wahl, oder?

Abbadon

Willst du nur die letzte Ziffer von 2^1000000000 haben? Das kann man doch fast im Kopf rechnen.
1000000000 mod 4 = 0 also ist die letzte ziffer von 2^1000000000 eine 6.

volkard

Abbadon schrieb:

Willst du nur die letzte Ziffer von 2^1000000000 haben? Das kann man doch fast im Kopf rechnen.
1000000000 mod 4 = 0 also ist die letzte ziffer von 2^1000000000 eine 6.

dem kann ich nicht folgen. warum keine 4 wie in 6738326782369864 ?
aber ich suche die zehntletze, also die 6 in 673832(6)782369864.

Code es halt in Java, da hast du die BigInteger-Klasse als nicht-fremde Lib und die bietet sogar Funktionen, um abzuschätzen, ob etwas eine Primzahl ist, womit du dein Ergebnis dann überprüfen kannst.
Und wenn ich mich nicht ganz täusche, wird die Zahl sogar intern im 2er Komplement repräsentiert, vielleicht nützt dir das was.

http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html

Abbadon

volkard schrieb:

Abbadon schrieb:

Willst du nur die letzte Ziffer von 2^1000000000 haben? Das kann man doch fast im Kopf rechnen.
1000000000 mod 4 = 0 also ist die letzte ziffer von 2^1000000000 eine 6.

dem kann ich nicht folgen. warum keine 4 wie in 6738326782369864 ?
aber ich suche die zehntletze, also die 6 in 673832(6)782369864.

Wenn mann sich die letzte Ziffer von 2^n anguckt also die folge (2^n mod 10), dann sieht man, dass sie periodisch ist (kann man auch allgemein zeigen für b^n mod k) und zwar: (1,2,4,8,6,2,4,8,6,2,4,8,6,...) wenn n durch 4 teilbar ist die letzte Ziffer eine 6. Wenn du die letzten 10 ziffern ausrechnen willst würde das zwar theoretisch auch funktionieren, nur ist die periode wohl ziemlich lang, das würde sich vermutlich nur bei sausausausaugroßen Zahlen lohnen. Ich würde dann einfach 1000000000 in kleinere faktoren a1, ... an zerlegen so dass 1000000000=a1*a2*...*an also 2^1000000000= (...(2^a1)a2)^...an)...) und dass dann modulo 10^10 schrittweise berechnen.

hier stand müll

Abbadon schrieb:

volkard schrieb:

Abbadon schrieb:

Willst du nur die letzte Ziffer von 2^1000000000 haben? Das kann man doch fast im Kopf rechnen.
1000000000 mod 4 = 0 also ist die letzte ziffer von 2^1000000000 eine 6.

dem kann ich nicht folgen. warum keine 4 wie in 6738326782369864 ?
aber ich suche die zehntletze, also die 6 in 673832(6)782369864.

Wenn mann sich die letzte Ziffer von 2^n anguckt also die folge (2^n mod 10), dann sieht man, dass sie periodisch ist (kann man auch allgemein zeigen für b^n mod k) und zwar: (1,2,4,8,6,2,4,8,6,2,4,8,6,...) wenn n durch 4 teilbar ist die letzte Ziffer eine 6. Wenn du die letzten 10 ziffern ausrechnen willst würde das zwar theoretisch auch funktionieren, nur ist die periode wohl ziemlich lang, das würde sich vermutlich nur bei sausausausaugroßen Zahlen lohnen. Ich würde dann einfach 1000000000 in kleinere faktoren a1, ... an zerlegen so dass 1000000000=a1*a2*...*an also 2^1000000000= (...(2^a1)a2)^...an)...) und dass dann modulo 10^10 schrittweise berechnen.

kurz: phi(10) = phi(2*5) = 1*4

borg

x^n kann man ganz gut mit repeated squaring berechnen, dann brauch man nur 2*log(n) schritte.

x^n mod k kann man quasi ohne rechenaufwand berechnen.

zB:

3^81 mod 11

81 = [1  ,0  ,1  ,0  ,0  ,0  ,1  ] <- binär
     [4  ,9  ,3  ,5  ,4  ,9  ,3  ] <- reste
     [x^7,x^6,x^5,x^4,x^3,x^2,x^1]

3^81 mod 11 = 4*3*3 = 3
das geht im kopf.

3^1 = 3 mod 11 = 3
33 mod 11 = 9
99 mod 11 = 4
4*4 mod 11 = 5
usw...

dann müssen nurnoch die teile wo binär eine 1 steht multipliziert werden und schon hat man den rest :p

aber ich könnte wetten mathematica kann das alles viel schneller und besser

volkard

borg schrieb:

x^n kann man ganz gut mit repeated squaring berechnen, dann brauch man nur 2*log(n) schritte.
x^n mod k kann man quasi ohne rechenaufwand berechnen.
...

das ist stark. dann brauche ich ja nur, 2^1000000 mod 10000000000 zu berechnen mit deinem trick. in ner schleife mit etwa 40 multiplikationen. schade, daß 10000000000 nicht mehr in einen 32-bit-int passt. aber egal. ist auf jeden fall millionen mal schneller, als ne langzahl-bibliothek zu verwenden.

Ähm das Prinzip mit der Zerlegung in Restklassenringe ist doch nichts neues? Aber das nützt dir bei Primzahlen nichts. Ich glaube nicht, dass du um die Benutzung einer Langzahlen-Klasse herumkommst.
Das ist ja das, was den RSA sicher macht.

volkard

Optimizer schrieb:

Ähm das Prinzip mit der Zerlegung in Restklassenringe ist doch nichts neues? Aber das nützt dir bei Primzahlen nichts.

borgs trick funktioniert doch bei primzahl^primzahl genauso. welches problem übersehe ich, weshalb du mich zu langzahlklassen bringen willst?

Keine Ahnung, ich kann nicht mehr denken.

borg

Optimizer schrieb:

Das ist ja das, was den RSA sicher macht.

das rsa verfahren wird sicher, weil man die primfaktoren einer multiplikation von 2 großen primzahlen bräuchte um es zu knacken. 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

restklassen gibts natürlich auch bei primzahlen.

Ja, ich merk grad, dass ich seit ungefähr 5, 6 oder 7 Posts an was völlig anderes gedacht habe... lass mich in Ruhe.

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".