a Solovay-strassen检验法的方法是如果要检验 m是否为素数,则在{1,2m-1}中随机取n, 并验证(n,m)是否等于1,和 Jacob符号J(m,n) 是否等于nm1/2modm。 这里J(m,n)=nn (m=p,,.p) p1八P2)(Pr n「1n是p的平方剩余 {-1n是P的非平方剩余 所谓平方剩余问题就是指,对于给定的一个奇数 n和整数a,决定a是否为模n的平方剩余,即判 定x2= a mod n是否有解,若有解,则a是modn的 平方剩余,否则a是模n的非平方剩余。 23:31:4823:31:48  Solovay-Strassen检验法的方法是,如果要检验 m是否为素数，则在{1,2,…m-1}中随机取n， 并验证(n,m)是否等于1，和Jacobi符号J(m,n) 是否等于n(m-1)/2mod m。  这里J(m,n)= (m=p1p2…pr)      prn pn pn  1 2    是 的非平方剩余 是 的平方剩余 ii i n p n p pn 1 1 所谓平方剩余问题就是指，对于给定的一个奇数 n和整数a，决定a是否为模n的平方剩余，即判 定x2=a mod n是否有解，若有解，则a是mod n的 平方剩余，否则a是模n的非平方剩余