c# - 为什么幂函数给出负值？

Question

目前我正在实现 RSA 算法。以下功能是我们在 RSA 中需要的功能。

private long power2(long x, long y, long n)
{
    long temp = 1;
    while (y > 0)
    {
        var z = y & 1;
        if (z == 1)
        {
            temp = ((temp % n) * (x % n)) % n;
        }

        x = ((x % n) * (x % n)) % n;

        y = y >> 1;
    }
    return temp;
}

这里的 n 是 9 个字符长(从 6 开始)。 如果我增加 n 的值(从 9 开始)，那么此函数会为 x 和 y 的某些值提供负值。我不知道为什么会这样。只要可以包含高达 9223372036854775807 的值，并且在我的幂函数中，乘法就无法超出该值。

如果我想比当前使用更长的时间(10-15 个字符)，我必须使用什么数据类型我正在使用。我试过 Decimal 和 double 但它有与上面相同的问题(给出负值)。

Answer 1

这是由于 so-called overflow 而发生的.

Here is an article解释为什么会这样。

您可能需要 to use BigInteger结构而不是 System.Numerics。