数论2014.ppt

这样，Fermat小定理加强为如下形式： 尽可能提取因子2，把n-1表示成d*2^r，如果n是一个素数，那么或者a^d mod n=1，或者存在某个i使得a^(d*2i) mod n=n-1 ( 0≤ir ) 3、素性判定 对于大数的素性判断，目前Miller-Rabin算法应用最广泛。 一般底数仍然是随机选取，但当待测数不太大时，选择测试底数就有一些技巧了。 比如，如果被测数小于4759123141，那么只需要测试三个底数2, 7和61就足够了。当然，你测试的越多，正确的范围肯定也越大。 如果每次都用前7个素数(2, 3, 5, 7, 11, 13和17)进行测试，所有不超过341550071728320的数都是正确的。 如果选用2, 3, 7, 61和24251作为底数，那么10^16内唯一的强伪素数为46856248255981。 3、素性判定 if n 1373653, it is enough to test a = 2 and 3. if n 9080191, it is enough to test a = 31 and 73. if n 4759123141, it is enough to test a = 2, 7, and 61. if n 2152302898747, it is enough to test a = 2, 3, 5, 7, and 11. 随机算法的确定性 3、素性判定 通常认为，Miller-Rabin素性测试的正确率可以令人接受，随机选取 k个底数进行测试算法的失误率大概为4^(-k)。 3、素性判定 实现Eraosthenes（爱拉托斯尼）筛法及线性筛法 HDOJ-2012 练 习 若a∣b，则对所有整数c， a∣bc; 若a∣b， a∣c，则a∣（b＋c） 1能整除任何数，任何数都能整除0 * 性质3根据的是唯一分解定理 性质2根据p与a最大公约数为1，导出p整除b * 2i+3|p[i+xp[i]]=(2i+3)|2(i+x(2i+3))+3=(2i+3)|(2i+3)+2x(2i+3) * 爱拉托斯尼 * Tag[i]为bool数组，初始化=0表示i为素数,1表示合数，筛掉 * 我们把可以通过以a为底的Miller-Rabin测试的合数称作以a为底的强伪素数 * 工大ACM团队 湖南工业大学 ACM数论问题 一、数论中的著名问题： 高斯曾经说过“数学是科学的皇后，数论是数学中的皇冠”。因此，数学家都喜欢把数论中一些悬而未决的疑难问题叫做“皇冠上的明珠”，以鼓励人们去“摘取”。 1.哥德巴赫猜想：任一充分大的偶数都可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和，记作“a+b”（欧拉版本）。1966年陈景润证明了任何一个大偶数都可表示成一个素数与另一个素因子不超过2个的数之和”。 2.费马大定理：当整数n2时，关于x,y,z的不定方程xn+yn=zn无正整数解(x=0或y=0不在考虑之列).1994年德国数学家维尔斯解决了这个问题，并获得了沃尔夫奖. 3. 费马小定理： 假如a是一个整数，p是一个素数，则 1、素数的概念和性质 定义：设a,b为整数，且b≠0. 如果存在整数q，使得a=bq，那么称b整除a，记作b|a，并且称b是a的因数，a是b的倍数. 如果这样的整数q不存在，就称b不整除a，记作b | a . 素数（prime）和合数（compound）:如果一个整数p只有1和p两个因子，则p为素数，不为素数的其它数为合数。 性质： (1)每个正整数n除1外的最小正因数p是一个素数. (2)若p为素数，p|ab，则p|a或p|b (3)如果大于1的整数a不能被所有不超过 的素数整除，那么a一定是素数。 1、素数的概念和性质 问题： 1、给一个数n，小于n的素数有哪些？ 2、给一个数n，如何判断n是不是素数？ 最一般的求解n以内素数的算法。复杂度是o(n*sqrt(n))，适合n很小 num = 0; for(i=2; i=n; i++) { for(j=2; j=sqrt(i); j++) if( i%j==0 ) break; if( jsqrt(i) ) prime[num++] = i; } 1、素数的概念和性质 当n很大的时候，比如n=10,000,000时，n*sqrt(n)30,000,000,000,数量级相当大 思考如何改进？ 1、素数的概念和性质 2、素数筛法 最简单的素数筛法 开一个大的bool型数组p[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为false. 把奇数的倍数设为false.