因为一个整数p，若检测为合数，这永远是真命题；而检测为素数，这命题只以较大概率成立。 可构造一种NP检测算法，步骤如下：
1. 猜测p（位长度n）的因子列表｛p1,p2,…pi｝，这是非确定的，每个分支耗时O(n)
2. 验证p1*p2*…pi？=p-1，耗时不超过O(n^2)
3. 若各因子乘积等于p-1，则用当前算法递归验证每个因子都是素数
4. 随机选择p最小剩余系内的一个数x，计算x^((p-1)/q) （q遍历上述列表经过步骤3验证过的素因子）是否都不同余于1模p，若是则必有x^(p-1)同余于1模p，则由指数整除p的欧拉数及费马小定理，知p为素数，考虑到有少量的合数也满足费马小定理，故需多次选择x重复验证，选择个数最多为log(p)
分析：本算法涉及的数论定理——设p是奇素数，p-1的所有素因子是q1,q2,…qs，那么g为原根的充要条件是，g^((p-1)/qj)不同余1模p，j=1,2…,s
结论：第3步可以看成递归调用树，每个顶点为待检测整数，其每个子结点为一个因子，则最多n层，每层至多耗时O(n^4)，所以每个路径即检测p是否素数的非确定任一分支中，总耗时O(n^5)。 2002年，印度科学家发现素检测确定性多项式时间算法，于是从NP前进到了P
posted on 2023-09-09 08:07
春秋十二月 阅读(653)
评论(0) 编辑 收藏 引用 所属分类:
Compute Theory