fr@gstyler Geschrieben 9. Juni 2010 Geschrieben 9. Juni 2010 Hallo Leute, ich habe folgenden Fermat-Test in C# implementiert: // liefert true, wenn der Fermat-Test n als zusammengesetzt erkennt private bool isCompositeFermat(long n) { return (modexp(2, n - 1, n) != 1); } // erzeugt eine zufaellige Primzahl der Laenge k private long randomPrime(long k) { long a=2^(k-1); long b=2*a-1; long n = RandomProvider.Next(a, ; while (isCompositeFermat(n)) n=n-1; return n; } private long modexp(long m, long e, long n) { if (e==0) return 1; if (e%2==1) return (modexp(m, e-1, n)*m)%n; return (modexp(m, e/2, n)^2)%n; } [/code] n ist zuerst immer in der Größenordnung, die ich eingestellt hab, aber nachdem der Fermat-Test durchgelaufen ist, ist das Ergebnis immer 1. Aber ne 1 als Primzahl für eine Verschlüsselung bringt mir so gar nichts. Ich versteh einfach nicht, was an diesem Code falsch ist. Hoffentlich könnt ihr mir helfen... Greets fr@gstyler Zitieren
Klotzkopp Geschrieben 9. Juni 2010 Geschrieben 9. Juni 2010 ^2 bedeutet nicht "hoch 2", sondern "bitweise xor 2". Zitieren
fr@gstyler Geschrieben 9. Juni 2010 Autor Geschrieben 9. Juni 2010 Vielen Dank! Jetzt funzt es! Arg... Woher hab ich denn wohl, das "^" "hoch" bedeutet? Greets fr@ggy Zitieren
Mcolli Geschrieben 9. Juni 2010 Geschrieben 9. Juni 2010 (bearbeitet) Du musst aufpassen dass Du nicht aus dem 64bit long range rausläufst: 1. long a=2^(k-1); 2. long b=2*a-1; der Größtmögliche wert für long ist "(2^63) -1" (s. Unten). --> k darf max. 64 sein Da aber bei 2. noch mit 2 Multipliziert wird darf a maximal "(2^63 - 1) / 2" sein da sonst b überläuft: "Richtig" wäre: k = k > 63 ? 63 : k; //k auf max 63 stellen da ja noch Multipliziert wird um b zu erechnen. // Potenziert darf maximal mit 62 werden da man unten ja noch mit 2 Multipliziert. Stichwort: 2^x * 2 = 2^(x+1) long a = 2^(k - 1) - 1 long b=2*a-1; Richtig in anführungszeichen da Du dann dir deine Random Zahl mit long n = RandomProvider.Next(a, ; holst. Ich schätze mal das a die untere und b die Obere Grenze abstecken sollen. Wenn dem so ist macht das meht Sinn: k = k > 63 ? 63 : k; //k darf jetzt maximal 64 sein da man ja nicht mehr mit 2 Multipliziert für das obere Intervall; long a = 2; long b = 2 *(k - 1) - 1; long n = RandomProvider.Next(a, ; [/code] Um den Aufwand beim folgenden Überprüfen ob Primzahl zu halbieren macht das noch sinn: [code] long n = n % 2 == 0 ? n - 1 : n; // n ungerade machen // n darf nicht kleiner als 2 werden (ja gerade Zahlen sind nicht mehr möglich) while (isCompositeFermat(n) && n > 3) { n=n-2; } return n; Sehr gut ist dass Du den Euklyd zur Prüfung benutzt. Wenn Du Die Primzahl aus dem Longbereich erstellt um einen RSA Schlüsselpaar mit 64 Bit zu bilden bedenke das der 64bit Schlüssel nicht 64 bit heisst weil er aus 2 64Bit Primzahlen zusammengesatzt wurde sondern weil der gemeinsame Teile der Schlüsselpaare, der durch Multiplikation 2er Primzahlen gebildet wird, 64Bit lang ist.... Warum 2 ^ (Stellen -1) - 1 als gröten Wert: Long wird, wie int, in der 2er komplimentär Darstellung ausgedrückt ... das heisst, dass das "höchstwertige" Bit (also das mit dem index 63) als negativ interpretiert wird. Der Rest (also Indizies 0-62) als Positive Zahl interpretiert werden und das zu dem Wert des negativen Anteils addiert werden. Wenn man das mit 4 Bit mal verdeutlicht: Zahl: 1 | 0 | 1 | 0 Index: 3 | 2 | 1 | 0 Bit-Wert: -(1*2^3)= -8 | (0*2^0)=0 | (1*2^1)=2 | (0*2^2)=0 Gesammt: -8 + 0 + 2 + 0 = -6 Größte Zahl Wäre: 0111 --> -0 + 1 + 2 + 4 = 7 = 2 ^3 - 1 Kleinster Wert: 1 000 -->-8 + 0 + 0 + 0 = -8 = -2^3 Bearbeitet 9. Juni 2010 von Mcolli Zitieren
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.