C#快速素数测试的示例代码

Question

可能是重复问题：
最快的素数测试算法

希望提供使用BigInteger或其他可变大小类型的C#快速素数测试示例代码的参考。

- Halfdan Faber

---

我了解哪些是最快的算法，比如AKS、Miller-Rabin等。我正在寻找C#中高效的实现。 - Halfdan Faber

与此同时，我发现了：http://www.emilstefanov.net/Projects/GnuMpDotNet/。看起来很有前途。 - Halfdan Faber

以下代码比下面回答中提到的 Miller Rabin 测试要快得多：https://dev59.com/ZHRB5IYBdhLWcg3wbGtB#33627100 - Charles Okwuagwu

Answer 1

这是一个在 C# 中使用Miller Rabin测试:

    bool MillerRabin(ulong n)
    {
        ulong[] ar;
        if (n < 4759123141) ar = new ulong[] { 2, 7, 61 };
        else if (n < 341550071728321) ar = new ulong[] { 2, 3, 5, 7, 11, 13, 17 };
        else ar = new ulong[] { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
        ulong d = n - 1;
        int s = 0;
        while ((d & 1) == 0) { d >>= 1; s++; }
        int i, j;
        for (i = 0; i < ar.Length; i++)
        {
            ulong a   = Math.Min(n - 2, ar[i]);
            ulong now = pow(a, d, n);
            if (now == 1) continue;
            if (now == n - 1) continue;
            for (j = 1; j < s; j++)
            {
                now = mul(now, now, n);
                if (now == n - 1) break;
            }
            if (j == s) return false;
        }
        return true;
    }

    ulong mul(ulong a, ulong b, ulong mod)
    {
        int i;
        ulong now = 0;
        for (i = 63; i >= 0; i--) if (((a >> i) & 1) == 1) break;
        for (; i >= 0; i--)
        {
            now <<= 1;
            while (now > mod) now -= mod;
            if (((a >> i) & 1) == 1) now += b;
            while (now > mod) now -= mod;
        }
        return now;
    }

    ulong pow(ulong a, ulong p, ulong mod)
    {
        if (p == 0) return 1;
        if (p % 2 == 0) return pow(mul(a, a, mod), p / 2, mod);
        return mul(pow(a, p - 1, mod), a, mod);
    }

- Saeed Amiri

---

Saeed：非常感谢。我已经将代码转换为使用BigInteger类型。运行得非常好，而且速度极快。 - Halfdan Faber

@Dubslow，对于ulong范围内的素性测试，这是正确的。我认为你没有注意到“ar”数组的使用。这不仅仅是Miller Rabin测试。如果没有任何排除一些重要例外的数组，那么你是正确的。查看Miller Rabin无法找到的复合数序列，并将其与提供的ulong范围算法进行比较。您可以在我上面的其他评论中找到该序列。 - Saeed Amiri

@SaeedAmiri，当我运行代码时，它会报告一些偶数（如12、14、16）为true。我在顶部添加了“if (n％2 == 0 || n == 1) return false;”，似乎已经纠正了这个问题。 - SunsetQuest

@Sunsetquest 实际上这会跳过1和2被报告为质数。所以应该是这样的：“如果（n == 1 || n == 2）返回真；如果（（n＆1）== 0）返回假；”。 - H. de Jonge

@DarthGizka，是的，如果a+b大于64位，则会出现错误。但是您可以在这种情况下使用大整数（当然速度会慢一些）。但是模函数非常快，并且计算巨大乘法模数的技术是众所周知的（不是我的发明）。它不会重复减去，您可以查看此解释：https://www.geeksforgeeks.org/multiply-large-integers-under-large-modulo/ 如果我们计算a mod z，然后b mod z并将两者相乘，则可能会溢出（即使对于60位也是如此），从而得到错误的结果。因此，上述代码解决了这个问题。 - Saeed Amiri