在一个巨大的数字中执行模运算？

Question

我需要在非常大的整数上执行模运算。我的平台（编辑：.NET 2.0）支持的最大整数是64位整数，这对于我正在处理的数字来说不够大。

如何对超大整数执行模运算，例如12654875632126424875387321657498462167853687516876876？

我有一个解决方案，将数字视为字符串并逐个处理它，但我想知道是否有更好的方法。

这是我的函数，将数字视为字符串。它基本上按照手动计算的方式进行长除法。

    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

有没有更干净、更有效的方法？

编辑：为了澄清，这些整数来自IBAN银行账户号码。根据规范，您必须将IBAN账户号码（包含字母）转换为一个整数。然后，对该整数进行模运算。因此，您可以说执行模运算的真实整数源是一串数字。

- Jim

---

这是什么编程语言？你可能想要添加一个标签。 - billjamesdev

包含一个例子将会更有帮助。你是否已经找到了在你的问题中对于巨大数字模除其他值的解决方案？ - Bill the Lizard

Answer 1

您没有说明这些数字的来源，但您可能可以进行一些简化。如果这些数字最初较小，则考虑以下事项：

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

或者

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

- Tony Arkles

---

是的 - 我需要更清楚地澄清问题。您的解决方案可以在我从多个整数开始时起作用，但在我的情况下，我从一个大整数开始。 - Jim

Answer 2

使用加密/数学库。Google搜索bignum。

- HUAGHAGUAH

Answer 3

如果您使用的是.NET 4，您可以直接使用BigInteger。但是以下是如何在早期版本中实现它。

有一种数学技巧，可以使用模运算来获取前x个数字，计算该值的模，然后将该模的结果重新添加到剩余的数字上，并不断重复此过程，直到达到您的“巨大”数字的末尾。

让我们开始递归方法吧！（抱歉我不会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);}

- user718642

Answer 4

你需要一个任意精度整数数学库，例如IntX。

- Michael Borgwardt