第4 章 公钥密码4.1 数论基础知识4.2 公钥密码的基本概念4.3 RSA 公钥密码4.4 ElGamal 公钥密码4.5 Rabin 公钥密码4.6 椭圆曲线公钥密码现代密码学电子科技大学4.1 数论基础知识现代密码学电子科技大学电子科技大学 现代密码学认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“ 精准扶贫” 项目素数与互素u定义1 对于整数a, b（b 0），若存在整数x使得b=ax，则称a整除b，或a是b的因子，记作a|b。u定义2 若a, b, c都是整数，a和b不全为0且c|a, c|b，则称c是a和b的公因子。如果整数d满足：u d是a和b的公因子；u a和b的任一公因子，也是d的因子。u则称d是a和b的最大公因子，记作d =gcd (a, b)。如果gcd (a, b)=1，则称a和b互素。u定义3 若a, b, c都是整数，a和b都不为0且a|c, b|c，则称c是a和b的公倍数。如果整数d满足： d是a和b的公倍数； d整除a和b的任一公倍数。 则称d是a和b的最小公倍数，记作d =lcm (a, b)。
