若m为素数,则有(m,m)=1且J(m,n 1)2modm。 若m不是素数,则等式J(m,n)=nm1modm 可能成立可能不成立。 有结论:对于奇合数,至多有一半使等式成 立,即至多有0.5的概率使上述等式成立。 若随机选择100个整数进行检验,上式均成立, 则m不是素数的概率小于21001030,因此可 认为m是素数。 23:31:48
23:31:48 若m为素数，则有(n,m)=1且J(m,n)= n(m- 1)/2mod m。 若m不是素数，则等式J(m,n)=n(m-1)/2mod m 可能成立可能不成立。 有结论：对于奇合数，至多有一半使等式成 立，即至多有0.5 的概率使上述等式成立。 若随机选择100个整数进行检验，上式均成立， 则m不是素数的概率小于2-100=10-30，因此可 认为m是素数
(1)如果n是奇数,m1=m2modn,则|m|="2|。 (2)如果n是奇数,则 1若n≡±1mod8 n(-1若n≡+3mo8 2如果n是奇数,则《)(mm) 特别当m2+t(t.奇数),则m 若m≡n≡3mod4 如果m和n是奇数,则(⑦) 否则 应用上述4个特性,可以在多项式时间内计算 Jacobi符 号 23:31:48
23:31:48 计算n(m-1)/2mod m有多项式时间算法， 那么怎么计算J(m,n)? 不能根据Jacobi符号的定义来计算， 因为只有在知道m的分解后才能计算， 而知道m的分解当然就知道m是否为素 数了 可以利用数论中的结果在不分解m的前 提下计算Jacobi符号。主要利用四条性 质： (1)如果 n 是奇数， m 1 = m 2 mod n，则 nm nm1 2 。 (2)如果 n 是奇数，则 1 3mod8 2 1 1mod8 nn n 若若 (3)如果 n 是奇数，则 nm nm n m1m2 1 2 。 特别当 m=2kt(t 为奇数)，则 nt n n m k 2 (4)如果 m 和 n 是奇数，则 否则若 m n m n m n n m 3mod4 应用上述 4 个特性，可以在多项式时间内计算 Jacobi 符 号
Miller-rabin检验法也是一个多项式时间算法, 它比 Solovay- Strassen检验法快,执行一次的 错误概率最多为1/4 ■对于奇整数n的 Miller-Rabin素性测试算法如 下 (1)令n-1=2km,m是奇数; ■(2)对i=1 to t do ①选择随机整数a(2≤a≤n-2); ②计算b= ammon; ③Ifb=modn, then n是素数and返回,else ④ If j=k then n是合数,算法终止 oIfb=1modn, then n是素数and返回, else计算b=b2modm,j=j计1,goto④ 23:31:48
23:31:48 Miller-Rabin检验法也是一个多项式时间算法， 它比Solovay-Strassen检验法快，执行一次的 错误概率最多为1/4 。 对于奇整数 n 的Miller-Rabin素性测试算法如 下： (1) 令n-1=2 k m，m是奇数； (2) 对i=1 to t do ①选择随机整数a(2 a n-2)； ②计算 b a mmodn; ③If b 1modn，then n是素数 and 返回,else 令j=1 ④If j=k then n是合数，算法终止 ⑤If b -1modn, then n是素数 and 返回， else 计算 b b 2modn, j=j+1,goto ④
确定性检验法是通过对给定的大整数进 行检验,下面介绍一种确定性检验法 ■采用了基于 Pocklington定理的特殊情形, 并将其改造为一递归算法加以实现 ■定理的特殊情形的描述: 定理:设n=2RF+1,其中F的真分解为 F=,如果存在整数a满足:anl=1modn 且(am)q-1,n)=1(j=1,…,r), 那么n的每一个素因子p具有p=mF+1的形式,其中 m21。更进一步,如果F>v或者F为奇数且F>R,那 么n是素数。 23:31:48
23:31:48 确定性检验法是通过对给定的大整数进 行检验，下面介绍一种确定性检验法。 采用了基于Pocklington定理的特殊情形， 并将其改造为一递归算法加以实现 定理的特殊情形的描述： 定理：设n=2RF+1，其中F的真分解为 F=，如果存在整数a满足:an-11mod n ， 且(a(n-1)/qj-1,n)=1( j=1,…r), 那么 n 的每一个素因子 p 具有 p=mF+1 的形式，其中 m 1。更进一步，如果 F> n 或者 F 为奇数且 F>R，那 么 n 是素数
7Y 函数 Prime Test(a)对较小的整数a进行有效地素性判 别,当且仅当a是素数时返回TRUE, 当且仅当a不能被小于等于b的素数除尽时,函数 " TrialDivision(ab)返回值为TRUE 函数 Checklemmal(n,q验证所给参数是否满足引理 中的条件,满足时可知n是素数,返回TRUE 温函数 GenRelativeS根据条件概率分布,可以从区 间 0.511中选择一个值作为相对规模 日函数 P2用于2的幂运算。 试除判定法的边界g被设定为某一常数copt的k2 倍,其中copt的最优值可通过试验来确定,这里取 为0.1。 常数 margin保证了R的取值范围应该足够大,以保 证该区间内至少包含一些成功的R。 算法可用来生成几乎随机的可证安全素数 23:31:48
23:31:48 在实际应用中，采用了一种易于实现的简化算法，只是所生成的 素数的差异性有所降低。 上述定理中令r=1 即F=q 。 下面给出函数RandomPrime 的 C语言描述 LongInt RandomPrime(int k) {if(k<=k0){do {n=Random(Power2(k-1),Power2(k)-1);} while(!PrimeTest(n));} else{g=c_opt*k*k; do{relative_size=GenRelativeSize(); kk= k*relative_size; }while(kk>k0 && kk>k-margin); q=RandomPrime( kk); success=FALSE; I=Power2(k-2)/q; while(!success) { R=Random(I,2*I); n=2*R*q+1; a=Random(2,n-1); if(TrialDivison(n,g))success=CheckLemmal(n,a,q);} } rerurn(n);} 函数 PrimeTest(a)对较小的整数 a 进行有效地素性判 别，当且仅当 a 是素数时返回 TRUE， 当且仅当 a 不能被小于等于 b 的素数除尽时，函数 TrialDivision ( a,b )返回值为 TRUE 。 函数 CheckLemmal(n,a,q)验证所给参数是否满足引理 中的条件，满足时可知 n 是素数，返回 TRUE 。 函数 GenRelativeSize 根据条件概率分布，可以从区 间 [0.5,1 ]中选择一个值作为相对规模。 函 数 Power2 用于 2 的幂运算。 试除判定法的边界 g 被设定为某一常数 c_opt 的 k 2 倍，其中 c_opt 的最优值可通过试验来确定，这里取 为 0.1 。 常数 margin 保证了 R 的取值范围应该足够大，以保 证该区间内至少包含一些成功的 R 。 算法可用来生成几乎随机的可证安全素数