ACM中的数学问题PPT教学课件

1、第二部分 素数相关 算术基本定理 筛法（筛法改进） 欧拉定理 素数测试 Pollard rho方法1第2页/共46页第1页/共46页第二部分 素数相关 算术基本定理 筛法（筛法改进） 欧拉定理 素数测试 Pollard rho方法2第3页/共46页第2页/共46页质数（素数） 定义 指在一个大于1的自然数中，除了1和自身外，不能被其他自然数整除的数。 合数：比1大但不是素数的数。 1和0既非素数也非合数。 素数与合数是相对的概念。素数，合数，0和1构成了全体自然数。3第4页/共46页第3页/共46页算术基本定理 任何一个大于1的自然数n,都可以唯一分解成有限个质数的乘积 n=p1r1p2r2.

2、pkrk p1p2.=1)，则a与b也互质 a1(mod b)，则a与b互质7第8页/共46页第7页/共46页常见的两数互质情况 两个不同的质数一定是互质数。 一个质数，另一个不为它的倍数，这两个数为互质数。 1和任意自然数都是互质。 相邻的两个自然数是互质数。 相邻的两个奇数是互质数。 较大数是质数的两个数是互质数。8第9页/共46页第8页/共46页二项式展开定理9第10页/共46页第9页/共46页筛法 目标:求出n以内的所有质数 算法步骤: 初始时容器内为2到n的所有正整数 取出容器中最小的数p,p一定是质数,删去p的所有倍数(注:只需从p2开始删除即可) 重复上述步骤直到容器为空10第1

3、1页/共46页第10页/共46页筛法11第12页/共46页第11页/共46页筛法评价 优点:算法简单,空间上只需要一个O(n)的bool数组 缺陷:一个数可能被重复删去多次,影响效率 例:在p=2,3,5,7时均会尝试删除210 一般的,若x有k个质因子,则x会被处理k次12第13页/共46页第12页/共46页筛法(改进) 改进: 初始时容器内为2到n的所有正整数 取出容器中最小的数p,p一定是质数 删去所有的pi, 令q为第一个未被删除的数,保留q,删去所有的piq, 再令q为下一个未被删除的数.直到q遍历所有未被删除的数为止(这一步骤可以把最小质因数为p的所有数删去) 重复上面两个步骤直到

4、容器为空13第14页/共46页第13页/共46页筛法(改进) 用bool数组+双向链表实现,空间复杂度仍为O(n) 小优化:初始时只加入奇数14第15页/共46页第14页/共46页欧拉函数的前奏 (a, m)=1, (a, n)=1 (a, mn)=1 若(m, n)=1, 则0至mn-1之间的数 所有的数用m, n 的余数表法唯一 有几个是m的倍数？有几个是n的倍数？ 有几个既是m的倍数，又是n的倍数？ 若该数不是m的倍数，则它与m互素吗？15第16页/共46页第15页/共46页欧拉函数的前奏 若m, n是两个不同的素数, 则0至mn-1之间的数 若该数不是m的倍数，则它与m互素吗？ 有几个

5、数与m互素？有几个数与n互素？ 既与m互素，又与n互素的数有几个？16第17页/共46页第16页/共46页例子 若m=3，n=7，则在020之间 3的倍数： 7的倍数： 与3互素的数： 与7互素的数： 既与3互素，又与7互素的数17第18页/共46页第17页/共46页欧拉函数 记(x)为与x互质且小于等于x的正整数的个数， (x)就是欧拉函数。18第19页/共46页第18页/共46页欧拉函数 性质1： 若p为素数，(p) = p-1. 性质2： 若p为素数，(pk)=pk-1(p-1) 性质3： 若(p, q)=1，(pq) = (p) (q) .19第20页/共46页第19页/共46页欧拉函

6、数 设x=p1r1p2r2.pkrk，则(x)=x*(1-1/p1)*(1-1/p2)*.*(1-1/pk) 证明： (piri， pjrj) = 1 (i != j) (x)= (p1r1)* (p2r2)* (pkrk) 又(pk)=pk-1(p-1) 所以结论得证20第21页/共46页第20页/共46页欧拉函数 递推形式：设x=p1r1p2r2.pkrk 若x中不含素数p，则(px)=(p)*(x)=(p-1) *(x) 若x中包含素数p，设第i个质因子为p，则(px)=p*(x)21第22页/共46页第21页/共46页欧拉函数 扩展:m的所有因子之和(p10+.+p1r1)(p20+.

7、+p2r2).(pk0+.+pkrk)22第23页/共46页第22页/共46页有关余数的简单性质 对于任意自然数N, 有1.在0 至N-1之间的数对N取模，所得的余数就是其本身； 2.任何连续N个自然数对N取模，所得的余数取满了0至N-1之间的每一个数； Eg. N = 10, 连续10个整数：2,3,4,11 余数：2,3,4,5,9,0, 13.任何连续N个自然数乘以一个与N互素的数，所得的余数取满了0至N-1之间的每一个数23第24页/共46页第23页/共46页欧拉定理 欧拉定理：若a和m互质,则a(m)1(mod m) 证明:设(m)个正整数r1,r2,.,r(m)满足:ri与m互质,

