www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Krypto,Kodierungstheorie,Computeralgebra" - Wieviele Primzahlen in 256Bit?
Wieviele Primzahlen in 256Bit? < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Krypto,Kodierungstheorie,Computeralgebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Wieviele Primzahlen in 256Bit?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 00:00 Di 04.02.2014
Autor: Major4189

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!


        
Bezug
Wieviele Primzahlen in 256Bit?: Antwort
Status: (Antwort) fertig Status 
Datum: 01:14 Di 04.02.2014
Autor: reverend

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


Bezug
                
Bezug
Wieviele Primzahlen in 256Bit?: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 22:24 Di 04.02.2014
Autor: Major4189

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?



Bezug
                        
Bezug
Wieviele Primzahlen in 256Bit?: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                                
Bezug
Wieviele Primzahlen in 256Bit?: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 22:48 Di 04.02.2014
Autor: Major4189

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

Bezug
                                        
Bezug
Wieviele Primzahlen in 256Bit?: Antwort
Status: (Antwort) fertig Status 
Datum: 22:53 Di 04.02.2014
Autor: reverend

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


Bezug
                                                
Bezug
Wieviele Primzahlen in 256Bit?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                                        
Bezug
Wieviele Primzahlen in 256Bit?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:04 Di 04.02.2014
Autor: reverend

Moin Felix,

> > > [mm]\pi[/mm] (x) [mm]\sim (2^{257}[/mm] -1) - [mm](2^{256}[/mm] -1)
>
> > Naja, bis auf die Notation...
>  
> ... und bis auf die nicht mehr auftauchenden Logarithmen
> :-)

Ich nehme an, die haben sich so schmal gemacht, dass sie sich hinter dem Relationszeichen verstecken konnten.
Das nennt man einen relativ logarithmischen Maßstab, meine ich. ;-)

LG
rev

Bezug
                                                
Bezug
Wieviele Primzahlen in 256Bit?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:36 Do 06.02.2014
Autor: Major4189

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?

Bezug
                                                        
Bezug
Wieviele Primzahlen in 256Bit?: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                                
Bezug
Wieviele Primzahlen in 256Bit?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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 []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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Krypto,Kodierungstheorie,Computeralgebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]