密码学课件JG1课件.ppt

素性检验方法 当k?3时， 。 当k=2时， 。若s1s2，则 ； 素性检验方法 若s1=s2，则这时“gcd(t, t1)t1”与“gcd(t, t2)t2”必至少有一个成立（否则，t1|t且t2|t，从2s?t=n-1=(p1-1)p2+(p2-1)=2s1t1 p2+2s2t2即知t1|t2且t2|t1，从而t1=t2；导致p1=p2），由于t, t1, t2都是奇数，故若gcd(t, t1)t1，则至少相差的一个因子3，即gcd(t, t1)?t1/3，从而 gcd(t, t1)? gcd(t, t2)?t1t2/3， 如此， 。 证毕。 素性检验方法 现在，可给出对一个正奇数n=1+2st（2?t）的米勒-罗宾素性检验的方法如下： 1?????????? a?R{1, 2, ?, n-1}. 2?????????? Compute b=at mod n. 3?????????? If b=1 then 3.1????????? Return (“n是素数”). 4?????????? For i from 0 to s-1 do 4.1????????? If b=n-1 then 4.1.1???? Return (“n是素数”). 4.2????????? Else 4.2.1???? b=b2 mod n. 5?????????? Return (“n是合数”). 素性检验方法 索洛维-斯特拉森检验与米勒-罗宾检验哪一个更好？ 对于一个为合数的正奇数n，经过索洛维-斯特拉森素性检验而回答“n是素数”的整数a所占的比例不超过50%与经过米勒-罗宾素性检验而回答“n是素数”的整数数a所占的比例不超过25%相比，似乎米勒-罗宾素性检验比索洛维-斯特拉森素性检验更有效些，但两个比例的总体分别为 {a|0?an, gcd(a, n)=1}与{a|0?an}而并不相同、致使人们不能真正肯定这一点，好在还有下述结果： 对于正奇数n，若其针对a (0an) 经过米勒-罗宾素性 检验而回答“n是素数”，则其针对同一个a经过 索洛维-斯特拉森素性检验也回答“n是素数”。 注. 上面结果的逆，当n?3 mod 4时是成立的；此外，考察n=65=5?13及a=14可知，其它情形却不一定成立。 习题 计算： (1) gcd(6188, 4709)；(2) 。 证明：对任意自然数n， 为整数； 若2 n，则8|(n2-1) ? 24|n(n2-1)； 若2 n ? 3 n，则24|(n2+23)。 证明下列命题等价： (1) n是大于4的合数；(2) n|(n-2)!；(3) n|(n-1)!。 证明：gcd(n!+1, (n+1)!+1)=1。 习题 设gcd(u, v)=1，试证明gcd(u+v, u-v)=1或2。 证明下列命题等价： (1) n是素数；(2) n|(n-1)!+1；(3) n|(n-2)!-1。 求解同余方程：23x?1 mod 140。 求解同余方程组： 习题 求以3为二次剩余的奇素数p。 分别求出使(1) (2) (3)x2?13 mod p 有解的全体素数p。 设对于正奇数n与整数a, 素数p|(an-1)，证明 。 设素数p=4m+1, d|m，证明 。 若素数p?3 mod 4使2p+1为素数，则(2p+1)|(2p-1)。 证明：(1)4a2+1的素因子?1 mod 4； (2)a4-a2+1的素因子?1 mod 12。 试求(1) x2?57 mod 27 (2) x2?10 mod 37 的所有根。 习题 设n=65=13?5， 对于a?{0, 1, 2, ?, n-1}, gcd(a, n)=1，证明： a使 9式成立的充要条件是a4?1 mod 13； “在11式中第一个不为1的数为n-1”的充要条件是a2?-1 mod 65或a?±1 mod 65。 (2) 试根据(1)分别求出： 使“在11式中第一个不为1的数为n-1” 的全部的a； 使“在11式中第一个不为1的数不为n-1”、但使10式成立的全部的a； 使10式不成立、但9式成立的全部的a。 习题 证明：13|(a2-7b2)（a, b?Z）的