维路于1978年指出,上述常数C=70 由此可以设计如下多项式算法: 对任意n,依次对a=1,2,,70(logn)2检验 上式是否成立。若对每一个a都不成立, 则n为素数。否则,n为合数。 上述算法的运算量为O(logn)^5
• 维路于1978年指出，上述常数C=70. • 由此可以设计如下多项式算法： 对任意n, 依次对a=1,2,…,70(logn)^2检验 上式是否成立。若对每一个a都不成立， 则n为素数。否则，n 为合数。 上述算法的运算量为O(logn)^5
1980年数学家 Adleman, Rumely Cohen和 Lenstra研究出一种非常复杂、具 有高度技巧的素数判别方法,检验—个 20位数的素性只需10秒,对一个5 0位数,只要15秒,而一个100位 数只用40秒。如果用试除法,判别 个50位数的素性要一百亿年!
• １９８０年数学家Adleman, Rumely, Cohen和Lenstra研究出一种非常复杂、具 有高度技巧的素数判别方法，检验一个 ２０位数的素性只需１０秒，对一个５ ０位数，只要１５秒，而一个１００位 数只用４０秒。如果用试除法，判别一 个５０位数的素性要一百亿年！
·概率判别法 Lehmann:给定p,判断它是否为素数: (1)选择一个小于p的随机数a (2)如果a与p不互素,则p为合数 (3)计算J=a(p-1) mod (4)如果J1或-1,那么p为合数; (5)如果J=1或-1,那么p不是素数 的可能性最多是50%
• 概率判别法 • Lehmann: 给定p, 判断它是否为素数： • （１）选择一个小于p的随机数a; • （２）如果a与p不互素，则p为合数； • （３）计算 J=a^(p-1) mod p； • （４）如果 J<>1或-1, 那么p为合数； • （５）如果 J=1或-1, 那么p不是素数 的可能性最多是50%
重复k次实验,那么p不是素数的可能性 不超过1/2^k 利用上述算法可以产生大的随机素数 (1)产生随机数p (2)确保p不被较小的素数整除。 (3)产生随机数a,利用上述算法检测p 的素性。直到经过多次测试为止
• 重复k次实验，那么p不是素数的可能性 不超过1/2^k. • 利用上述算法可以产生大的随机素数： • （1）产生随机数p; • （2）确保p不被较小的素数整除。 • （3）产生随机数a, 利用上述算法检测p 的素性。直到经过多次测试为止
素性判别的多项式算法 给定一个n位的整数,假设某一算法能在 f(n)步内判断出该整数是否素数。如果fn) 是一个多项式的话,则称该算法具有多 项式复杂性,称该问题是“多项式可解 的”。如果不存在一个算法其具有多项 式的计算复杂性,则称该问题属于NP问 题
• 素性判别的多项式算法 给定一个n位的整数，假设某一算法能在 f(n)步内判断出该整数是否素数。如果f(n) 是一个多项式的话，则称该算法具有多 项式复杂性，称该问题是“多项式可解 的”。如果不存在一个算法其具有多项 式的计算复杂性，则称该问题属于NP问 题