密码学中的数论基础

数论是密码学的基本工具，尤其是公钥密码学。概念：研究“离散数字集合”运算为“”示例：整数：5 9=14；53=5 5=15多项式：x2 1 x=x2 x 1Xx2 1=x3 x，1。数论简介，计算概念，计算：模块化多项式运算为：指数运算，逆计算，除以，整数b！=0和a，如果有整数m，则a=mb，b称为a的系数。b|a示例1，2，3，4，6，8，12，24等于24，1 .系数：为a，b(b0)为两个整数，如果有其他整数m，则称为a=mb，b称为a | a，b称为a的系数。1.1小数和倒数小数，整数具有以下特性：a|1，如果是，a=1。a|b和b|a，a=b. 所有b(b0)，b|0。b|g，b|h对任意整数m，n有b|(mg NH)。1.1小数和相互小数，如果这里只给出证明，其他三种性质的证明就很简单了。特性证明：如b|g，b|h所示，因为有整数G1，h1，所以g=bg1，h=bh1，所以mg nh=mbg1 nbh1=b(mg1 nh1)，所以b|(mg NH)，1.1小数和倒数小数，2 .小数：表示p的系数为1，如果p，则整数p(p1)称为小数。所有整数a(a1)都可以唯一分解为以下形式：其中p1p2pt.pt是小数，ai0 (I=1，t)。例如，91=711，11011=711213，1.1小数和交叉小数，此特性可以称为整数分解的唯一性，也可以说明如下：如果将p设定为所有小数集，则可以用唯一的形式创建任意整数a(a1)。其中ap0，等号右侧的积取所有小数，但大多数指数项的ap为0。因此，正整数也可以显示为非零指数列表。例如，11011可以表示为a7=1，a11=2，a13=1。两个数字相乘等于相应的指数相加。也就是说，可以用k=mn得到。对于每个小数，p，kp=mp NP。适用于A|b:每个小数p，APBP。这是因为PK只能由pj(jk)分割。1.1小数和相互小数，3 .互素数是c是两个整数a，b的最大公因数，如果c是a的系数也是b的系数，那么c是a，b的公因数。a和b的所有共同因子也是c的因子。c=显示为gcd(a，b)。1.1小数和倒数小数，所需的最大公共元素为正数，因此gcd (a，b)=gcd (a，-b)=gcd (-a，b)=gcd (-a，-b)=gcd(-a，-b)。一般gcd(a，b)=gcd(|a|，|b|)。可以用非零整数除以零，gcd(a，0)=|a|。如果a，b全部表示为小数的乘积，则gcd(a，b)很容易判别。例如：300=223152；18=2132gcd(18，300)=213150=6通常可以通过c=gcd(a，b)获得。对于每个小数p，cp=min(ap，bp)。1.1小数和相互小数，因为确定大量的素元素并不容易，所以这种方法不能直接用于查找两个大数字的最大公共元素，下面讨论了查找两个大数字的最大公共元素的方法。如果Gcd(a，b)=1，则称为a和b交互。1.1小数和倒数小数，整数倒数，整数a，b倒数除1外没有其他系数8和15倒数8的系数1，2，4，815的系数1，3，5，151是唯一的公共系数，小数和不可约多项式，小数：是系数1及其自身1万个普通小数示例2，3，5，7是小数，4，6，8，9，10以外的素多项式或不可约多项式irreducible:不能用作其他参数X3 x 1是不可约多项式，部分小数，200个以下的小数3360111317192323133741434735961677173737989710107312731373137313731373151163171791811997199，小数分解，将整数n写为小数的性分