Fermat-Test in C#

[fr@gstyler]

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

[Klotzkopp]

^2 bedeutet nicht "hoch 2", sondern "bitweise xor 2".

[fr@gstyler]

Vielen Dank! Jetzt funzt es!

Arg...

Woher hab ich denn wohl, das "^" "hoch" bedeutet?

Greets

fr@ggy

[Mcolli]

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