试除法 假设我们已经找到了前n个素数p1=2 p2=3…pn,为了寻找下一个素数我们 从pn+2开始依次检验每一个整数N看N 是否能被某个pii=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(modm) 这里a≡ b mod p是指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互素,那么 a=l moa p 实际上,大约2500年前,中国古代数学家 就发现了上述结论。他们由此得出:如 果2”=2(删n边素数。该判别法 的运算量为Oog^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为合数!称使得 2P-=1 mod p 成立的p为伪素数
通过编程计算发现，反过来结论并不成 立。例如， 但是341=11x34为合数！称使得 成立的p为伪素数。 2 1 mod 341 340 p p 2 1 mod 1 −
注意同余的计算: 2=(2 10、34 =102434= (3×341+1)=1mod341 进一步,伪素数有多少个?
注意同余的计算： 进一步，伪素数有多少个？ (3 341 1) 1 mod 341 2 (2 ) 1024 34 340 10 34 34 + = = =