Führen Sie einen Modulus in einer großen Anzahl aus?

Question

Ich muss eine Modulusoperation an sehr großen Ganzzahlen durchführen. Die größte von meiner Plattform unterstützte Ganzzahl (edit: .NET 2.0) ist eine 64-Bit-Ganzzahl, die für die Zahlen, mit denen ich arbeite, nicht groß genug ist.

Wie kann ich einen Modulus an wirklich großen ganzen Zahlen machen, wie 12654875632126424875387321657498462167853687516876876?

Ich habe eine Lösung, die die Zahl als eine Zeichenfolge behandelt und es Stück für Stück bearbeitet, aber ich wollte wissen, ob es einen besseren Weg gibt.

Hier ist meine Funktion Behandlung der Nummer als eine Zeichenfolge. Es macht im Grunde lange Teilung, wie Sie es von Hand tun würden.

Public Function MyMod(ByVal numberString As String, ByVal modby As Integer) As Integer 
     Dim position As Integer = -1 
     Dim curSubtraction As Integer = 0 

     While position < numberString.Length - 1 
      position += 1 
      curSubtraction = curSubtraction * 10 + CInt(numberString.Substring(position, 1)) 

      If (curSubtraction/modby) < 1 And position = numberString.Length - 1 Then 
       Return curSubtraction 
      ElseIf (curSubtraction/modby) < 1 Then 
       Continue While 
      Else 
       curSubtraction = curSubtraction Mod modby 
      End If 
     End While 
     Return curSubtraction 
    End Function 

Gibt es einen saubereren, effizienteren Weg?

EDIT: Um zu klären, kommen die ganzen Zahlen von IBAN Bankkontonummern. Gemäß der Spezifikation müssen Sie die IBAN-Kontonummer (mit Buchstaben) in eine ganze Zahl umwandeln. Dann machen Sie ein Modulo für die Ganzzahl. Also, ich denke, man könnte sagen, dass die wahre Quelle der Ganzzahl, um den Modulus auszuführen, eine Ziffernfolge ist.

Answer 1

Sie haben nicht angegeben, wo die Zahlen herkommen, aber Sie können möglicherweise einige Vereinfachungen vornehmen. Wenn die Zahlen ursprünglich kleiner sind, soll dann Dinge wie:

(a + b) MOD n = ((a MOD n) + (b MOD n)) MOD n 

oder

ab MOD n = (a MOD n)(b MOD n) MOD n 

Answer 2

Verwenden Sie eine Crypto/Math-Bibliothek. Google für bignum.

Answer 3

Sie benötigen eine beliebige Genauigkeit Integer-Mathematik-Bibliothek wie IntX.

Answer 4

Wenn Sie .NET 4 verwenden, können Sie einfach einen BigInteger verwenden. Aber hier ist, wie es mit früheren Versionen geht.

Es ist ein mathematischer Trick mit Mods, wo man die Mod nehmen kann auf diesen Wert nur die erste x Anzahl der Stellen, berechnen, dann schreibe das Ergebnis dieser Mod wieder auf die übrig gebliebenen Ziffern und immer wiederholen der Prozess, bis Sie das Ende Ihrer "großen" Nummer erreichen.

Holen Sie sich die rekursive Methode! (Sorry, ich mache keine VB)

private static int Mod(string value, int mod) { 
    if (string.IsNullOrEmpty(value)) throw new ArgumentException("Invalid value.", "value"); 
    if (mod <= 0) throw new ArgumentException("Invalid mod.", "mod"); 

    int maxLength = long.MaxValue.ToString().Length - 1; 

    return value.Length > maxLength 
     ? Mod((Convert.ToInt64(value.Substring(0, maxLength)) % mod).ToString() + value.Substring(maxLength), mod) 
     : Convert.ToInt32(Convert.ToInt64(value) % mod);}