《离散数学数论》课件.pptVIP

*****************课程概述数论是数学的核心它是关于整数性质的研究，从素数到同余关系等。计算机科学的基石数论在密码学、算法设计和计算机安全中扮演重要角色。培养逻辑思维学习数论可以增强逻辑推理能力，提高解决问题的能力。数论的基本概念整数整数是自然数、负数和零的统称。素数素数是指大于1的自然数，除了1和它本身之外没有其他因数的自然数。合数合数是指大于1的自然数，除了1和它本身之外还有其他因数的自然数。整除如果一个整数能被另一个整数整除，就称后者是前者的一个因数或因子。最大公约数和最小公倍数1定义最大公约数，英文为GreatestCommonDivisor，简称GCD，是两个数的公共因数中最大的一个2概念最小公倍数，英文为LeastCommonMultiple，简称LCM，是两个数的公共倍数中最小的一个3性质两个数的最大公约数和最小公倍数之积等于这两个数之积4应用最大公约数和最小公倍数在数学中有着广泛的应用，例如在约分、通分、求最大公约数、求最小公倍数、求最大公因数等等欧几里得算法1定义欧几里得算法是一种用于计算两个非负整数最大公约数（GCD）的经典算法。2步骤如果b等于0，则a是最大公约数，算法结束。将a除以b，得到余数r。令a等于b，b等于r，重复步骤1-3。3举例求12和18的最大公约数：18除以12余6，12除以6余0，因此6是12和18的最大公约数。扩展欧几里得算法核心思想求解线性方程ax+by=gcd(a,b)递归求解将问题转化为求解bx+(amodb)y=gcd(b,amodb)的解回溯求解从递归求解得到的结果中，回溯得到原方程的解应用场景求解模逆元，解决线性同余方程等数论问题素数理论素数定义素数是大于1的自然数，除了1和它本身以外不再有其他因数。例如，2、3、5、7、11都是素数。素数是数论研究中的基本元素，在密码学、信息安全等领域有着广泛的应用。素数判定判断一个数是否为素数，可以使用试除法，即从2到该数的平方根进行除法，如果能被整除，则该数不是素数。还有一些更高效的素数判定算法，例如米勒-拉宾素数判定法。费马小定理基本定理如果p是素数，a是一个整数，且a不是p的倍数，则a^(p-1)除以p的余数为1。应用费马小定理可用于求模运算中的逆元，以及解决一些数论问题，例如判断一个数是否是素数。证明费马小定理的证明可以通过利用模运算和组合数学知识完成，涉及到一些较为复杂的数学推理。欧拉函数1定义欧拉函数φ(n)表示小于等于n且与n互质的正整数的个数。2性质欧拉函数具有许多重要性质，例如积性性质、欧拉定理等，在数论中具有广泛的应用。3计算欧拉函数可以通过多种方法计算，包括素因子分解法和递归算法。4应用欧拉函数在密码学、信息安全等领域有着重要的应用。同余关系定义两个整数a和b模n同余，记作a≡b(modn)，当且仅当a-b能被n整除。性质自反性：a≡a(modn)对称性：若a≡b(modn)，则b≡a(modn)传递性：若a≡b(modn)且b≡c(modn)，则a≡c(modn)应用同余关系在数论中有广泛的应用，例如简化计算、证明定理、解决问题等。模运算1定义模运算是指将一个数除以另一个数，并取其余数的操作。2符号模运算用符号%或mod表示。3应用在密码学、计算机科学和数字理论中广泛应用。4性质模运算具有封闭性、结合律、分配律等性质。中国剩余定理基本原理该定理解决了一组线性同余方程的解。找到一个满足所有方程的整数解。应用场景密码学中广泛应用于密钥生成和数据加密。计算机科学中用于解决数据结构和算法问题。离散对数定义离散对数是指在模运算下，求解一个数的指数。应用离散对数在密码学中广泛应用，例如密钥交换和数字签名。求解求解离散对数通常需要使用专门的算法，如Baby-stepGiant-step算法。原根与阶循环群原根是循环群的生成元，它可以生成群中的所有元素。阶的定义元素的阶是指将该元素自身乘以自身若干次后才能得到单位元的最小次数。原根的性质一个数是模n的原根，当且仅当它的阶等于欧拉函数φ(n)。密码学应用数论在密码学中有着广泛的应用，特别是公钥密码体制。RSA、Diffie-Hellma