8、对于任意ij,rirj(mod m)由于a与m互质,可以证明ar1,ar2,.,ar(m) 对m取余依然满足上述条件 这样就有(ar1)(ar2).(ar(m) ) r1r2.r(m)(mod m)而(ar1)(ar2).(ar(m) ) a(m) r1r2.r(m)(mod m)a(m) r1r2.r(m) r1r2.r(m)(mod m)(a(m) -1) r1r2.r(m) 0 (mod m)又r1r2.r(m) 与m互素，所以得到欧拉定理24第25页/共46页第24页/共46页欧拉定理 利用欧拉定理求下列余数 310 mod 5 513 mod 11 3200 mod 1725第26页

9、/共46页第25页/共46页?3200 mod 110526第27页/共46页第26页/共46页?6200 mod 1027第28页/共46页第27页/共46页求形如ab mod c 的余数问题 ab mod c 的情形讨论 a与c互素； a与c不互素； 方法 欧拉定理 二进制原理 中国剩余定理28第29页/共46页第28页/共46页求形如ab mod c的余数问题 513 mod 11 l6 100 mod 10 l3200 mod 1105 29第30页/共46页第29页/共46页求形如ab mod c 的余数问题 利用二进制原理一般解法（如 513 mod 11 ） 目标：将大数的求余转

10、化为较小数的求余 步骤： 将指数用二进制表示 13 = 20 + 22 + 23 =1 + 4 + 8 改写原数 513 = 5 * 54 * 58 研究5i 对11取模的数直到最高位 5 5; 523; 549; 584; (mod 11) 513 5*9*44(mod 11)30第31页/共46页第30页/共46页求形如ab mod c的余数问题 l利用中国剩余定理的一般解法（如6 100 mod 10 ）令x = 6 100, 又10 = 2 * 5计算x mod 10 等价于求解同余式组 x b1(mod 2) x b2(mod 5)找一个最小正整数，使得x满足以下同余式组 x 0(m

11、od 2) x 1(mod 5)解得x = 6 就是所求的余数。31由欧拉定理计算得到b1=0, b2 = 1第32页/共46页第31页/共46页 求 3200 mod 110532第33页/共46页第32页/共46页 求 6 100 mod 10 33第34页/共46页第33页/共46页 求 2 1000000 mod 77 34第35页/共46页第34页/共46页不开口算你姓35第36页/共46页第35页/共46页数论题目推荐 2342、1528、1953 (都是赤裸裸的) 进阶题目： POJ 1091、POJ 1619、POJ 1845、POJ 2478、POJ 2480、POJ 260

12、3、POJ 2649、POJ 2773、POJ 2992、POJ 329236第37页/共46页第36页/共46页素数测试 费马小定理:若p为素数,则对于任意小于p的正整数a,有a(p-1)1(mod p) 证明:欧拉定理的特例(m为质数) 问题:只是必要条件,不是充分条件(仅对2测试成立) 反例:561,1105,1729.37第38页/共46页第37页/共46页素数测试 二次探测定理:若p为素数,a21(mod p)小于p的正整数解只有1和p-1 满足费马小定理和二次探测定理的数可以确定是素数38第39页/共46页第38页/共46页Miller-Rabin算法 Miller-Rabin算法

13、(n为待判定数): 令n-1=m*2j,m为奇数 随机在2(n-1)之间取一个整数b,令v=bm 对v平方,当v=1时,若上一次的v既不是1也不是(n-1),由二次探测定理,n不是素数,退出;循环j次得到b(n-1) v=1,满足费马小定理,通过测试;否则n一定不是素数 选取几个不同的b进行多次测试39第40页/共46页第39页/共46页素数测试 Miller-Rabin只能算一种测试,因为通过测试的数不一定是素数,非素数通过测试的概率大约是1/4 虽然一次测试的结果不一定令人满意,但五六次随机测试基本可以保证正确率超过99.9%40第41页/共46页第40页/共46页大整数分解 至今仍是世界

14、难题 在密码学中起着至关重要的作用 试除法,Fermat方法,Pollard方法 Pollard rho方法41第42页/共46页第41页/共46页Pollard rho方法 原理: 设n为待分解的大整数 用某种方法生成两个整数a和b,计算p=gcd(a-b,n),直到p不为1或a,b出现循环为止 若p=n,则n为质数,否则p为n的一个约数42第43页/共46页第42页/共46页Pollard rho方法 算法步骤: 选取一个小的随机数x1 迭代生成xi=x(i-1)2+k,一般取k=1,若序列出现循环则退出 计算p=gcd(x(i-1)-xi,n),若p=1,返回上一步继续迭代;否则跳出迭代过程 若p=n,则n为素数;否则p为n的一个约数并递归分解p和n/p43第44页/共46页第43页/共46页Po