Wieviele Primzahlen in 256Bit? < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Schätzen Sie ab, wieviele Primzahlen mit 256 Bit Länge es gibt. (Eine Primzahl ist 256 Bit lang, wenn das höchstwertige, ganz links stehende Bit 1 ist und von 255 weiteren Binärstellen gefolgt wird.).
Benutzen Sie die einfache Gaußsche Abschätzung der π-Funktion und stellen Sie Ihre Rechenschritte nachvollziehbar dar.
Stellen Sie die Abschätzung als 10er Potenz dar! |
Hallo,
hier ist mein Ansatz zur Lösung des Problems...irgentwie scheint mir das nicht ganz geheuer...
Nach der einfachen Abschätzung von Gauß gilt, dass die Menge der Primzahlen <=x, wenn:
[mm] \pi [/mm] (x) [mm] \sim \bruch{x}{ln x}
[/mm]
Setzte ich jetzt für x [mm] 2^{256} [/mm] ein, so erhalte ich 6,525 * [mm] 10^{74} [/mm]
Aber das kann doch nicht die Aufgabe gewesen sein, oder? Heißt dass, dass in 2^256 Bit ca. 6,525 * [mm] 10^{74} [/mm] Primzahlen vorhanden sind? Über einen Denkansatz würde ich mich freuen!
|
|
| |
|
Hallo Major,
alles ist gut.
> Schätzen Sie ab, wieviele Primzahlen mit 256 Bit Länge es
> gibt. (Eine Primzahl ist 256 Bit lang, wenn das
> höchstwertige, ganz links stehende Bit 1 ist und von 255
> weiteren Binärstellen gefolgt wird.).
>
> Benutzen Sie die einfache Gaußsche Abschätzung der
> π-Funktion und stellen Sie Ihre Rechenschritte
> nachvollziehbar dar.
>
> Stellen Sie die Abschätzung als 10er Potenz dar!
> Hallo,
>
> hier ist mein Ansatz zur Lösung des Problems...irgentwie
> scheint mir das nicht ganz geheuer...
>
> Nach der einfachen Abschätzung von Gauß gilt, dass die
> Menge der Primzahlen <=x, wenn:
>
> [mm]\pi[/mm] (x) [mm]\sim \bruch{x}{ln x}[/mm]
>
> Setzte ich jetzt für x [mm]2^{256}[/mm] ein, so erhalte ich 6,525 *
> [mm]10^{74}[/mm]
>
> Aber das kann doch nicht die Aufgabe gewesen sein, oder?
> Heißt dass, dass in 2^256 Bit ca. 6,525 * [mm]10^{74}[/mm]
> Primzahlen vorhanden sind? Über einen Denkansatz würde
> ich mich freuen!
Du zählst hier auch alle Primzahlen mit, die weniger als 256 bit lang sind. Das solltest Du noch korrigieren. Ansonsten: alles ok soweit!
Grüße
reverend
|
|
|
| |
|
Ah, ok! das heißt alle Zahlen 2^256 - 2^255? Da ja die Gaußsche Abschätzung alle Zahlen BIS 2^256 liefert. Also wäre Quasi die Menge aller Prinzahlen [mm] 2^{256} [/mm] = [mm] 2^{256} \cap 2^{255} [/mm] richtig?
Konkret: [mm] \pi (2^{256}) [/mm] - [mm] \pi (2^{255}) [/mm] = [mm] 6,525^{74} [/mm] - [mm] 3,276^{74} [/mm] = [mm] 3,249^{74}
[/mm]
ist das so richtig oder hab ich etwas übersehen?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:33 Di 04.02.2014 | | Autor: | felixf |
Moin!
> Ah, ok! das heißt alle Zahlen 2^256 - 2^255? Da ja die
> Gaußsche Abschätzung alle Zahlen BIS 2^256 liefert. Also
> wäre Quasi die Menge aller Prinzahlen [mm]2^{256}[/mm] = [mm]2^{256} \cap 2^{255}[/mm]
> richtig?
Sozusagen.
> Konkret: [mm]\pi (2^{256})[/mm] - [mm]\pi (2^{255})[/mm] = [mm]6,525^{74}[/mm] -
> [mm]3,276^{74}[/mm] = [mm]3,249^{74}[/mm]
Schreib da bitte [mm] $\approx$ [/mm] und nicht $=$!
> ist das so richtig oder hab ich etwas übersehen?
Das schaetzt die Anzahl der Primzahlen mit 255 Bits ab.
Du suchst die Anzahl der Primzahlen mit 256 Bits.
(Hinweis: die groesste Zahl mit 256 Bits ist [mm] $2^{257}-1$.)
[/mm]
LG Felix
|
|
|
| |
|
Ah ok, dann lautet die richtige Lösung:
[mm] \pi [/mm] (x) [mm] \sim (2^{257} [/mm] -1) - [mm] (2^{256} [/mm] -1)
da ja die größte Zahl mit 255 Bit [mm] 2^{256} [/mm] -1 lauten müsste. Ist das so ok? (das ausrechnen habe ich mir mal hier erspart).
|
|
|
| |
|
Hallo nochmal,
> Ah ok, dann lautet die richtige Lösung:
>
> [mm]\pi[/mm] (x) [mm]\sim (2^{257}[/mm] -1) - [mm](2^{256}[/mm] -1)
>
> da ja die größte Zahl mit 255 Bit [mm]2^{256}[/mm] -1 lauten
> müsste. Ist das so ok? (das ausrechnen habe ich mir mal
> hier erspart).
Naja, bis auf die Notation...
Aber wir wissen schon, was Du meinst.
Ansonsten ist der skizzierte Lösungsweg jetzt richtig.
Wenn Du willst, schreibs nochmal korrekt auf; muss aber nicht. 
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:54 Di 04.02.2014 | | Autor: | felixf |
Moin,
> > Ah ok, dann lautet die richtige Lösung:
> >
> > [mm]\pi[/mm] (x) [mm]\sim (2^{257}[/mm] -1) - [mm](2^{256}[/mm] -1)
> >
> > da ja die größte Zahl mit 255 Bit [mm]2^{256}[/mm] -1 lauten
> > müsste. Ist das so ok? (das ausrechnen habe ich mir mal
> > hier erspart).
>
> Naja, bis auf die Notation...
... und bis auf die nicht mehr auftauchenden Logarithmen 
LG Felix
|
|
|
| |
|
So ich wollte jetzt die Aufgabe fertig machen, dabei ist mir aufgefallen, dass ich zu wenig Ahnung von der Informatik-Komponente habe. Ich bräuchte mal nen Tip, warum (2^257)-1 die höhste Zahl in 2^256 ist...
Analog habe ich die Aufgabe mal mit 8 Bit gemacht, da man da auch mal nen paar übersichtliche Ergebnisse hat:
Mit 8 Bit lassen sich 256 Zahlen von 0-255 darstellen. Jetzt möchte ich alle Primzahlen mit 8 Bit Länge erhalten:
Die größte Zahl mit 8 Bit ist [mm] (2^9)-1 [/mm] weil (???). Die Anzahl der Primzahlen von [mm] (2^9)-1 [/mm] nach Gauß lautet: [mm] pi(2^9-1) [/mm] ~ 511/ln(511) ~ 81,94
Davon ziehe ich alle Primzahlen mit bis zu 7 Bit ab:
[mm] pi(2^8-1) [/mm] ~ 255/ln(255) ~ 46,02
Also:
[mm] pi(2^9-1) [/mm] - [mm] pi(2^8-1) [/mm] ~ 35,92
Soweit alles korrekt? Wenn ja: Warum ist jetzt [mm] 2^9-1 [/mm] die größte Zahl mit 8 Bit, wenn ich doch nur Zahlen bis 255 darstellen kann?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:47 Do 06.02.2014 | | Autor: | Hing |
hi,
Vorab:
[mm] X_2 [/mm] Binärzahl
[mm] X_{10} [/mm] Dezimalzahl
Kleines Beispiel:
[mm] 0111_2=0*2^3+1*2^2+1*2^1+1*2^0=7_{10} [/mm]
(Umrechnung Binär in Dezimal. Die Potenzen geben die Stellen in der Zahl an bzw. Wertigkeit, angefangen bei Null)
[mm] 1000_{2}=1*2^3+0*2^2+0*2^1+0*2^0=8_{10}
[/mm]
Oder [mm] 1000_{2}-0001_{2}=0111_{2} [/mm] oder [mm] 2^{3}-2^0=7
[/mm]
Umgedacht auf deine Frage: [mm] 2^{257 (Bitstellen)}-2^0=2^{256 (Bitstellen)} [/mm] (voller Einsen)
Wenn du noch weiterlesen willst: Dualzahlen oder Binärzahlen suchen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:19 Do 06.02.2014 | | Autor: | felixf |
Moin!
> hi,
>
> Vorab:
> [mm]X_2[/mm] Binärzahl
> [mm]X_{10}[/mm] Dezimalzahl
>
> Kleines Beispiel:
> [mm]0111_2=0*2^3+1*2^2+1*2^1+1*2^0=7_{10}[/mm]
> (Umrechnung Binär in Dezimal. Die Potenzen geben die
> Stellen in der Zahl an bzw. Wertigkeit, angefangen bei
> Null)
>
> [mm]1000_{2}=1*2^3+0*2^2+0*2^1+0*2^0=8_{10}[/mm]
>
> Oder [mm]1000_{2}-0001_{2}=0111_{2}[/mm] oder [mm]2^{3}-2^0=7[/mm]
>
> Umgedacht auf deine Frage: [mm]2^{257 (Bitstellen)}-2^0=2^{256 (Bitstellen)}[/mm]
> (voller Einsen)
>
> Wenn du noch weiterlesen willst: Dualzahlen oder
> Binärzahlen suchen
Was man hier auch nie vergessen sollte zu erwaehnen ist die ![[]](/images/popup.gif) geometrische Summenformel: [mm] $\sum_{i=0}^n q^i [/mm] = [mm] \frac{q^{n+1} - 1}{q - 1}$. [/mm] Setzt du hier $q = 2$ ein, so bekommst du [mm] $2^n [/mm] + [mm] 2^{n-1} [/mm] + [mm] \dots [/mm] + [mm] 2^1 [/mm] + [mm] 2^0 [/mm] = [mm] \sum_{i=0}^n 2^i [/mm] = [mm] \frac{2^{n+1} - 1}{2 - 1} [/mm] = [mm] 2^{n+1} [/mm] - 1$.
LG Felix
|
|
|
|
