Thực hiện mô đun trong một số lượng lớn?

Question

Tôi cần thực hiện thao tác mô đun trên các số nguyên rất lớn. Số nguyên lớn nhất được hỗ trợ bởi nền tảng của tôi (chỉnh sửa: .NET 2.0) là một số nguyên 64 bit, không đủ lớn cho các số tôi đang làm việc.

Làm cách nào để tạo mô đun trên các số nguyên thực sự lớn, như 12654875632126424875387321657498462167853687516876876?

Tôi có một giải pháp xử lý số dưới dạng chuỗi và hoạt động theo từng phần, nhưng tôi muốn biết liệu có cách nào tốt hơn không.

Đây là chức năng của tôi xử lý số dưới dạng chuỗi. Về cơ bản nó phân chia dài cách bạn làm bằng tay.

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 

Có cách nào sạch hơn, hiệu quả hơn không?

EDIT: Để làm rõ, các số nguyên đến từ số tài khoản ngân hàng IBAN. Theo đặc điểm kỹ thuật, bạn phải chuyển đổi số tài khoản IBAN (chứa các chữ cái) thành một số nguyên. Sau đó, bạn làm một mô đun trên số nguyên. Vì vậy, tôi đoán bạn có thể nói rằng nguồn thực sự của số nguyên để thực hiện mô đun trên là một chuỗi các chữ số.

Answer 1

Bạn chưa chỉ định vị trí của các số, nhưng bạn có thể thực hiện một số đơn giản hóa. Nếu các con số ban đầu nhỏ hơn, sau đó xem xét những thứ như:

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

hoặc

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

Answer 2

Sử dụng thư viện mật mã/toán học. Google cho bignum.

Answer 3

Bạn cần một thư viện toán số nguyên tùy ý chính xác như IntX.

Answer 4

Nếu bạn đang sử dụng .NET 4, bạn chỉ có thể sử dụng BigInteger. Nhưng đây là cách để làm điều đó với các phiên bản trước đó.

Có một trick toán học với mods nơi bạn có thể chỉ cần lấy số x đầu tiên của chữ số, tính toán mod trên giá trị đó, sau đó thêm vào trước các kết quả của mod đó trở lại vào các chữ số còn sót lại, và tiếp tục lặp đi lặp lại quá trình cho đến khi bạn đạt đến cuối số "khổng lồ" của bạn.

Mang theo phương pháp đệ quy! (Xin lỗi tôi không làm 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);}