5

我需要对非常大的整数进行模运算。我的平台支持的最大整数（编辑：.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 帐号（包含字母）转换为一个整数。然后，您对整数进行取模。所以，我想你可以说执行模数的整数的真正来源是一串数字。

4

4 回答 4

5

您尚未指定数字的来源，但您可以进行一些简化。如果数字最初较小，请考虑以下事项：

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

或者

ab MOD n = (a MOD n)(b MOD n) MOD n
于 2008-11-10T16:57:59.480 回答
3

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

于 2008-11-10T16:52:58.337 回答
0

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

于 2009-01-16T13:58:57.483 回答
0

如果您使用的是 .NET 4，则可以只使用 BigInteger。但这是使用早期版本的方法。

mods 有一个数学技巧，您可以只取前x个数字，计算该值的 mod，然后将该 mod 的结果添加到剩余的数字上，并继续重复该过程直到您到达末尾你的“巨大”数字。

引入递归方法！（对不起我不做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);}
于 2011-04-21T09:36:22.673 回答