Esegui un modulo in un numero enorme?

Question

Ho bisogno di fare un'operazione di modulo su interi molto grandi. Il più grande numero intero supportato dalla mia piattaforma (modifica: .NET 2.0) è un numero intero a 64 bit, che non è abbastanza grande per i numeri con cui sto lavorando.

Come posso fare un modulo su numeri interi veramente grandi, come 12654875632126424875387321657498462167853687516876876?

Ho una soluzione che tratta il numero come una stringa e la lavora a pezzi una per una, ma volevo sapere se c'è un modo migliore.

Ecco la mia funzione che considera il numero come una stringa. Fondamentalmente fa una lunga divisione nel modo in cui lo faresti a mano.

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 

Esiste un modo più pulito ed efficiente?

MODIFICA: per chiarire, gli interi provengono da numeri di conto bancario IBAN. Secondo le specifiche, devi convertire il numero di conto IBAN (contenente lettere) in un numero intero. Quindi, si esegue un modulo sul numero intero. Quindi, immagino si possa dire che la vera fonte del numero intero per eseguire il modulo sia una stringa di cifre.

Answer 1

Non hai specificato da dove vengono i numeri, ma potresti essere in grado di fare alcune semplificazioni. Se i numeri sono in origine più piccoli, quindi prendere in considerazione le cose come:

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

o

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

Answer 2

Utilizzare una libreria crittografica/matematica. Google per bignum.

Answer 3

È necessario una libreria matematica intero precisione arbitraria, come IntX.

Answer 4

Se si utilizza .NET 4, è sufficiente utilizzare un BigInteger. Ma ecco come farlo con le versioni precedenti.

C'è un trucco matematico con mods dove si può semplicemente prendere il primo numero x di cifre, calcolare il mod su quel valore, quindi anteporre il risultato di quel mod indietro sulle cifre rimanenti, e continuare a ripetere il processo fino a raggiungere la fine del tuo numero "enorme".

Portare sul metodo ricorsivo! (Scusa non lo faccio 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);}