Primitivitätsprüfung Algorithmus

Question

Primality Check ist wahrscheinlich einer der "schwierigen" Probleme in der Mathematik. Also, was ist der beste und schnellste Algorithmus zur Verfügung, um die Primzahl einer großen Zahl zu überprüfen. Die rohe und der langsamste Weg wahrscheinlich ist:

public static bool IsPrime(int i) 
{ 
    for (var x = 2; x < i - 1; i++) 
    { 
     if (i % x == 0) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

Vor kurzem habe ich gelesen, dass die 768-Bit-RSA-Algorithmus Brute-Force geknackt wurde mit einem Grid-Computing-Array. Wie führen sie die rohe Gewalt an einer riesigen Primzahl aus? Nimmt jede Verarbeitungseinheit eine Reihe von Zahlen auf, faktorisiert sie und prüft die Primzahl auf die Anzahl, die in diesem Bereich liegt?

Answer 1

Check out primality tests auf Wikipedia für Zeiger auf aktuelle Algorithmen

Im Hinblick auf Ihre naive Implementierung, merken Sie, dass Sie sofort false zurückgeben können, wenn die Zahl durch 2 teilbar ist, so dass Sie nur ungerade überprüfen Zahlen. Wenn Sie keinen Faktor finden, bei dem x < = sqrt (i) ist, ist es prim. Wenn Sie nämlich einen Faktor gefunden haben, der größer als sqrt (i) ist, muss er mit einem Faktor kleiner als sqrt (i) gepaart werden. Wenn Sie also diesen kleineren Faktor nicht zuerst finden, sind Sie fertig.

Es gibt auch einige weitere Tricks, die Sie zu einem naiven Algorithmus anwenden können, bevor Sie trooping off zu https://mathoverflow.net/ um Hilfe zu gehen :)

Answer 2

public static bool IsPrime(int i) 
{ 
    for (var x = 2; x < (i/2); x++) 
    { 
     if (i % x == 0) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

Answer 3

ich es annehmen, ist eine Art von Lastverteilung, aber ich bezweifle, dass sie solche verwendet ein einfacher Algorithmus für den Primzahltest. Vielleicht haben sie die number field sieve oder verwendet.

Answer 4

Dieses etwas ganz schneller sein sollte:

public static bool IsPrime(int i) {   
    // only go up to the root of i 
    // +1 to be save from floating point rounding errors, ceil should work too. 
    var max = sqrt(i) + 1; 

    // skip numbers dividable by 2, except 2 itself 
    if (i == 2) return true; 
    if (i % 2 == 0) return false; 
    for (var x = 3; x < max; x+=2) { 
     if (i % x == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

Answer 5

Cracking RSA-768 hat, eher nicht direkt jede primality Prüfungsalgorithmus beinhalten, was ein Faktorisierung Algorithmus benötigt wurde war: RSA-768 ist das Produkt aus zwei sehr große Primzahlen, und knacken es beinhaltet diese Primzahlen zu finden. Der verwendete Faktorisierungsalgorithmus war Lenstras Number Field Sieve.

Sie können den vollständigen Artikel hier lesen: Factorization of a 768-bit RSA modulus.

Answer 6

Primärtest! = Faktorisierung.

Das Brechen eines bestimmten öffentlichen RSA-Schlüssels und das Abrufen des privaten Schlüssels erfordert Faktorisierung.

Der Prozess des Erstellens eines öffentlichen/privaten RSA-Schlüsselpaars umfasst Primzahltests. Die meisten Primitivitätstests, die nicht für die Faktorisierung verwendet werden, liefern keine 100% eindeutige Antwort, sondern sind probabilistic mit einer beliebig hohen Wahrscheinlichkeit (mehr Testiterationen = höhere Wahrscheinlichkeit).

Und technisch können Sie eine deterministic primality test haben, die schnell ist und tatsächlich keine Faktoren der fraglichen Zahl berechnet.

Answer 7

Ich schlage vor, Fermat's Little Theorem zu verwenden. Wert von 'x' prim if ((a^(x-1))% x) == 1.Wobei 'a' ist eine beliebige Nummer und 'x' nicht gleich 1, 0 oder 2.