Miller-Rabin 算法
Miller-Rabin 算法是一个以很大概率正确地判定一个奇数是不是素数的算法
?
一种很草率的方法便是用分别去除n,但是这样的算法最坏情况是
,嗯……似乎n很大时会炸?
伪素数测试
令表示
中的非零元素:

根据费马小定理,我们可以知道,若是素数,则
对所有
成立
如果n是一个合数,且







Miller-Rabin 随机性素数测试
定理
如果是一个奇素数且
则方程


证明
等价于











我们称和
是以
为模的
的平凡平方根,若
满足
且
不是以
为模的
的平凡平方根,则称
是以
为模的
的非平凡平方根
推论
如果对模存在
的非平凡平方根,则
是合数
证明
由定理可知,如果对模存在
的非平凡平方根,则
不可能是奇素数或奇素数的幂。有因为当
时只有平凡平方根,所以
是合数
应用
由上面的定理及推论可知,如果发现一个以为模的
的非平凡平方根,那么可以判断
是合数
因此在伪素数测试过程中加入这个判断,正确性又会高
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
//C++ bool witness(long long a, long long n) { int t = 0; while ((n - 1) % (((long long)1) << (t + 1)) == 0) { t++; } long long u = (n - 1) / (((long long)1) << t); long long x = pow_mod(a, u, n); for (int i = 1; i <= t; i++) { long long pre = x; x = x * x % n; if (x == 1 && pre != 1 && pre != n - 1) { return true; } } if (x != 1) { return true; } return false; } bool miller_rabin(long long n, int s) { for (int j = 1; j <= s; j++) { long long a = ((long long)rand() * (((long long)1) << 32) + (long long)rand() * (((long long)1) << 16) + (long long)rand()) % (n - 1) + 1; if (witness(a, n)) { return false; } } return true; } |
若witness函数返回true,则说明以为证据可以判断
是合数
miller_rabin(n,s)表示对于n是不是素数测试s次
由算法导论中的定理31.39可得,miller_rabin出错的概率至多为,并且选
基本上足够了
参考资料
《算法导论 第三版中文版》第31章数论算法
大佬大佬大佬
%%%%%%%%