Updates from 四月, 2016 Toggle Comment Threads | 键盘快捷键

  • jinzihao pm6:18 on 2016年4月30日 链接地址 | 回复  

    缓冲区溢出漏洞入门笔记  

    最近在了解缓冲区溢出漏洞的发现和利用,完全零基础…
    看了一些文章了解到一些入门内容,但水平还不足以写篇文章总结一下…
    就把自己看过的文章在这里分享一下吧,应该这些文章结合起来看看就可以入门了:

    这篇文章很适合入门,从基础概念讲起,给了很多示例:
    http://www.xfocus.net/articles/200708/%BB%BA%B3%E5%C7%F8%D2%E7%B3%F6%B9%E2%CB%D9%C8%EB%C3%C5.pdf

    稍微进阶一点的文章,示例也很多:
    http://linux.ximizi.com/linux/linux5570.htm

    乌云上的一篇概述性的文章,介绍了很多常用工具:
    http://drops.wooyun.org/binary/6521

    前几篇文章里提到的shellcode在这里有系统性的介绍:
    http://www.xfocus.net/articles/200805/980.html

    一个方便的测试shellcode的工具,里面也给出了一段经典的shellcode:
    http://www.secdev.org/projects/eggrun/

    关于C语言的函数调用栈,大多数情况下需要对函数调用栈有些基本了解才可以利用缓冲区溢出漏洞:
    http://www.cnblogs.com/clover-toeic/p/3755401.html

    用gdb查看内存数据的方法(必备技能),gdb的更多用法可自行搜索:
    http://eminzhang.blog.51cto.com/5292425/1256022

    关于ret2libc攻击方法,缓冲区溢出漏洞的利用方法之一:
    http://blog.csdn.net/linyt/article/details/43643499

    ret2libc的一个实例:
    http://geeksspeak.github.io/blog/2015/05/18/defconctf-2015-quals-ropbaby-writeup/

    乌云上介绍ret2libc的一篇文章,很详细:
    http://drops.wooyun.org/binary/13554

    一篇介绍ROP(缓冲区溢出漏洞的一类利用方式)的文章,很详细:
    http://codearcana.com/posts/2013/05/28/introduction-to-return-oriented-programming-rop.html

    一组示例,可以检验一下自己对各种攻击方式的理解是否正确:
    http://5alt.me/posts/2014/09/Protostar%20stack%200-7%20writeup.html

    另外一篇系统性地介绍ROP的文章:
    http://drops.wooyun.org/tips/6597

    一个ROP的例子,可以验证一下自己的理解:
    http://www.ricter.me/posts/Vortex12%20Writeup%20-%20The%20First%20ROP%20I%20Wrote

    另一个关于ret2libc的例子,对抗地址随机化的一种思路:
    http://lieanu.github.io/2014/12/08/SCTF-pwn200.html

     
  • jinzihao am11:42 on 2016年4月23日 链接地址 | 回复  

    初等数论 – 期中复习 

    期中复习

    2016年4月21日

    20:02

    第一章

    公理:良序性质(WOP):非空正整数集合有最小元

    有理数:可以表示为p/q的数,p和q是整数,q不是0

    T1.1:根号2是无理数

    证明:反证,如果根号2是有理数,构造一个这样的集合,其中的元素本身和它的根号2倍都是正整数,这个集合有最小元,这最小元的根号2倍减去这个最小元也是正整数,且它乘上一个根号2还应该是正整数,这就推出矛盾了,因为最小元的根号2倍减去这个最小元大概只有最小元的0.414倍,比最小元更小 (WOP)

    整系数多项式的根是代数数

    中括号表示下取整

    一个数的小数部分可以用一个数减去一个数的下去整来表示,可以用大括号表示

    T1.2 鸽巢原理:k+1个物体装入k个箱子,必有箱子里装着不止一个物体

    证明:反证,不用定理或公理

    T1.3 狄利克雷逼近原理:对于任意实数alpha,任取一个n,都有不超过n的整数a,与另一个整数b,使a倍的这个实数alpha与b的差在1/n以内

    证明:考虑这个实数alpha的0倍、1倍、2倍直到n倍,这n+1个数的小数部分落在0~1/n, 1/n~2/n, … (n-1)/n~1这n个区间里,必有一个区间里有两个数,这两个数的差不到1/n。记住这落在同一个区间的两个数{k*alpha}和{j*alpha},记住它们分别是这个实数的多少倍k和j,这两个倍数之差k-j作为a,这个实数的这两个倍数倍各自下取整再做差[k*alpha]-[j*alpha]作为b,这就构造出了满足要求的a和b了。 (T1.2)

    可数集合:可以和正整数一对应的集合

    T1.4 有理数集是可数的

    证明:只要说明有理数是可列的就可以了。按照这样的顺序排列有理数:

    0/1 1/1 -1/1 2/1 -2/1 3/1
    0/2 1/2 -1/2 2/2 -2/2 3/2
    0/3 1/3 -1/3 2/3 -2/3 3/3
    0/4 1/4 -1/4 2/4 -2/4 3/4
    0/5 1/5 -1/5 2/5 -2/5 3/5

    按照对角线从右上到左下,碰到边界之后向下一格,再从左下到右上,碰到边界后向右一格,再从右上到左下,往复进行直至无穷…

    T1.5 数学归纳法原理:如果一个集合有1,而且如果有k必有k+1,则所有正整数概莫能外

    证明:假设真有不在这个集合里的正整数,那这样的数必有最小的一个n,这最小的一个n一定不是1,那么比最小的这一个还小1的那个数n-1应该在集合里。n-1在集合里,而n不在集合里,这就推出了矛盾。(WOP)

    T1.6 第二数学归纳法:如果一个集合里有1,而且如果所有不超过n的数都在集合里则必有n+1也在集合里,则所有正整数概莫能外

    证明:考虑这个集合T的这样一个子集S:总能找到一个n,不超过n的数都在这个集合T里(从1往上试就好了),把这些不超过n的数都放入这个子集S里,那么n+1也可以放进去了(因为1到n全部都在T里面,那么n+1也应该在T里面了,那么不超过n+1的数都在T里面了,那么n+1也可以放进S里面了。)也就是说,如果不超过n的数在S里面,那么不超过n+1的数也都在S里面,又因为不超过1的数在S里面,用第一数学归纳法可证明所有正整数都在S里面,S又是T的子集,所以所有正整数都在T里面 (T1.5)

    斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

    T1.7 斐波那契数列的通项:fn=1/sqrt(5)*(alpha^n-beta^n),其中alpha=(1+sqrt(5))/2, beta=(1-sqrt(5))/2

    证明:略

    什么是整除?有b=ac存在,c是个整数,那么a能整除b

    T1.8 a能整除b,b能整除c,那么a能整除c

    证明:根据定义证明,b=ma, c=nb, 那么c=n*m*a=(nm)a

    T1.9 c能整除a,c能整除b,那么c能整除(m*a+n*b)

    证明:根据定义证明,a=pc,b=qc,那么ma+nb=mpc+nqc=(mp+nq)c,也能被c整除

    T1.10 除法算法:给定正整数b,整数a一定能唯一地表示为bq+r的形式,r是小于b的正整数

    证明:将所有非负的a-bk构成一个集合,这里有最小元a-bq,把a-bq记为r,r一定是不超过b的,因为如果超过b了,就能构造出比r还小的正整数a-b(q+1)了,这就矛盾了。这样就找到了满足要求的q和r了,再证q和r是唯一的:如果能构造出两组q1, r1和q2, r2,那a=q1*b+r1=q2*b+r2,那(q1-q2)*b=r2-r1,那b能整除r2-r1,因为r1、r2都是小于b的正整数,r2-r1也不会超出-b到b这个开区间,注意是开区间,所以-b和b都取不到,所以r2-r1只可能是0,那r2和r1就是同一个数了,那a-r不可能既是b的q1倍又是b的q2倍,q1和q2也必须是同一个数 (WOP)

    最大公约数:最大的能整除a和b的整数,记作(a, b)

    互素:如果(a, b)=1就称a、b互素

     

    第三章

    素数:正整数里除了1和它本身没有能整除它的数(要求是大于1的正整数)

    L3.1:大于1的整数都有素因子

    证明:用反证法,没有素因子的大于1的整数构成一个集合,这集合应该有最小元n,n是不是素数呢?不是。因为n能整除n,n是n的因子,n没有素因子,n作为n的因子必须不是素数。那么n就是合数,那么n就能写成a*b的形式,a和b都比n小。既然n是最小的没有素因子的大于1的整数,那a一定有素因子,由T1.8,a的因子也是n的因子,而这是个素因子,矛盾!(WOP, T1.8)

    T3.1:素数有无穷多个

    证明:假设素数只有有限多个,将这些素数p1p2…pn都乘在一起再加1,由L3.1,这个数Qn应该有素因子。但谁是它的素因子呢?素数只有有限多个,假如其中某一个pj是这个数Qn的素因子,那pj能整除Qn,pj能整除p1p2…pn,那由T1.9,pj也能整除1*Qn+(-1)*(p1p2…pn),也就是说pj能整除1。但1不应该有素因子的,矛盾!(T1.9, L3.1)

    T3.2:合数n有不超过sqrt(n)的素因子

    证明:n是合数,n可以表示为a*b,a和b都在1到n的开区间里,不妨设a不超过b,那a一定不超过sqrt(n),要不b也会超过sqrt(n),a*b也就会超过n了,矛盾!既然a不超过sqrt(n),L3.1又告诉我们a应该有素因子,这素因子肯定不超过a,T1.8又告诉我们a的这个素因子也是n的素因子,所以n有了一个不超过a的素因子,而a也不超过sqrt(n) (T1.8, L3.1)

    pi(x):不超过x的素数个数

    T3.3:a和b互素,则{a*n+b}里面有无穷多的素数

    证明:略

    T3.4 素数定理:x趋向于无穷时,pi(x)趋向于x/log(x)(或说两者同阶)

    C3.4.1:第n个素数与n*log(n)同阶 (T3.4)

    T3.5:可以找到任意多个连续的合数

    证明:构造(n+1)!+2, (n+1)!+3, …, (n+1)!+(n+1),一共n个数,2能整除第1个数,3能整除第2个数,… ,(n+1)能整除第n个数(由T1.9),所以这n个数都是合数 (T1.9)

    T3.6:若(a, b)=d,则(a/d, b/d)=1,换而言之,a/d和b/d互素

    证明:假设a/d和b/d还有大于1的公因子n,那么a/d=pn, b/d=qn,那么a=p*(d*n), b=q*(d*n),那么a和b的最大公因子就不是d了,就是d*n了,矛盾!

    C3.6.1:a/b一定能表示为p/q的形式,p、q互素

    证明:取p=a/(a, b),q=b/(a,b)就是满足要求的p和q了 (T3.6)

    T3.7:(a+cb, b)=(a, b)

    证明:利用T1.9,证明a+cb与b的公因子都是a与b的公因子,a与b的公因子也都是a+cb与b的公因子。因为b能用a+cb和b线性组合出来,而a+cb也能用a和b线性组合出来,所以这两组数的公因子都是一样的,那最大公因子也是一样的。(T1.9)

    线性组合:ma+nb

    T3.8:a和b的最大公因数就是a和b的最小的正的线性组合

    证明:首先因为a和b不全为0,故a和b一定有正的线性组合,又由WOP,a和b有最小的正的线性组合d=ma+nb。用除法算法(T1.10)用d除a,商q余r,r非负且小于d,那么r=a-dq=a-(ma+nb)*q=(1-qm)*a-qnb,那么r也是a和b的线性组合,而d已经是a和b的最小线性组合了,r还小于d,那么r只能是0,那么d就能整除a了,同理就有d能整除b了,所以d确实是a和b的公因数,只需再证明d是a和b的最大公因数,可以证明a和b的所有公因数都整除b:因为如果一个数能整除a和b,那么它就能整除ma+nb(T1.9),也就是d,所以a和b的所有公因数都能整除d,也就都不会大于d了,所以d就是a和b的最大公因数了。(WOP, T1.9, T1.10)

    C3.8.1:a和b的最大公因数能表示为a和b的线性组合 (T3.8)

    C3.8.2:a和b如果能线性组合得到1,则a和b互素;如果a和b互素,那么a和b一定能线性组合得到1

    证明:a和b如果能线性组合得到1,那1一定是最小的正的线性组合了,不能更小,所以1就是最大公因数了;如果a和b互素,那(a,b)=1,那最小的正的线性组合就是1了,那1一定能通过线性组合得到。(T3.8)

    T3.9:a和b的线性组合构成的集合就是a和b的最大公因数的倍数构成的集合

    证明:首先证明a和b的线性组合都是(a, b)的若干倍:因为d能整除a,d能整除b,所以d能整除a和b的所有线性组合(T1.9),所以a和b的线性组合都是d的倍数;接下来证明(a, b)的若干倍都是a和b的线性组合:因为(a,b)可以表示为ma+nb(T3.8),所以(a,b)的若干倍可以表示为(km)*a+(kn)*b,这一定是a和b的线性组合(T1.9, T3.8)

    T3.10:d是a和b的最大公因数的充要条件是:d能整除a,d能整除b,且所有既能整除a又能整除b的数都能整除d

    证明:首先证明必要性:如果d是a和b的最大公因数,那么由最大公因数的定义可知d能整除a且d能整除b,而且d能表示为m*a+n*b,所以所有既能整除a又能整除b的数都能整除d。接下来证明充分性:如果d能整除a且d能整除b,那么d一定是a和b的公因子。因为a和b的公因子都能整除d,所以a和b的所有公因子都不超过d,所以d就是a和b的最大公因子(T1.9, T3.8)

    (a1, a2, …, an)是这n个数的最大公因子

    L3.2:(a1, a2, …, an-1, an) = (a1, a2, …, an-2, (an-1, an))

    证明:a1, a2, …, an-1, an这n个数的公因子一定是an-1和an的公因子,也就一定能整除(an-1, an),同时也肯定能整除a1, a2, …, an-2,所以等号左边这n个数的公因子一定能分别整除等号右边这n-1个数;反之,能整除等号右边这n-1个数的数,一定能整除前n-2个数,且能整除最后一个(an-1, an),所以也一定能整除an-1,能整除an,也就是能整除等号左边这n个数。既然能整除等号左边的n个数就一定能整除等号右边这n-1个数,反之亦然,那等号左边的n个数的公因子与等号右边的n-1个数的公因子构成的集合完全相同,那最大公因子也一定是同一个数。

    若(a1, a2, …, an)=1,则称a1, a2, …, an互素;若(ai, aj)=1,对于所有i和j不相等,则称a1, a2, …, an两两互素

    T3.11 欧几里得算法(辗转相除法):取a不小于b,a做被除数r0,b做除数r1,得到一个商和一个余数,拿除数做被除数r1,拿余数做除数r2,往复进行以至余数为0,则最后一个不是0的余数就是(a, b)

    证明:利用除法算法用r0除以r1,用r1除以r2,用r2除以r3……,因为每次的余数都要做下一次的除数,而下一次的余数必须小于除数,所以每一次的余数都要小于前一次,是严格地小于,故终有余数为0的时候。再利用L3.3,第一次的被除数和除数的最大公因数,就是第二次的被除数和除数的最大公因数,也是第三次的被除数和除数的最大公因数,…,也是最后一次的被除数和除数的最大公因数,而最后一次除法得到的余数为0,所以最后一次的除数就是这个最大公因数,而倒数第二次的除法得到的余数就是最后一次除法得到的除数,所以倒数第二次除法的余数就是这个最大公因数 (L3.3)

    L3.3:如果e能表示为dq+r的形式,那e和d的最大公因数就是d和r的最大公因数

    证明:利用T3.7,因为(a+cb, b) = (a, b),那么dq+r与d的最大公因数就是r与d的最大公因数(T3.7)

    T3.12:用欧几里得算法求斐波那契数列连续两项的最大公因数正好需要做n次除法

    证明:利用斐波那契数列的定义,fn+2 = fn+1 * 1 + fn,fn+1 = fn * 1 + fn-1,往复进行,倒数第二次f4 = f3 * 1 + f2,最后一次f3=f2 * 2 + 0,总共n次除法

    T3.13 拉梅定理:用欧几里得算法求两个数a和b的最大公因数所需除法次数不超过a和b中较小者的位数的5倍

    证明:注意到如果a和b是斐波那契数列的连续两项的话,这是对于欧几里得算法最差的情况,在最差情况下,如果欧几里得算法涉及了n次除法,a和b中的较小者b也要不小于fn+1。可以用数学归纳法证明一个引理:对于所有n>2,fn+1 > alpha^(n-1)(n=3时成立,n=4时成立,且若不超过n+1时成立,则n+2时有fn+2 = fn+1 + fn > alpha^(n-1) + alpha(n-2) = alpha^n*(2/(1+sqrt(5)) + 2/(3+sqrt(5))) = alpha^n*2*(4+2*sqrt(5))/(8+4*sqrt(5))=alpha^n,利用第二数学归纳法可证)。接下来只要看5*log10b与n的大小关系:因为b不小于fn+1,fn+1又大于alpha^(n-1),所以log10b就大于(n-1)*log10(alpha),又因为log10(alpha)是大于1/5的,所以(n-1)*log10(alpha)就又大于(n-1)/5,从而得出log10b大于(n-1)/5,也就是说, n-1要小于5*log10b,n也不会超过5*log10b,这样就把除法次数n控制在了5倍的b的位数以内了。简单地说,先将b控制在斐波那契数列的第n+1项以上,再将斐波那契数列的第n+1项控制在alpha的n-1次方以上,再将alpha的n-1次方控制在(5次根号下10)的n-1次方以上,最终就发现b要在(5次根号10)的n-1次方以上,而且是严格大于的,所以两侧取以10为底的对数,发现b的位数可以严格大于(n-1)/5,也就是说n-1要严格小于5倍的(b的位数),也就把除法次数n控制在了b的位数的5倍以内了。(T1.6)

    C3.13.1:用欧几里得算法求a和b的最大公因数需要O(log^3(n))的时间

    证明:拉梅定理告诉我们欧几里得算法需要O(log(n))次除法操作,而每次除法操作需要O(log^2(n))的位运算(注:回忆一下4位除法器是如何实现的),故总计需要O(log^3(n))的时间。(T3.13)

    T3.14:a和b的最大公因数可以表示为a和b的这样一个线性组合:sn*a+tn*b,其中sn和tn是如下递归定义的:

    s0 = 1, s1 = 0, sj=sj-2 – qj-1 * sj-1;t0 = 0, t1 = 1, tj = tj-2 – qj-1 * tj-1(即s数列前两项是1和0,t数列前两项是0和1,递归定义都是第n项为前两项减去前一项乘上第n-1个商qn-1)

    证明:只要证明一个更强的结论:rj = sj * a + tj * b 对于j从0到n都成立,那么j取n时,(a, b)就是rn,就有(a, b) = rn = sn * a + tn * b,用第二数学归纳法证明这个结论:j = 0时成立(r0 = a),j = 1时成立(r1 = b),如果j不超过k-1时都成立,那么首先利用欧几里得算法把rk写成rk-2 – rk-1 * qk-1(原本是rk-2 = rk-1 * qk-1 + rk,移项一下就好),因为j不超过k-1时该结论成立,于是可以把rk-2写成(sk-2 * a + tk-2 * b),把rk-1写成(sk-1 * a + tk-1 * b),于是rk就可以写成(sk-2 – qk-1 * sk-1) * a + (tk-2 – qk-1 * tk-1) * b,而sk-2 – qk-1 * sk-1就是sk,tk-2 – qk-1 * tk-1就是tk(根据sk和tk的递归定义),所以rk就可以表示成sk * a + tk * b了,于是用第二数学归纳法就有rj = sj * a + tj * b对于任意j成立,于是j取n时,(a, b) = rn = sn * a + tn * b。简单地说,先用第二数学归纳法证明了一个更有通用性的结论rj = sj * a + tj * b,其中注意利用欧几里得算法中的rk和rk-2、rk-1、qk-1的递推式、以及利用sj和tj的递归定义式,然后再把j=n代入就好了。

    T3.15 算术基本定理:一个大于1的正整数可以唯一地表示为一系列素数的乘积,其中这些质数按照非降序排列

    证明:用反证法,假设真的有这样的数不能表示为一系列素数的乘积,其中必有最小的一个n (WOP),这最小的一个n不能是素数,否则它本身就是素数的乘积了。于是n是个合数,于是n可以写成a*b,a和b都小于n,既然n是最小的不能表示为素数的乘积的数,那a和b都能表示为素数的乘积,那n=a*b也一定能表示为这两个乘积的乘积,也还是素数的乘积。这样就解决了存在性的问题,下面证明唯一性:假如这个n有两种素因数分解,将两种素因数分解写在一个等号的两边,把相同的素数约去,剩下的不同的记为pi1 * pi2 * … * piu = qi1 * qi2 * … * qiv。pi1肯定能整除pi1 * pi2 * … * piu,于是pi1也应该能整除qi1 * qi2 * … * qiv,可pi1不能整除qi1到qiv中的任何一个,因为qi1到qiv都是质数,而且哪个都和pi1不相等(如果有相等的早就该被约去了),这样就和L3.5矛盾了。(WOP, L3.5)

    L3.4:如果a和b互素,a能整除b*c,那么a就能整除c

    证明:因为a和b互素,所以a和b有一个线性组合ax+by=1 (C3.8.2),两边同乘c,于是acx+bcy=c,于是x*a+y*(bc)=c,因为a能整除a自身,a也能整除b*c,所以a能整除x*a+y*(bc) (T1.9),也就是a能整除c了。(T1.9, C3.8.2)

    L3.5:如果素数p能整除a1a2…an的乘积,那么p一定能整除a1到an中的某一个ai

    证明:用数学归纳法:n=1时,p能整除a1,则p能整除a1,显然成立。如果n=k时成立,考虑k+1个ai中的前k个a1, a2, …, ak,因为p是素数,p与a1a2…ak的乘积的最大公因数不是1就是p,如果是1,则p和a1…ak互素,但p能整除a1…ak+1,利用L3.4可知p能整除ak+1;如果是p,那就说明p能整除a1…ak,就退化为n=k的情况了,这样p一定能整除a1, a2, …, ak中的某一个。(T1.5, L3.4)

    a和b的最大公因数就是对于a和b的所有素因数,次数取a和b的素因数分解中次数较低的,再乘在一起
    最小公倍数:a和b的最小公倍数是最小的能同时被a和b整除的数

    a和b的最小公倍数就是对于a和b的所有素因数,次数取a和b的素因数分解中次数较高的,再乘在一起

    L3.6:x和y中的较大者,加上x和y中的较小者,就是x+y、

    证明:分x>=y和x<y两类讨论即可

    T3.16:[a, b] = ab / (a, b)

    证明:把a写成p1^a1 * p2^a2 * … * pn^an,把b写成p1^b1 * p2^b2 * … * pn^bn,那么[a, b] = p1^max(a1, b1) * p2^max(a2, b2) * … * pn^max(an, bn),(a, b) = p1^min(a1, b1) * p2^min(a2, b2) * … * pn^min(an, bn),利用L3.6可知,[a, b] * (a, b) = p1^(max(a1, b1) + min(a1, b1)) * p2^(max(a2, b2) + min(a2, b2)) * … * pn^(max(an, bn) + min(an, bn)),也就是p1^(a1+b1) * p2^(a2+b2) * … * pn^(an+bn),也就是a*b

    L3.7:m和n互素,如果d能整除m*n,那么d一定能唯一地分解为d1*d2,其中d1能整除m,d2能整除n。反之,如果d1能整除m,d2能整除n,那么d=d1*d2也一定能整除m*n

    证明:把m分解为p1^m1 * p2^m2 * … * ps^ms,把n分解为q1^n1 * q2^n2 * … * qt^nt,因为d能整除m*n,所以d一定能分解为p1到ps到q1到qt的若干次方,这“若干”一定不会比m或n中对应的系数大,所以把d的素因数分解中pi的若干次项提取出来,乘在一起就是d1,把d的素因数分解中的qi的若干次项提取出来,乘在一起就是d2,于是就构造出了d1和d2。接下来再证明d1和d2是唯一的:因为d的素因数分解必须要分成两份,pi^mi能且只能被分入d1里面,qi^ni能且只能被分入d2里面,所以分法是唯一的。证明“反之”可直接用m=d1*p, n=d2*q,则mn=(d1*d2)*(p*q)=d*(p*q),所以d能整除m*n。如果要用算数基本定理证明,因为d1中的每一个素因子的次数都不超过m中对应的次数,d2中每一个素因子的次数都不超过n中对应的次数,那把d1和d2乘在一起,把m和n也乘在一起,因为m和n是互素的,所以乘完之后只是把两个素因数分解“连接”在一起,每个素因数的次数都没有改变,原先次数小的现在次数仍然小,所以d1*d2仍然能整除m*n

    T3.17:4*n+3型的素数有无穷多个

    证明:假设只有有限多的4n+3型的素数,记为p0, p1, …, pr,其中p0=3。接下来从p1乘到pr,乘上4,再加上3,也就是Q=4*p1*p2*…*pr+3,Q的素因数分解里面肯定有4n+3型的素数,否则所有素因数都是4n+1型的,乘在一起也是4n+1型的 (L3.8),而Q的表达式Q=4*(…)+3已经说明它是4n+3型的了。既然4n+3型的素数只有有限多个,那这个4n+3型的素数是p0, p1, …, pr中的哪一个呢?是p0吗?如果是的话,p0=3能整除Q,p0=3还能整除3,于是p0=3能整除p1*p2*…*pr (T1.9),而p1到pr都是素数,里面没有3,3是不可能整除p1*…*pr的,矛盾!如果不是p0,那就是p1到pr中的某一个,那这一个pi能整除Q,这一个pi能整除p1*p2*…*pr(因为pi就是p1到pr中的某一个),于是pi能整除3,而pi一定比3大,矛盾!于是原假设就不成立。(T1.9, L3.8)

    L3.8:两个4n+1型的数乘在一起还是4n+1型的

    证明:(4r+1)*(4s+1)=16rs+4(r+s)+1=4(4rs+r+s)+1

    T3.18:最高次项系数为1的关于x的整系数n次多项式的根要么是整数,要么是无理数

    证明:假设这个多项式的根可以是一个a/b的形式,a和b互素,而且b不是1或-1,那把a/b代入原多项式,得到(a/b)^n + cn-1*(a/b)^(n-1) + … + c1*(a/b) + c0 = 0,两边同乘b^n,再移项,等号左侧只留a^n,其余项移到等号右边,发现a^n=b*(-cn-1*a^(n-1) – … – c1*a*b^(n-2) – c0*b^(n-1)),这说明b能整除a^n。如果b不是1或-1,那b有素因子p,那p能整除a^n (T1.8),p能不能整除a呢?一定能,利用数学归纳法证明一个引理:如果p能整除a^n,而且p是素数,那么p能整除a(因为n=2时p能整除a^2必然能推出p能整除a,否则p就与a^2中的一个a互素,于是p就整除a^2中的另一个a (L3.4),由此归纳,如果n=k时成立,那如果p能整除a^(k+1)=a^k * a,假设p不能整除a,那p就能整除a^k,因为n=k时原命题成立,p就能整除a了,矛盾!所以p如果能整除a^(k+1),也一定有p能整除k)若以p能整除a,p又能整除b,这和a和b互素矛盾了。于是b只能取1或-1,这个多项式的有理数根a/b就一定会退化为一个整数a。(T1.5, T1.8, L3.4)

    T3.19:(关于黎曼zeta函数,略)

    L3.9:一个正的奇数n可以分解为两个正整数a和b的乘积a*b,也可以分解为两个整数s和t的平方差s^2-t^2,这两类分解是一一对应的。

    证明:s=(a+b)/2, t=(a-b)/2;a=s-t, b=s+t,这两个线性映射都是一一映射

    T3.20:费马数Fn=2^(2^n)+1的所有素因子都是2^(n+2)*k+1的形式

    证明:略

    L3.10:第k个费马数Fn=2^(2^n)+1可以表示为F0*F1*…*Fn-1 + 2

    证明:用数学归纳法:n=1时,F1=2^(2^1)+1=5=2^(2^0)+1+2=F0+2,原命题成立。如果n=k时成立,则n=k+1时Fk+1=2^(2^(k+1))+1=2^(2^k) * 2^(2^k) + 1 = (Fk – 1)^2 + 1 = (F0*F1*…*Fk-1 + 1) * (Fk – 1) + 1 = F0*F1*…*Fk + (Fk – F0*F1*…*Fk-1 – 1 + 1) = F0*F1*…*Fk + 2,所以n=k+1时也成立。  (T1.5)

    T3.21:任意两个不同的费马数互素

    证明:不妨设这两个费马数为Fm和Fn,m < n,利用L3.10,可把较大的Fn表示为F0*F1*…*Fm*…*Fn-1 + 2。假设有一个d能同时整除Fm和Fn,那么d能整除Fm和(F0*F1*…*Fm*…*Fn-1 + 2),那么d能整除2 (T1.9),那么d不是1就是2。但因为费马数是奇数,d不可能是2,所以d只能是1,也就是说能同时整除Fm和Fn的只有1,也就是Fm和Fn互素。(T1.9)

    T3.22:(关于费马数的几何应用,略)

    T3.23:考虑整系数方程ax+by=c,如果(a, b)能整除c,那就有无穷多个解,而且如果有一个特解x0, y0,则通解可以表示为x=x0+(b/(a,b))*n,y=y0-(a/(a,b))*n(也就是ax和by分别加减一个[a, b]);如果(a, b)不能整除c,那就无解

    证明:将(a, b)记为d,如果原方程有解,因为c是a和b的线性组合,所以d能整除c;如果d不能整除c,那方程就一定无解。接下来证明另一类情况:如果d能整除c,因为d是a和b的最大公因数,所以d可以表示为a和b的一个线性组合as+bt。因为d能整除c,所以c可以表示为e*d=e*(as+bt)=a*(es)+b*(et),那么x0=es和y0=et就是一组解,所以原方程有解。接下来只需证明如果有一组解,就有无穷多组解。考虑x=x0+(b/d)*n,y=y0-(a/d)*n,只需证明这样的x和y都是原方程的解,而且原方程的解都是这个形式。将这个x和y代入原方程,得到ax0+ab/d*n+by0-ba/d*n=c,即ax0+by0=c,这是成立的,说明这样的x和y确实是原方程的解。再证明ax+by=c的所有解都是这个形式:因为ax+by=c,ax0+by0=c,两式相减得到a(x-x0)=b(y0-y),等号两边同除以d,得到a/d*(x-x0)=b/d*(y0-y),由T3.6可知(a/d)和(b/d)互素,又因为(x-x0)倍的(a/d)就是(b/d)*(y0-y),于是a/d能整除(b/d)*(y0-y)。又由L3.4可知a/d就一定能整除y0-y,于是可以将y0-y表示为n*(a/d),于是y=y0-n*(a/d),于是x-x0=b/a(y0-y)=b/a*n*(a/d)=(b/d)*n,于是x=x0+n*(b/d),于是原方程的通解就是这个形式。

    T3.24:a1x1+a2x2+…+anxn=c有解当且仅当d=(a1, a2, …, an)能整除c,而且如果有解,则有无穷多组解

    证明:如果有解,因为d能整除a1,d能整除a2,…,d能整除an,利用T1.9(的推广),d就能整除a1到an的一个线性组合c;反之,如果d不能整除c,原方程就无解。接下来要证明如果d能整除c,原方程就有解,而且有无穷多组解:n=2的情况在T3.23中已证明,如果n=k时原命题成立,考虑一个k+1元方程a1x1 + a2x2 + … + akxk + ak+1xk+1 = c,因为akxk + ak+1xk+1就是ak和ak+1的线性组合,可以等价替换为y*(ak, ak+1),可以取到的值的集合是不变的(T3.9)。这样如果(a1, a2, …, ak, ak+1)能整除c,那么(a1, a2, …, ak-1, (ak, ak+1))能整除c (L3.2),那么(a1, a2, …, ak-1, y)能整除c,那么由归纳假设,k元方程a1x1 + a2x2 + … + ak-1xk-1 + (ak, ak+1)y = c有解,且有无穷多组解,那么k+1元方程a1x1 + a2x2 + … + akxk + ak+1xk+1 = c也有解,也有无穷多组解,因为这两个方程的解集之间有一一映射,xk, xk+1取一个值, y就有唯一的值与之对应,反之亦然(T3.9)

     

    第四章

    a同余于b模m,等价于m整除a-b

    T4.1:a同余于b模m,等价于存在整数k使得a=b+km

    证明:一方面,因为a同余于b模m,所以m整除a-b,所以a-b=km,所以a=b+km;另一方面,因为a=b+km,所以a-b=k*m,所以m整除a-b,所以a同余于b模m

    T4.2:同余关系具有自反性、对称性、传递性(我与我同余,我与你同余则你与我同余,我与你同余你与他同余则我与他同余)

    证明:自反性:因为m|0,所以m|(a-a),所以a同余于a模m;对称性:若a同余于b模m,则m整除a-b,则km=a-b,则(-k)m=b-a,则m整除b-a,则b同余于a模m;传递性:若a同余于b模m, b同余于c模m,则m整除a-b且m整除b-c,则a-b=pm, b-c=qm,则a-c=a-b+b-c=(p+q)*m,则m整除a-c,则a同余于c模m

    T4.3:a同余于b模m,等价于a除以m的余数等于b除以m的余数。

    证明:先证明充分性:a=q1m+r,b=q2m+r,则a-b=(q1-q2)*m,则m整除a-b,则a同余于b模m;再证明必要性:因为a同余于b模m,所以m整除a-b,考虑a=q1m+r1,b=q2m+r2,因为a-b=(q1-q2)m+r1-r2,且m能整除a-b,且r1、r2大于等于0小于m,r1-r2也在-m到m的开区间内,所以必有r1-r2=0,即r1=r2

    模m的完全剩余系:任意一个整数和这个集合里的某一个数(有且仅有一个)模m同余

    T4.4:如果a同余于b模m,那么a和b (1)同加一个c (2)同减一个c (3)同乘一个c 之后仍然模m同余

    证明:因为a同余于b模m,所以m整除a-b,所以m整除(a+c)-(b+c)=a-b,所以m整除(a-c)-(b-c)=a-b,又因为ac-bc=c(a-b),m整除a-b,a-b整除c(a-b),由T1.8得m整除c(a-b),故m整除ac-bc,故a和b (1)同加一个c (2)同减一个c (3)同乘一个c 之后仍然模m同余。

    T4.5:如果ac和bc模m同余,设c和m的最大公因数为d,那么a和b就模m/d同余

    证明:因为ac和bc模m同余,所以m整除ac-bc=(a-b)c,所以(a-b)c=km,两侧同除以d得到(a-b)(c/d)=k(m/d),从而有m/d整除(a-b)(c/d),又因为m/d与c/d互素 (T3.6),由L3.4得到m/d整除a-b,即a和b模m/d同余。

    C4.5.1:如果ac同余于bc模m,c和m互素,那么a同余于b模m

    T4.6 T4.4的更一般形式:如果a同余于b模m,那么a和b (1)各自加一个模m同余的数c和d (2)各自减一个模m同余的数c和d (3)各自乘一个模m同余的数c和d 之后仍然模m同余

    证明:因为a同余于b模m,c同余于d模m,所以a-b=pm,c-d=qm,所以(a+c)-(b+d)=(a-b)+(c-d)=(p+q)m,所以(a-c)-(b-d)=(a-b)-(c-d)=(p-q)m,所以ac-bd=(b+pm)*(d+qm)-bd=(bq+dp+pqm)m,即(a+c)-(b+d),(a-c)-(b-d),ac-bd都能被m整除,即a和b (1)各自加一个模m同余的数c和d (2)各自减一个模m同余的数c和d (3)各自乘一个模m同余的数c和d 之后仍然模m同余

    L4.1:m个两两模m不同余的数构成一个模m的完全剩余系

    证明:假设并不能构成模m的完全剩余系,那么就能找到一个a使得a和这m个数中的任意一个模m不同余,那么a除以m的余数r也和这m个数中的任意一个模m不同余,这样这m个数除以m的余数只有m-1种可能性了(否则由T4.3总有一个数会和a模m同余),这样这m个数总有两个模m同余,与这两个数两两模m不同余又矛盾了。

    T4.7:一个模m的完全剩余系的每个元素都乘上一个与m互素的正整数a,再加上一个任意的整数b,得到的集合还是一个模m的完全剩余系。

    证明:首先证明得到的新集合中任取不同的i和j,a*ri+b和a*rj+b模m不同余:假如有a*ri+b和a*rj+b模m同余,那么由T4.4,有a*ri和a*rj模m同余。因为a和m互素,由C4.5.1有ri和rj模m同余,矛盾!那么由L4.1,这个新集合中的m个数两两模m不同余,这个新集合也构成一个模m的完全剩余系。

    T4.8:如果a同余于b模m,k是正整数,那么a^k也同余于b^k模m

    证明:只需证明m整除a^k-b^k:因为a^k-b^k=(a-b)*(a^(k-1) + a^(k-2)*b + … + a * b^(k-2) + b^(k-1)),m整除a-b,a-b整除a^k -b^k,由T1.8有m整除a^k-b^k。(也可递归使用T4.6(3)依次得到a^2与b^2模m同余, a^3与b^3模m同余,…, a^k与b^k模m同余)

    T4.9:如果a和b模m1同余,模m2同余,…, 模mn同余,那么a和b就模所有mi的最小公倍数[m1, m2, …, mn]同余

    证明:引理:若mi整除a-b对于i=1, 2, …, n成立,则[m1, m2, …, mn]整除a-b(先证明如果a整除c,b整除c,就有[a, b]整除c:由算数基本定理,a的各个素因数的次数不超过其在c中对应的次数,b的各个素因数的次数也不超过其在c中对应的次数,而[a, b]的各个素因数的次数就是a和b的对应的次数取较大者,这仍然不会超过c中对应的次数,故[a, b]仍然整除c。再用数学归纳法推广,如果n=k时成立,那么a1, a2, …, ak分别整除c可以推出[a1, a2, …, ak]整除c,那么如果a1, a2, …, ak, ak+1分别整除c,必有a1, a2, …, ak分别整除c,既得到[a1, a2, …, ak]整除c,而且还有ak+1整除c,从而得到[[a1, a2, …, ak], ak+1]整除c。由于k个数的最大值再和第k+1个数取较大者等同于直接取这k+1个数的最大值,故[[a1, a2, …, ak], ak+1] = [a1, a2, …, ak, ak+1],即得[a1, a2, …, ak, ak+1]整除c,即n=k+1时原命题也成立

    C4.9.1:如果a和b模m1同余,模m2同余,…, 模mn同余,而且m1, m2, …, mn两两互素,那么a和b就模所有mi的乘积m1*m2*…*mn同余

    证明:只需证明引理:如果m1, m2, …, mn两两互素,那么[m1, m2, …, mn] = m1 * m2 * … * mn,证明如下:n=2时[m1, m2] = m1 * m2 / (m1, m2) = m1 * m2 / 1 = m1 * m2, 原命题成立。假如n=k时原命题成立,那么[m1, m2, …, mk, mk+1] = [[m1, m2, …, mk], mk+1] = [m1*m2*…*mk, mk+1],因为mk+1与m1, m2, …, mk都互素,(假如存在d为mk+1与m1*m2*…*mk的公因子,由L3.1,d必有素因子p,又由L3.5,p必整除m1到mk中的某一个mi,又因为p整除d,d整除mk+1,故p整除mk+1,这样就有mi和mk+1有大于1的公因子p,与mi和mk+1互素矛盾了。)所以mk+1与m1*m2*…*mk也互素,所以[m1*m2*…*mk, mk+1] = m1*m2*…*mk*mk+1。

    T4.10:关于快速幂模运算的复杂度分析,略

    T4.11:a和m的最大公因数是d,如果d不能整除b,那么ax同余于b模m就无解;如果d能整除b,那么ax同余于b模m恰有d个模m不同余的解

    证明:ax同余于b模m等价于ax-my=b,x是ax同余于b模m的解,等价于能找到一个y使得ax-my=b。由T3.23,如果d=(a, m)不能整除b,这个方程就无解;如果d=(a, m)能整除d,这个方程就有无穷多组解,通解为x=x0+(m/d)*n,y=y0+(a/d)*n。接下来需要判断有多少个模m不同余的解,首先需要确定两个x模m同余的条件,设x1=x0+(m/d)*n1, x2=x0+(m/d)*n2,如果x1和x2模m同余,那么m/d*n1和m/d*n2模m同余(T4.4(2))。因为m/d和m的最大公因数就是m/d(因为m=d*(m/d)),所以n1和n2模m/(m/d) = d同余,所以如果x1和x2模m同余,则对应的n1和n2模d同余,而模d同余一共有d种可能,所以x模m恰有d种可能。

    C4.11.1:如果a和m互素,那么ax同余于b模m恰有1个解

    如果a和m互素,则ax同余于1模m的唯一的整数解称为a模m的逆

    T4.12:p是素数,a模p的逆仍然是a当且仅当a同余于1模p或者a同余于-1模p

    证明:先证明必要性:如果a模p的逆仍然是a,说明a*a同余于1模p,说明p整除a^2 – 1。因为a^2 – 1 = (a-1) * (a+1),由L3.5,p整除a-1或者p整除a+1,所以a同余于1模p或a同余于-1模p。再证明充分性:如果a同余于1模p或者a同余于-1模p,则有a^2同余于1*1=1模p或者a^2同余于(-1) * (-1) = 1模p,也就是说a^2一定是同余于1模p的,也就是说a模p的逆仍然是a。

    T4.13 中国剩余定理:m1, m2, …, mr两两互素,则有x同余于a1模m1,x同余于a2模m2, …,x同余于ar模mr这个线性同余方程组模M=m1*m2*…*mr有唯一解

    证明:先设Mk = M / mk,则有(Mk, mk) = 1,由T4.11可知Mk * y同余于1模mk有唯一解,这个解yk就是Mk模mk的逆,也就是Mk*yk同余于1模mk。令x=a1M1y1 + a2M2y2 + … + arMryr,则x就是上述方程组的解,证明如下:因为x的表达式中除了第k项都能被mk整除,所以把同余于0模mk的k-1项都去掉,剩下的akMkyk同余于x模mk (T4.6)。又因为Mkyk同余于1模mk,故ak同余于x模mk (T4.6),这就证明了x确实为上述方程组的解。接下来证明上述方程组的所有解模M同余:考虑上述方程组的两个解x0和x1,对于任意一个k,x0和x1和ak都模mk同余,于是mk就整除x0-x1,由T4.9,由于m1, m2, …, mk都整除x0-x1,且m0, m1, …, mk两两互素,得到M整除x0-x1,于是x0和x1模M同余,于是所有的解x都模M同余。

    中国剩余定理求解“物不知数”问题:

    问:“有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?”

    答:“三人同行七十希,五树梅花廿一支,七子团圆正半月,除百零五使得知。”

    这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。意思是:将除以3得到的余数乘以70,将除以5得到的余数乘以21,将除以7得到的余数乘以15,全部加起来后除以105,得到的余数就是答案。

    70=5*7*2,2是35模3的逆

    21=3*7*1,1是21模5的逆

    15=3*5*1,1是15模7的逆

    L4.2:2^a – 1除以2^b – 1的余数是2^r – 1,r是a除以b的余数

    证明:由T1.10,a=bq+r,故2^a – 1 = 2^(bq+r) – 1 = (2^b – 1) * (2^(b*(q-1) + r) + 2^(b*(q-2) + r) + … + 2^(b + r) + 2^r) + (2^r – 1),因为0<=r<b,故2^r – 1就是2^a – 1除以2^b – 1的余数

    L4.3:2^a – 1和2^b – 1的最大公因数是2^(a, b) – 1

    证明:以a=r0, b=r1开始执行欧几里得算法,记录下r2, r3, …, rn-1,其中rn-1就是(a, b)。再以2^a=r0,2^b=r1开始执行欧几里得算法,则r’2 = 2^r2,r’3 = 2^r3,…,r’n-1 = 2^(rn-1),最后一个非零的余数r’n-1就是2^(rn-1),也就是2^(a, b),所以说(2^a, 2^b)就是2^(a, b)

    T4.14:2^a – 1和2^b – 1互素当且仅当a和b互素

    证明:由L4.3可得

     
  • jinzihao pm9:37 on 2016年4月18日 链接地址 | 回复  

    连续地访问内存TLB是否命中在运行时间上会有很大差别,例如:

    #include <stdio.h>
    
    int main() {
      int *a = new int[4096 * 4096];
      for (int i = 0; i < 4096; ++i) {
        for (int j = 0; j < 4096; ++j) {
          // a[(j << 12) + (i << 0)] = 0; // 0.4004s
          // a[(j << 11) + (i << 1)] = 0; // 0.3810s
          // a[(j << 10) + (i << 2)] = 0; // 0.3809s
          // a[(j << 9) + (i << 3)] = 0; // 0.3548s
          // a[(j << 8) + (i << 4)] = 0; // 0.3503s
          // a[(j << 7) + (i << 5)] = 0; // 0.2727s
          // a[(j << 6) + (i << 6)] = 0; // 0.2691s
          // a[(j << 5) + (i << 7)] = 0; // 0.1434s
          // a[(j << 4) + (i << 8)] = 0; // 0.1195s
          // a[(j << 3) + (i << 9)] = 0; // 0.0714s
          // a[(j << 2) + (i << 10)] = 0; // 0.0651s
          // a[(j << 1) + (i << 11)] = 0; // 0.0681s
           a[(j << 0) + (i << 12)] = 0; // 0.0825s
        }
      } 
      return 0;
    }
    

    上述程序中循环体内有13个版本的代码,每次编译只启用其中1行,注释掉其余的12行,测量运行时间。

    每次访问内存地址的增量从16KB逐次折半,到最后每次增量为4byte,内存访问操作由第一个版本100%的TLB miss,到第4个版本TLB miss开始降至50%(假设页大小为4KB),此后TLB miss比例逐次减半,直到最后几乎100%的TLB hit(1023/1024),此过程中运行时间不断下降。

    问题:最后一个版本的运行时间明显上升,且多次实验结果均无改变,不知该如何解释?

     

     
c
写新的
j
下一篇文章/下一个回复
k
前一篇文章/以前的回复
r
回复
e
编辑
o
显示/隐藏 回复
t
回到顶部
l
go to login
h
show/hide help
shift + esc
取消