768-Bit Primzahlen

Neue Frage »

27.11.2010, 08:40	Ionel	Auf diesen Beitrag antworten »
768-Bit Primzahlen Hallo Leute, ich bin gerade auf eine Fragestellung gestoßen: Wie kann man abschätzen (oder besser noch ausrechnen) wieviele 768-Bit Primzahlen es gibt und wie viele verschiedene n=p*q existieren wenn p und q jeweils 768-Bit Primzahlen sind. Wäre schön wenn mir jemand helfen kann. Danke schonmal im Vorraus. lg Ionel
27.11.2010, 08:48	kiste	Auf diesen Beitrag antworten »
http://de.wikipedia.org/wiki/Primzahlsatz auf 2^768-1 und 2^767 angewandt
27.11.2010, 08:55	Ionel	Auf diesen Beitrag antworten »
also muss ich für das x= 2^768-1 und 2^767 einsetzen?
27.11.2010, 09:18	Ionel	Auf diesen Beitrag antworten »
Gut, also ich habe mich nochmal ein bisschen eingelesen und habe in den Primzahlsatz eingesetzt. Doch jetzt habe ich ein neues Problem: wie rechne ich nun $\begin{eqnarray} \frac{2^{767}766 }{408302,506} \end{eqnarray*}$
27.11.2010, 09:41	kiste	Auf diesen Beitrag antworten »
Was willst du da rechnen? Ist ne Zahl mit ca. 228 Stellen, welchen Informationsgewinn erhoffst du dir wenn man dir die Zahl gibt?
27.11.2010, 09:51	Ionel	Auf diesen Beitrag antworten »
ja stimmt eigentlich... naja gut, da hab ich schonmal das =) und wie kann ich nun angeben, wieviele verschiedene n=p*q es gibt wenn p und q jeweils 768-Bit Zahlen sind?
Anzeige

