Zum Inhalt springen

Fermat-Test in C#


fr@gstyler

Empfohlene Beiträge

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

Link zu diesem Kommentar
Auf anderen Seiten teilen

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, B); 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 von Mcolli
Link zu diesem Kommentar
Auf anderen Seiten teilen

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.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...