现代密码学(中山大学)Lecture04.ppt

素性判定 Fermat定理：ap-1=1 mod p Euler定理：a ?(n) =1 mod n 素性判定：Fermat 定理的逆定理不成立， 满足条件的合数叫 Carmichael 数，最小的 是 561=3×11×17。 判定一个整数是不是素数在数论和密码学中都有着重要的应用 ECPP是一个概率检测算法，但它是一种零错误概率算法。改进的Atkin-Morain算法的计算时间复杂度是O(log4n)，这使得它成为首选的素性检测方法。尽管现在已经有确定性多项式时间素性检测算法，即三个印度人Agrawal, Kayal和Saxena于2002年发明的AKS算法，但他们的算法复杂度是O(log12n)。Lenstra和Pomerance对AKS算法进行改进，使得该确定性算法的运行时间复杂度到了O(log6n)。目前ECPP是依然是最快和最广泛使用的素性检测方法。 二次剩余 定义： x2=a mod n 有解，则a 称为mod n 的一个二次剩余，否则称为mod n 的一个二次非剩余。 定理：令p是一个素数 1）QRp={x2 mod p | 0x= (p-1)/2} 2) 二次剩余和二次非剩余各有(p-1)/2个。 Euler 准则 令p是一个素数，那么对任意的x \in Zp*, x是mod p 的二次剩余的充分必要条件是： x (p-1)/2 =1 mod p Legendre-Jacobi 符号 定义： Legendre 符号：（x/p）= 1 x \in QRp ； -1 其它。 Jacobi符号： （x/n）= （x/pi）ei ， n=∏piei 近世代数基本概念 若干个（有限或无限多个）固定事物的全体叫做一个集合。 组成一个集合的事物叫做这个集合的元素（有时简称元）一个没有元素的集合叫空集合。 集合A和集合B的所有共同元素组成的集合叫做A和B的交集A∩B。 由至少属于A和B之一的一切元素组成的集合叫做A和B的并集A∪B。 令A1，A2，…,An是n个集合，由一切从A1，A2，…,An里顺序取出的元素组（ a1，a2，…,an）（ai∈Ai）所做成的集合叫做A1，A2，…,An的积，记成A1×A2 ×…×An 映射和代数运算 假如通过一个法则φ，对于任何一个A1×A2 ×…×An的元素（ a1，a2，…,an） （ai∈Ai），都能得到一个唯一的集合D的元素d，那么这个法则φ叫做集合A1×A2 ×…×An到集合D的一个映射。元素d叫做元素（ a1，a2，…,an）在映射φ之下的象;元素（ a1，a2，…,an）叫做元素d在映射φ之下的逆象。 一个映射常用以下符号来描写， φ： （ a1，a2，…,an） →d= φ（ a1，a2，…,an） 一个A×B到D的映射叫做一个A×B到D的代数运算。 一个代数运算用?来表示，?: (a,b) → d=?(a,b) 为方便起见, ?(a,b)可以写成a?b 代数运算定律 假如?是一个A×A到A的代数运算，我们就说，集合A对于代数运算?来说是封闭的，也说?是A的代数运算或二元运算。 一个集合A的代数运算?适合结合律，假如对于A的任何三个元a,b,c来说，都有(a ?b) ?c=a ?(b ?c) 一个A×A到D的代数运算?适合交换律，假如对于A的任何两个元a,b来说，都有a ?b= b?a 代数运算⊙ ⊕适合分配律，假如对于B的任何元素b，A的任何元素a1,a2来说，都有b ⊙(a1⊕a2）=（b ⊙ a1 ） ⊕ （b ⊙ a2 ） 或者， (a1⊕a2）⊙b =（ a1 ⊙ b） ⊕ （ a2 ⊙b ） 群（Group） 群G，有时记做{G, ?}，是定义了一个二元运算的非空集合，这个二元运算可表示为? ，G中的每一个序对(a,b)通过运算生成G中的元素(a ? b)，并满足以下公理： ①封闭性：如果a 和 b都属于G，则 (a ? b)也属于G 。 ②结合律成立：a ?(b ? c)=(a ? b) ? c，对于G的任意三个元素都a,b,c成立 ③单位元：G里至少存在一个元素e，对于G的任何元a，都有e ? a=a ? e=a成立。 ④逆元：对于G的每一个元素a，在G里至少存在一个元素a’，使得a’ ? a=a ? a’=e成立。 群论—近代代数学的基本概念之一 Hermann Weyl: “Galois’ ideas, which for several decades remained a book with seven seals but later exerted a more and more profound influence upon the whole de