试除法 假设我们已经找到了前n个素数p1=2 p2=3,…p_n,为了寻找下一个素数我们 从pn+2开始依次检验每个整数N看N 是否能被某个pi=1,2…n整除如果N 能被前面的某个素数整除,则N为合数.否 则N即为下一个素数p{n+1 为提高算法的效率,只需用不超过√的 素数去除N
• 试除法 假设我们已经找到了前n个素数p_1=2, p_2=3, ...,p_n, 为了寻找下一个素数我们 从p_n+2开始依次检验每一个整数N, 看N 是否能被某个p_i, i=1,2,...,n整除. 如果N 能被前面的某个素数整除, 则N为合数. 否 则N即为下 一个素数p_{n+1}. 为提高算法的效率，只需用不超过 的 素数去除N。 N
3、素数的判别 威尔逊判别法 n是素数的充要条件是 (n-1)!+1≡0(modn) 这里a≡bmdp是指a-b被p整除。 不过该算法的运算量为O( nlogn^2)计 算量太大
3、素数的判别 威尔逊判别法 n是素数的充要条件是 这里 是指 a-b 被p整除。 不过该算法的运算量为O(nlogn^2),计 算量太大。 a b mod p (n −1)!+1 0 (mod n)
Fermat判别法 如果p是素数,a与p互素,那么 P-1≡1modp 实际上,大约2500年前,中国古代数学家 就发现了上述结论。他们由此得出:如 果2”=2(-素数。该判别法 的运算量为o(og^3n
• Fermat判别法 如果p是素数，a与p互素，那么 实际上，大约2500年前，中国古代数学家 就发现了上述结论。他们由此得出：如 果 ,则n为素数。该判别法 的运算量为O(log^3n). a p p 1 mod 1 − 2 2 (mod 2) n
通过编程计算发现,反过来结论并不成 立。例如, 2340≡1mod341 但是341=11×34为合数!称使得 2 nod p 成立的p为伪素数
通过编程计算发现，反过来结论并不成 立。例如， 但是341=11x34为合数！称使得 成立的p为伪素数。 2 1mod 341 340 p p 2 1 mod 1 −
注意同余的计算 2=(2)=10244= (3×341+1)34=1md341 进一步,伪素数有多少个?
注意同余的计算： 进一步，伪素数有多少个？ (3 341 1) 1 mod 341 2 (2 ) 1024 34 340 10 34 34 + = = =