27.11.2010, 10:19	Airblader	Auf diesen Beitrag antworten »
Verschiedene Primzahlen führen auch auf echt verschiedene Produkte. Damit ist die Frage rein kombinatorischer Natur. air
27.11.2010, 10:29	Ionel	Auf diesen Beitrag antworten »
Tut mir leid, aber damit kann ich gerade nicht viel Anfragen. Ich hätte die Vermutung das man das vllt. mithilfe einer Permutation rausbekommen kann, aber ich bin mir da nicht so sicher.
27.11.2010, 10:41	Airblader	Auf diesen Beitrag antworten »
Nun, es ist klar, dass wenn n=pq gilt, es keine anderen Primzahlen a, b gibt mit n=ab. Das ist die Eindeutigkeit der Primfaktorzerlegung. Die Frage ist also: Wie viele Möglichkeiten gibt es, aus x Zahlen zwei auszuwählen? Betrachte das Produkt p*q so: Für die erste Stelle (Zahl) hast du x Möglichkeiten und für die zweite Stelle (Zahl) dann auch nochmal x Möglichkeiten (wenn du zulässt, dass p=q gelten darf). Wenn p=q nicht sein darf, dann hast du für die zweite Stelle/Zahl eben noch (x-1) Möglichkeiten. Das ist ganz grundlegende Kombinatorik. Das Urnenmodell kennst du doch sicherlich, oder? air
27.11.2010, 11:00	Ionel	Auf diesen Beitrag antworten »
also hätte ich theoretisch $\begin{eqnarray} x^{10^{228}} x^{10^{228}} \end{eqnarray*}$ möglichkeiten?
27.11.2010, 11:11	Airblader	Auf diesen Beitrag antworten »
Wie kommst du auf diesen wahnwitzigen Exponenten? x ist die Anzahl der "Kugeln in der Urne", also die Anzahl der Zahlen, die du kombinieren kannst. z.B.: Angenommen, es gibt nur x=2 Primzahlen. Dann gibt es offenbar drei Möglichkeiten: Zweimal die 1. Zahl, zweimal die 2. Zahl oder jeweils eine von beiden. Da sehen wir auch gleich den Haken: Die Reihenfolge ist egal. D.h. wir interessieren uns nicht dafür, ob n=pq oder n=qp ist, es ist "das selbe". Auf jeden Fall gibt es nicht (2^(10^228))² Möglichkeiten, wie du zu behaupten scheinst. In der Sprache des Urnenmodells: Wir haben eine Urne ohne Reihenfolge (n = pq = qp) und mit Zurücklegen (n = pp ist erlaubt). Die Urne besteht aus x Kugeln (x ist die Anzahl der zur Verfügung stehenden Primzahlen) und daraus wollen wir n=2 Stück ziehen (eben die beiden Faktoren). Für eine solche Urne (ohne Reihenfolge, mit Zurücklegen) gilt für die Anzahl der Möglichkeiten $\begin{eqnarray} \|\Omega\| = \binom{x+n-1}{n} \end{eqnarray}$ Setzen wir mal x=2 und n=2 ein, dann ist $\begin{eqnarray} \|\Omega\| = \binom{2+2-1}{2} = \binom{3}{2} = \frac{3!}{2!1!} = 3 \end{eqnarray*}$ Ah, schau mal einer an - scheint ja zu klappen. Allerdings ist bei dir nicht x=2, sondern eben x die Anzahl der Primzahlen, die du ja (näherungsweise) berechnet hast. air
27.11.2010, 11:25	Ionel	Auf diesen Beitrag antworten »
ah ich glaube zu verstehen =) also ist in meinem konkreten fall die rechnung so: ich habe zwei 768-Bit Primzahlen, also ist die Anzahl der n=pq so zu berechnen: n= $\begin{eqnarray} (1,4563110^{228})^{2} \end{eqnarray}$ stimmt das nun?
27.11.2010, 11:28	Airblader	Auf diesen Beitrag antworten »
Nein. Ich weiß auch nicht, wie oft ich noch schreiben soll, dass x die Anzahl der zur Verfügung stehenden Primzahlen ist und n die Anzahl der Primzahlen, die du dann wirklich ziehst (n=2). Ich sollte erwähnen, dass ich oben etwas inkonsequent war. Es ist nicht sehr schlau, von "n=pq" zu sprechen und im Urnenmodell dann n=2 zu sagen. Das sind natürlich verschiedene 'n's. Stell dir einen Topf vor, in dem alle deine x Primzahlen schwimmen. Und jetzt ziehst du n=2 raus, um deren Produkt zu bilden. Die Frage ist, wie viele Möglichkeiten es dafür gibt. Es ist nicht x=2, sondern n=2. x ist die Anzahl der Zahlen im Topf. air
27.11.2010, 11:30	Ionel	Auf diesen Beitrag antworten »
achso, sorry ich steh ein bisschen auf der leitung grad =) also ist am ende n=(2^(1,45631*10^228)).
27.11.2010, 11:32	Airblader	Auf diesen Beitrag antworten »
Nein, immer noch falsch Ich habe doch explizit gesagt, dass n=2 ist. Jetzt änderst du das schon wieder, was mir signalisiert, dass du das Urnenmodell nicht im Geringsten verstanden hast. Lies dir also mein Posting zur Urne nochmal genau durch! air
27.11.2010, 11:55	Ionel	Auf diesen Beitrag antworten »
ok, danke für deine Gedult mit mir =) wenn n=2 und x=1,4563110^(228) dann ergibt sich folgende gleichung: $\begin{eqnarray} \begin{pmatrix} 1,4563110^{228} + 2 - 1 \\ 2 \\ \end{pmatrix} = \begin{pmatrix} 1,4563110^{228} + 1 \\ 2 \\ \end{pmatrix}= \frac{(1,4563110^{228})!}{(1,4563110^{228}-2 )2!} \end{eqnarray}$ stimmt das jetzt so?
27.11.2010, 12:00	Airblader	Auf diesen Beitrag antworten »
Beim Umschreiben des Binomialkoeffizienten in die Fakultäten hast du die "+1" jeweils vergessen. Ansonsten stimmt das so, ja. Vergiss natürlich nicht, dass auch das nur eine Näherung ist, da bereits deine Anzahl der Primzahlen eine Näherung war. air

Neue Frage »

Antworten »

768-Bit Primzahlen

Verwandte Themen