Miller Rabin素性检验

Question

我已经用return写了一个Miller Rabin素性测试，但它在每次输入时都返回false。

代码如下：

    static Boolean MilRab(UInt64 n)
    {
        UInt64[] ar = new UInt64[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
        for (int i = 0; i < 10; i++)
        {
            if (Tanu(ar[i], n) == true) return false;
        }
        return true;
    }//MilRab

    static Boolean Tanu(UInt64 a, UInt64 n)
    {
        UInt64 b = n - 1;
        UInt64 d = 1;
        UInt64 x;
        Int16 i;
        for (i = 63; i >= 0; i--) if (((b >> i) & 1) == 1) break;

        for (;i>=0;i--)
        {
            x = d;
            d = ((d * d) % n);
            if (d == 1 && x != 1 && x != n - 1) return true;
            if (b>>i == 1) d = (d * a) % n;
        }
        if (d != 1) return true;
      return false;
    }//Tanu

你认为问题可能是什么？我花了一天的时间调试，这让我抓狂。谢谢。

Answer 1

检查此实现的int和BigInteger

http://rosettacode.org/wiki/Miller-Rabin_primality_test#C.23

Answer 2

就像阿米尔说的，

http://rosettacode.org/wiki/Miller-Rabin_primality_test#C.23

有解决方案。但是..。我试过了，即使对于非常小的输入值，比如79，它也会给出错误的结果(79是质数，但反复出现不是质数)。原因是幂中的溢出(例如，11^78类似于1E+81，它不能用32位或64位整数表示)。

所以在这里

public static class RabinMiller
{
    public static bool IsPrime(int n, int k)
    {
        if(n < 2)
        {
            return false;
        }
        if(n != 2 && n % 2 == 0)
        {
            return false;
        }
        int s = n - 1;
        while(s % 2 == 0)
        {
            s >>= 1;
        }
        Random r = new Random();
        for (int i = 0; i < k; i++)
        {
            double a = r.Next((int)n - 1) + 1;
            int temp = s;
            int mod = (int)Math.Pow(a, (double)temp) % n;
            while(temp != n - 1 && mod != 1 && mod != n - 1)
            {
                mod = (mod * mod) % n;
                temp = temp * 2;
            }
            if(mod != n - 1 && temp % 2 == 0)
            {
                return false;
            }
        }
        return true;
    }
}

您应该添加一个函数

    static int ModuloPower(int a, int b, int n)
    {
        // return (a^b)%n
        int res = 1;
        for (int i = 0; i < b; ++i)
            res = (res * a) % n;
        return res;
    }

并将power/modulo行改为

    int mod = ModuloPower(a, temp, n); // (int)Math.Pow(a, (double)temp) % n;

当然，这可以再次优化。在rosettacode站点上查看其他语言的代码示例，以获得更快地计算幂/模的一些更聪明的方法。

(我试过在那里编辑代码，但必须注册，所以我在这里发帖。)