定理对于任何非负的整数a和b-湖南大学.ppt

* Page: * 有限域(Galois Field)：域的概念 域由一个非空集合F组成，在集合F中定义了 两个个二元运算“+”和“.”。满足以下性质的代数系统称为域，记为{F, +, .} F关于加法“+”是一个交换群，其单位元是“0”，a的逆元是-a； F关于乘法“.”是一个交换群，其单位元是“1”，a的逆元是a-1； 分配律：对任意的a,b,c∈F，有 a . (b + c) = a . (b + c) = a . b + a . c； 无零因子：对任意的a,b,c∈F，如果a . b = 0，则a = 0或b = 0。 例一：Q, +, .是域，其中Q是有理数集合。 * Page: * 有限域(Galois Field)：有限域的概念 有限域是指域中元素个数有限的域，元素个数称为域的阶。 若q是素数的幂，即q = pr，其中p是素数，r是自然数，则称阶为q的域称为Galois域(有限域)，记为GF(q)或GF(pr)或Fq。 当r = 1时，有限域GF(q)称为素域。 * Page: * 密码学数学引论组成 数论：研究整数性质的一个数学分支，重点研究素数。 群论：一种代数系统，重点研究在整数上的代数运算。 有限域理论：一种代数系统，比群更加复杂。 计算复杂性理论：分析不同密码技术的算法和问题复杂性的方法，并进行比较，确定其安全性。 * Page: * 计算机复杂性理论：算法的复杂性 近代密码分析学取决于攻击方法在计算机上编程实现时所需的计算时间(时间复杂度)和占用的硬件资源(空间复杂度)。——平均复杂度。 如果用n表示问题的大小/输入的长度，计算复杂性可用两个参数来表示：T(n)和S(n)。如果T(n)=O(nc)(c0)，则称该算法是时间多项式的；如果T(n)=O(ap(n))(a0)，则称该算法是时间指数级的，其中p(n)是一个多项式。如果一个算法是时间指数级的，则认为是计算上安全的。 确定性算法和不确定性算法：区别在于算法的每一步操作结果是否确定。 * Page: * 计算机复杂性理论：算法的复杂性 * Page: * 计算机复杂性理论：算法的复杂性 例一：确定以下算法的时间复杂度和空间复杂度 int Prime(int n) { int i = 2, x = (int) sqrt(n); while (i = x) { if (n % i == 0) break; i++; } if (i x) return 1; else return 0; } Answer：T(n)=O(sqrt(n)) 　　　S(n)=O(1) * Page: * 计算机复杂性理论：问题的复杂性 P问题类：多项式时间内可以用确定性算法求解的问题称为P问题类。 NP问题：多项式时间内可以用非确定性算法可判别的问题称为NP问题类。(猜测 + 验证) NPC问题类：NP问题类中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间算法，那么所有NP问题都是多项式时间可解的。——SAT问题 * * * Page: * 密码学数学引论 杨秋伟 湖南大学 计算机与通信学院 * Page: * 密码学数学引论组成 数论：研究整数性质的一个数学分支，重点研究素数。 群论：一种代数系统，重点研究在整数上的代数运算。 有限域理论：一种代数系统，比群更加复杂。 计算复杂性理论：分析不同密码技术和算法的计算复杂性的方法，并进行比较，确定其安全性。 * Page: * 数论：整除 整除：设整数a和b，且a≠0。如果存在整数k使得b = ak，那么就说b能被a整除，记做a|b，或者说b是a的倍数。 整除的性质 对所有的整数a，a|0和a|a成立。同理，对任意的整数b，1|b 成立； 如果a|b且b|c，则a|c 成立； 如果a|b且a|c，则对所有的整数s和t，a|sb+tc。 * Page: * 数论：素数 如果整数p(p1)只能被1或者是它本身整除，而不能够被其他整数整除，则称整数p为素数。 素数定理：设π(x)是小于x的素数的个数，则 π(x) ≈ x / lnx * Page: * 数论：素数 算术基本定理：任何一个正整数都可以分解为几个素数的乘积，且该因数分解是唯一的，除非颠倒因子的顺序。 补充定理：如果p是一个素数，且乘积ab能被p整除，那么p|a 或者p|b。更一般地，如果乘积ab……z能够被素数p整除，那么ab……z