为什么幂函数给出负值？

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。

Answer 2

您的解决方案仍然可以超越长值

你将 x%n（可以是 10 个字符长）的结果与相同的值相乘，结果很可能超过 2^64（在应用最后一个模数之前，结果在模数也应该适合长变量）

考虑使用 BigInteger

为什么幂函数给出负值？

why power function giving negative value?

c#

integer-overflow

long-integer