1、数论基础4.1 数论简介习题4.1.1 素数和互素数1. 因子设 a， b(b0)是两个整数，如果存在另一整数 m，使得 a=mb， 则称 b整除 a， 记为 b|a， 且称 b是 a的因子。4.1 数论简介数论是密码学特别是公钥密码学的基本工具，本章首先介绍密码学中常用的一些数论知识，然后介绍公钥密码体制的基本概念和几种重要算法。整数具有以下性质： a|1， 那么 a=1。 a|b且 b|a， 则 a=b。 对任一 b (b0)， b|0。 b|g， b|h， 则对任意整数 m、 n有 b|(mg+nh)。这里只给出 的证明，其他 3个性质的证明都很简单。性质 的证明： 由 b|g， b|h
2、知，存在整数 g1、 h1， 使得 g=bg1,h=bh1所以mg+nh=mbg1+nbh1=b(mg1+nh1),因此 b|(mg+nh)。2. 素数称整数 p(p1)是素数，如果 p的因子只有 1， p。任一整数 a(a1)都能惟一地分解为以下形式：其中 p1p2p t是素数， ai0(i=1,t) 。 例如91=711， 11011=711213这一性质称为整数分解的惟一性，也可如下陈述： 设 P是所有素数集合，则任意整数 a (a1)都能惟一地写成以下形式：其中 ap0,等号右边的乘积项取所有的素数，然而大多指数项 ap为 0。相应地，任一正整数也可由非 0指数列表表示。例如： 110
3、11可表示为a7=1,a11=2,a13=1。两数相乘等价于对应的指数相加，即由 k=mn 可得：对每一素数 p,kp=mp+np。 而由 a|b可得： 对每一素数 p,apbp。 这是因为 pk只能被 pj(jk)整除。3. 互素数称 c是两个整数 a、 b的最大公因子，如果 c是 a的因子也是 b 的因子，即 c是 a、 b的公因子。 a和 b的任一公因子，也是 c的因子。表示为 c=gcd(a, b)。由于确定大数的素因子不很容易，所以这种方法不能直接用于求两个大数的最大公因子，如何求两个大数的最大公因子在下面介绍。如果 gcd(a,b)=1， 则称 a和 b互素。由于要求最大公因子为正
4、，所以 gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。 一般 gcd(a,b)=gcd(|a|,|b|)。 由任一非 0整数能整除 0，可得 gcd(a,0)=|a|。 如果将 a， b都表示为素数的乘积，则 gcd（ a, b） 极易确定。例如：300=22315218=2132gcd(18,300)=213150=6一般由 c=gcd(a,b)可得： 对每一素数 p，cp=min(ap,bp)。设 n是一正整数， a是整数，如果用 n除 a， 得商为q， 余数为 r， 则a=qn+r,0rn, 其中 x为小于或等于 x的最大整数。用 a mod n表示余数
5、 r， 则 。如果 (a mod n)=(b mod n)， 则称两整数 a和 b模 n同余，记为 ab mod n。 称与 a模 n同余的数的全体为 a的同余类，记为 a， 称 a为这个同余类的表示元素。注意： 如果 a0(mod n)， 则 n|a。4.1.2 模运算同余有以下性质： 若 n|(a-b)， 则 ab mod n。 (a mod n)(b mod n)， 则 ab mod n。 ab mod n,则 ba mod n。 ab mod n,bc mod n,则 ac mod n。从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。求余数运算（简称求余运算） a mod n将整数 a映射到集合 0,1, , n-1， 称求余运算在这个集合上的算术运算为模运算，模运算有以下性质： (a mod n)+(b mod n) mod n=(a+b) mod n。 (a mod n)-(b mod n) mod n=(a-b) mod n。 (a mod n)(b mod n) mod n=(ab) mod n。
