a
2
a (modn) n
• 维路于1978年指出，上述常数C=70. • 由此可以设计如下多项式算法： 对任意n, 依次对a=1,2,…,70(logn)^2检验 上式是否成立。若对每一个a都不成立， 则n为素数。否则，n 为合数。 上述算法的运算量为O(logn)^5.
2、素数表的构造
• Eratosthenes筛法 2 3 4 5 10 11 12 13
18 19 26 27 20 28 21 29
6 14 22 30
7 15
8 16
9 17 25
23 24 31
32 33
经过众多学者的艰辛努力, D.N.Lehmer 于 1914年编织出了10000000以内的素数表。
通过编程计算发现，反过来结论并不成 立。例如，
2
340
1 mod341
1 mod p
但是341=11x34为合数！称使得
2
p 1
成立的p为伪素数。
注意同余的计算：
2
340
(2 ) 1024
10 34 34 34
(3 341 1) 1 mod 341
进一步，伪素数有多少个？
• 五年后他进一步证明了: 一个正n边行可 用直尺与园规作图的充要条件是, n=2^k 或者n=2^k p_1 p_2... p_r, 其中 p_1,p_2,...,p_r为不同的Fermat数. 特 别地, 正17边形可以用直尺与园规做出. • 此后，数学家梨西罗与盖尔美斯给出了 正257边形与正65537边形的做图法！
267 1 193707721 7618382572 87
• 截止2002年2月, 数学家仅发现了39个 Mersenne素数.
