Fermat素数测试法 Bool Fermat Prime(int n)i a=2; power=n-1; other =1 while(power >1), if (power %2==1other *=a; other %/=n; 1 power /=2 a=a*a% n if(a other %n=-1)return True return False 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 11 Fermat素数测试法 ◼ Bool Fermat_Prime(int n) { ◼ a = 2; power = n – 1; other = 1; ◼ while(power > 1) { ◼ if (power % 2 == 1) {other *= a; other %= n;} ◼ power /= 2; a = a * a % n;} ◼ if (a * other % n == 1) return True; ◼ return False; ◼ }
合数的见证者 ■设n为测试的自然数,不妨设n是大于2的奇数, 则有n-1=2m,其中i是非负整数,m是正奇 数。取一自然数b,1<b<n,记W(b)为条件: ①b1≠1(modn)或 ②彐i,使得m=(n-1)2且1<gcd(bm-,n)<b。 若①或②中有一个为真,就认为W(b)满足,则 n必定是合数,我们称b是n为合数的见证者。 ■若n有见证者,则n必定为合数。 2021/22 计算机算法设计与分析 12
2021/2/21 计算机算法设计与分析 12 合数的见证者 ◼ 设n为测试的自然数，不妨设n是大于2的奇数， 则有n – 1 = 2im，其中i是非负整数，m是正奇 数。取一自然数b，1 < b < n，记W(b)为条件： ◼ ① b n–1 ≠ 1 (mod n) 或 ◼ ②i，使得m = (n–1)/2i 且 1 < gcd(bm–1 , n) < b。 ◼ 若①或②中有一个为真，就认为W(b)满足，则 n必定是合数，我们称b是n为合数的见证者。 ◼ 若n有见证者，则n必定为合数
合数的见证者多于一半 ■ Miller已经证明,存在常数c,使得当n为合数 时,在[,c(ogn)2]范围内有见证者 ■ Rabin证明了:如果n是合数,则 {b1lbn,W(b)满足}(n-1)/2 即,在小于n的自然数中有多半是n的见证者 ■任取一个自然数b<n,若b不是n的见证者,则 n是合数的概率小于1/2。若随机取m个数都不 是见证者,则n是合数的概率小于1/2m 2021/221 计算机算法设计与分析 13
2021/2/21 计算机算法设计与分析 13 合数的见证者多于一半 ◼ Miller已经证明，存在常数c，使得当n为合数 时，在[1, c(log n)2 ]范围内有见证者。 ◼ Rabin证明了：如果n是合数，则 |{b|1<b<n，W(b)满足}|≥(n–1)/2 即，在小于n的自然数中有多半是n的见证者。 ◼ 任取一个自然数b < n，若b不是n的见证者，则 n是合数的概率小于1/2。若随机取m个数都不 是见证者，则n是合数的概率小于1/2m