密码学中的数论基础教学课件_第1页
密码学中的数论基础教学课件_第2页
密码学中的数论基础教学课件_第3页
密码学中的数论基础教学课件_第4页
密码学中的数论基础教学课件_第5页
已阅读5页，还剩106页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1.数论简介一数论是密码学持别是公钥密码学的基本工具数论概念研究“离散数字集合运算是“+”,“■例:整数:5+9=14;5×3=5+5+5=15多项式:x2+1+X=x2+x+1;X×x2+1=x3+X运算概念算模数运算模多项式运算进一步运算:指数运算,逆运算整除对整数b=0及a,如果存在整数m使得a=mb,称b整除a,也称b是a的因子记作b|a■例1,2,3,4,6,8,12,24整除241.1素数和互素数1.因子:设a,b(b≠0)是两个整数,如果存在另一整数m,使得a=mb,则称b整除a,记为ba,且称b是a的因子1.1素数和互素数整数具有以下性质:①al1,那么a=±1②2ab且ba,则a=±b③对任-b(b≠0),b|0。④4bg,bh则对任意整数m、n有b(mg+nh)1.1素数和互素数这里只给出④的证明,其他3个性质的证明一都很简单。性质④的证明:由bg,bh知,存在整数g1、h1,使得g=bg1h=bh1所以mg+nh=mbg1+nbh1=bmg1+nh1),因此b(mg+nh)。11素数和互素数2.素数:称整数p(p>1)是素数,如果p的因子只有±1,±p。任一整数a(a>1)都能惟一地分解为以下形式工y2其中p1>p2>.p是素数,a>0(=1,例如91=7×11,11011=7×112×1311素数和互素数这一性质称为整数分解的惟一性,也可如下陈述设P是所有素数集合,则任意整数a(a>1)都能惟一地写成以下形式a=l其中a20,等号右边的乘积项取所有的素数,然而大多指数项a为0。相应地,任一正整数也可由非0指数列表表示。例如:11011可表示为={a=1a1=2a18=1}两数相乘等价于对应的指数相加,即由k=m可得对每一素数pk=m+n。而由ab可得:对每素数papb。这是因为pk只能被p(≤k)整除。1.1素数和互素数3.互素数称C是两个整数a、b的最大公因子,如果①c是a的因子也是b的因子,即c是a、b的公因子。②2a和b的任一公因子,也是c的因子。表示为c=gc(a,b)11素数和互素数由于要求最大公因子为正,所以gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,b)般gcd(a,b)=gcd(al,b)。由任一非0整数能一整除0,可得gcd(a,0)=|al。如果将a,b都表示为素数的乘积,则gcd(a,b)极易确定。例如:300=22×31×52;18=2

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论