欢迎来到三一文库! | 帮助中心 三一文库31doc.com 一个上传文档投稿赚钱的网站
三一文库
全部分类
  • 研究报告>
  • 工作总结>
  • 合同范本>
  • 心得体会>
  • 工作报告>
  • 党团相关>
  • 幼儿/小学教育>
  • 高等教育>
  • 经济/贸易/财会>
  • 建筑/环境>
  • 金融/证券>
  • 医学/心理学>
  • ImageVerifierCode 换一换
    首页 三一文库 > 资源分类 > PPT文档下载  

    第一讲数论初步.ppt

    • 资源ID:3112142       资源大小:108.52KB        全文页数:12页
    • 资源格式: PPT        下载积分:4
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录 QQ登录   微博登录  
    二维码
    微信扫一扫登录
    下载资源需要4
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    第一讲数论初步.ppt

    第一讲 数论初步,-喻鹏举,基本概念,数论是研究数的性质的学科,数论基本上可分为初等数论、解析数论、代数数论等几个较大的分支。,整数的整除性,整除与约数、倍数. 注意负数 a除以非0整数b商为整数,且余数为零。 (我们就说a 能被b整除或说b能整除a,记作b|a) 可整除性的基本性质 若a|b, a|c, 则a|(b+c) 若a|b, 那么对所有整数c, a|bc 若a|b, b|c, 则a|c 整除关系具有传递性.,素数和合数,如果大于1的正整数p仅有的正因子是1和p, 称 p为素数(prime) 大于1又不是素数的正整数称为合数(compound) 如果n是合数, 则n必有一个小于或等于n1/2的素因子,算术基本定理,每个正整数都可以惟一地表示成素数的乘积,其中素数因子从小到大依次出现(这里的“乘积”可以有0个、1个或多个素因子)。 换句话说, 任意正整数n可以写成n=2a1*3a2*5a3*,其中a1,a2,a3等为非负整数 这个定理也叫做惟一分解定理。它是一个定理而不是公理!虽然在大多人看来,它是“显然成立”的,但它的确是需要证明的定理,除法和同余,令a为整数,d为正整数,那么有惟一的整数q和r,其中0rd,使得a=dq+r 可以用这个定理来定义除法:d叫除数,a叫被除数,q叫商,r叫余数。如果两个数a,b除以一个数c的余数相等,说a和b关于模c同余,记作ab(mod c),最大公约数和最小公倍数,令a和b是不全为0的两个整数,能使d|a和d|b的最大整数称为a和b的最大公约数,用gcd(a,b)表示,或者记为(a,b)。 令a和b是不全为0的两个整数,能使a|d和b|d的最小整数称为a和b的最小公倍数,用lcm(a,b)表示,或者记为a,b 定理: ab = gcd(a,b) * lcm(a,b) 如果gcd(a,b)=1 ,a,b互质,定理的证明,使用惟一分解定理. 设 则有:,容易验证定理成立,求出1 n的全部素数;,法一:Eratosthenes的筛子 2是素数, 删除2*2, 2*3, 2*4, , 2*50 第一个没被删除的是3, 删除3*3, 3*4, 3*5,3*33 第一个没被删除的是5, 删除5*5, 5*6, 5*20 得到素数p时, 需要删除 p*p, p*(p+1), p*n/p, 运算量为n/p-p, 其中p不超过n1/2(想一想, 为什么) 近似公式(Legendre常数B=-1.08366),素数判定,枚举法: O(n1/2), 指数级别 改进的枚举法: O(phi(n1/2)=O(n1/2/logn), 仍然是指数级别 概率算法: Miller-Rabin测试 + Lucas-Lehmer测试 对于奇数n, 记n=2r*s+1, 其中s为奇数 随机选a(1=a=n-1), n通过测试的条件是 as1(mod n), 或者 存在0=j=r-1使得a2j*s-1(mod n) 素数对于所有a通过测试, 合数通过测试的概率不超过1/4 只测试a=2, 3, 5, 7, 则2.5*1013以内唯一一个可以通过所有测试的数为3215031751,最大公约数,方法一: 使用惟一分解定理, 先分解素因数, 然后求最大公约数 方法二: (Euclid算法) 利用公式gcd(a, b)=gcd(b, a mod b), 时间复杂度为O(logb) 方法三: (二进制算法) 若a=b, gcd(a,b)=a, 否则 A和b均为偶数, gcd(a,b)=2*gcd(a/2,b/2) A为偶数, b为奇数, gcd(a,b)=gcd(a/2,b) 如果a和b均为奇数, gcd(a,b)=gcd(a-b,b) 不需要除法, 适合大整数,小小动脑,

    注意事项

    本文(第一讲数论初步.ppt)为本站会员(本田雅阁)主动上传,三一文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一文库(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    经营许可证编号:宁ICP备18001539号-1

    三一文库
    收起
    展开