wahrscheinlichkeit bei multiplikation
-
Hallo leute,
ich habe zwei primzahlen p und q.
die funktion bitCount(n), gibt die anzahl der bitstellen von n an.wie hoch ist die wahrscheinlichkeit, dass gilt:
bitCount(p * q) = bitCount(p) + bitCount(q)dabei interessiert es mich insbesondere, wie sich die wahrscheinlichkeit für sehr große primzahlen p und q (so um die 1024 bitstellen) entwickelt.
kann man das irgendwie genau sagen, oder zumindest schätzen?
ich brauche das für die schlüsselerzeugung bei RSA, wobei eine bestimmte schlüssellänge vorgegeben wird.
danke!
Gruß mathik
-
Die Aufgabe ist etwas ungenau gestellt. Wenn Du die beiden Zahlen bereits hast, dann ist die Wahrscheinlichkeit, daß Deine Formel gilt: 1, falls sie gilt und 0 falls nicht.
Aber das wolltest Du wahrscheinlich nicht wissen. Ich nehme an Du ziehst p und q zufällig und willst das dann wissen, oder?
Und was meinst Du mit Anzahl Bitstellen? Anzahl der gesetzten Bits? Oder Anzahl der Stellen, die benötigt werden um die Zahl darzustellen?
MfG Jester
-
ich geh mal davon aus, dass du das ganze irgendwie in einem programm verwenden willst. Daher ist die Anzahl der Primzahlen wohl schon durch die größte darstellbare Zahl bestimmt (kommt halt auf den datentyp an). Und da du dadurch alle möglichen Primzahlen kennst musst du nur noch alle paare finden für die die Gleichung gilt und die Anzahl derer durch die Anzahl aller paare teilen. dann hast du die wk.
-
Hallo Jester,
Jester schrieb:
Aber das wolltest Du wahrscheinlich nicht wissen. Ich nehme an Du ziehst p und q zufällig und willst das dann wissen, oder?
p und q sind zufällig, wobei diese aber eine bestimmte bitlänge haben (s.u.).
Jester schrieb:
Und was meinst Du mit Anzahl Bitstellen? Anzahl der gesetzten Bits? Oder Anzahl der Stellen, die benötigt werden um die Zahl darzustellen?
Das zweitere. bitCount sagt aus, wieviele bits benötigt werden um die zahl darzustellen. also z.b bitCount(5) = bitCount(4)= 3. der name ist unglücklich gewählt, ich nenne das jetzt deswegen besser bitLength.
worum es bei mir geht:
ich generiere zwei primzahlen p und q, die eine bestimmte bitlänge haben.
die bitlänge des produktes dieser zahlen muss aber gleich der summe der bitlängen von p und q sein. (siehe oberen beitrag).
um das zu erreichen, generiere ich einfach die zahlen p und q und schaue ob die bedingung erfüllt ist. wenn nicht, dann generiere ich sie nochmal (ganauer: nur die kleinere von beiden wird erneut generiert).
dabei gehe ich davon aus, dass die wahrscheinlichkeit bei sehr großen zahlen sehr hoch ist, dass die bedingung beim ersten durchgang erfüllt wird.
ich brauche das jetzt allerdings präziser, wie hoch diese wahrscheinlichkeit tatsächlich ist.denn das generieren von primzahlen unter java ist eine sehr langwierige angelegenheit...
Gruß mathik
-
heinzel schrieb:
ich geh mal davon aus, dass du das ganze irgendwie in einem programm verwenden willst. Daher ist die Anzahl der Primzahlen wohl schon durch die größte darstellbare Zahl bestimmt (kommt halt auf den datentyp an). Und da du dadurch alle möglichen Primzahlen kennst musst du nur noch alle paare finden für die die Gleichung gilt und die Anzahl derer durch die Anzahl aller paare teilen. dann hast du die wk.
ich verwende einen datentypen, der mit "unendlich" großen zahlen rechnen kann. wobei die zahlen mit denen gerechnet wird, werte von ca. 24096 haben.
in diesem zahlenraum gibt es mehr primzahlen, als atome im ganzen universum!
Gruß mathik
-
Hm, erstmal versuchen bitcount/bitlength mathematisch zu fassen. Sieht mir nach nem Logarithmus zur Basis 2 aus (mit leichter Modifikation). Ich nenn den mal ld.
ld(x)+1 scheint mir die Anzahl zu sein, wenn man abrundet.
Und wir wissen: ld(p*q) = ld(p)+ld(q)Also: bitcount(p*q) == bitcount(p)+bitcount(q) -> einsetzen
floor(ld(p*q))+1 == floor(ld(p))+1 + floor(ld(q))+1 <=>
floor(ld(p)+ld(q)) == floor(ld(p)) + floor(ld(q)) + 1wenn ich das recht sehe.
Der abgerundeten ld müßte sich doch auch für recht große Zahlen noch ganz gut bestimmen lassen. Die rechte Seite ist also nett. Die linke Seite aber noch nicht. Aber vielleicht kannste den ld so genau berechnen, daß Du entscheiden kannst welcher Fall eintritt. Es ist klar, daß die linke Seite immer kleiner/gleich der Rechten ist.
Mit Wahrscheinlichkeiten kann ich da leider nicht dienen. Es Funktioniert jedenfalls, wenn das was Du beim abrunden abschneidest sich mindestens zu 1 addieren läßt. Hoffe, das hilft ein bißchen.
MfG Jester
-
du willst eine art rsa-verfahren basteln? da gibt es bei wikipedia eine wirklich gute seite die sich damit auseinandersetzt. dummerweise find ich sie grad nicht wieder, da würd ich aber mal suchen.
wenns nix mit rsa zu tun hat und nur zufällig so aussieht vergiss das einfach
-
Hallo Jester,
vielleicht kann man das irgendwie folgendermaßen lösen. und zwar sind die bitlängen von p und q in meinem fall gleich, oder unterscheiden sich manchmal um ein bit. aber zur vereinfachung nehmen wir mal an, dass die beiden bitlängen gleich sind.
wenn man jetzt p und q schriftlich multipliziert, dann sieht das im binärsystem so aus:
(p0 p1 p2 ... pn-1 pn) * (q0 q1 q2 .. qn-1 qn) dann ist auf jeden fall p0 = q0 = pn = qn = 1, da p und q primzahlen sind. somit sieht das dann so aus: (1 p1 p2 ... pn-1 1) * (1 q1 q2 ... qn-1 1) ein ausschnitt aus der schriftlichen multiplikation sieht dann so aus: (1 p1 p2 ... pn-1 1 ) * 1 + ( 1 p1 ... pn-2 pn-1 ) * q1 + ( 1 ... pn-3 pn-2 ) * q2 + ( ... . . ) . + ( . . ) . + ( 1 ) * 1hierbei habe ich den "linken teil der additionsreihen" dargestellt, ich hoffe ihr versteht was ich damit darstellen will.
dabei ist zu beachten, dass die zeilen, die mit q1 .. qn-1 multipliziert werden, auch 0 sein können.
wie man sieht tritt in der rechten spalte auf jeden fall ein carry auf (wegen 1 + 1).damit nun die bitlänge des produktes gleich 2n ist, muss an der stelle "(1 + p1)" ein carry auftreten.
die frage ist jetzt, wie hoch ist denn hier die wahrscheinlichkeit?Gruß mathik
-
Das ist ne gute Frage.
Hab leider keine Idee dazu.