• 2007-08-25

    [读书笔记]《离散数学及其应用Discrete Mathematics and its applications (Fifth Edition)》笔记-Chapter2 - [阅读]

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/sgzxy-logs/7916332.html

    Discrete Mathematics and its applications

    Written by (U.S.)Kenneth H. Rosen

     笔记-Chapter2

     

          在花了N多时间看书后继续花N多时间整理一份笔记,是因为我觉得这样可以把书中个人认为最精华的部分提取出来,同时通过自己的理解、表达以及讨论来加深印象。没办法,这是笨人笨办法。

        Chapter1讲逻辑演算的基本概念,乏善可陈,内容比华工自个出的中文课本上少了很多,像范式等概念提都没提。至于连接词及谓词演算方面的深入讨论都放到了后面布尔代数的章节,故此章省略。

        Chapter2则是数论入门内容,这些东西在中国课本上是完全看不到影子的,而它们却实际上是离散数学的根本。因为重要的离散数学算法常常建立在数论研究上。数论是数学基础的基础,也是数学难上的最难(最有名的数学难题大多来自数论,包括哥德巴赫猜想与费马大定理),学深下去恐怕我是没这个能力的,只能尽力把基础的和应用性大的掌握。

    Chapter 2 The Fundamentals: Algorithms, the Integers, and Matrices

    证明1.“素数个数无限”(The Infinitude of Primes)的证明

    证:假设只存在有限素数p[1],p[2]…p[n],令Q=p[1]p[2]…p[n]+1

    则对于任意p[j]属于{p[1],p[2]…p[n]}p[j]Q1,即pjQ的因数。根据算术基本定理(The Fundamental Theorem of Arithemetic),任意大于1的正数均可唯一地写成素数或者素数乘积的形式。而Q在假设中非素数,且无法表示成素数(假设中有限)乘积,故矛盾。得证。

     

     定理1.The Prime Number Theorem)内容:

    p表示不大于自然数x的素数的个数,则当x趋于无穷,p/(x/ln(x))的极限为1 

     

     算法1.(密码学常用)快速计算 b^n mod m 的方法(b,n,m均是大数):

    首先有公式:ab mod m= a(b mod m) mod m(易证)

    然后将n转为高精度二进制表达,假设有n=a[k-1]…a[1]a[0]binary

    利用公式循环迭代计算b mod mb^2 mod m,……,b^(2^(k-1) ) mod m,循环过程中根据n的二进制表达选择性地将这些结果累乘求模(原理同公式),循环部伪代码如下:

    for (i=0; i<k; )

    {    if (a[i]=1)

         x=(x*power) % m;         //powerb幂的迭代计算值,x为求结果的累乘求模值

         power=(power*power) % m;

    }

     

     定理2.中国剩余定理(The Chinese Remainder Theorem):

    m[1],m[2]…m[n]为两两互质的正整数,m=m[1]m[2]…m[n],则方程组

    xa[1] (mod m[1])

    xa[2] (mod m[2])

    xa[n] (mod m[n])ii

    [0,m)中仅有一解。

    1xa mod m)表示x mod m=a mod m

    2:利用此定理,可用一余数n元组来表示在[0,m)的一个数,从而可以进行较大数的快速运算(P188)。感觉此法只在某些特殊的情况下才显得有用,粗略分析来看不会比传统高精度计算更有优势,而且范围有局限、不支持小数,故仅作为参考。

     

     定理3.费马小定理(Fermat’s Little Theorem):

    如果p是一素数,a是一不能被p整除的整数,则

    a^(p-1) 1 (mod p)  或者  a^p a (mod p)

     

     原理1.RSA公共密钥算法方法及原理:

    加密:设M为明文,C为暗文。

    选定两个大素数pq,取n=p*q,取e(p-1)(q-1)互质,记作gcd( e, (p-1)(q-1) )=1

    gcd=Greatest Common Devisor最大公因数)

    则有C= M^e mod n (利用算法1

    解密:公钥d满足d*e1 ( mod (p-1)(q-1)),也即d*e=1+k(p-1)(q-1),可得

            M=C^d mod n

     

    原理[1]-d的作用原理:

    C^d (M^e)^d    //易证,将数写成b*q+r的形式即可)

         =M^(d*e) =M^(1+k(p-q)(q-1))

    由费马小原理得:M^(p-1) 1 (mod p)M^(q-1) 1 (mod q)

    C^dM (mod p) C^dM (mod q)     //将幂中的+1提出来即可

    利用中国剩余定理,则有C^d M (mod p*q) M (mod n)

     

      原理[2]-d的存在原理:若gcd(e, (p-1)(q-1))=1成立,则必有满足条件的d存在

              证:记m=(p-1)(q-1)

                  因为gcd(e,m)=1,则存在整数st,满足s*e+t*m=1。(*

                  即有s*e1 (mod m),则d=s存在。

                 

                  现在证(*):设集合S={ u| u=s*e+t*m }cS中最小的正整数

                            假设c不能整除e,则有e=c*q+r0<r<c

    r = e-c*q = e-(s*e+t*m)*q = (1-s*q)*e + (-t*q)*m S

    c是最小矛盾。故c能整除a (记为 c|a

    同理证c|m。又gcde,m=1,则c=1。得证。

                 

    原理[3]-d的计算原理:在此举例说明,e=3 m=17

    利用Euclidean算法(辗转相除)计算gcde,m=1,有过程如下

    17=5*3+2

    3=1*2+1

    则可得1 = 3-1*2 = 3-1*(17-5*3) = -1*17 + 6*3

    d=6

       (不过这样表达的话转换成算法要用到树来表达,感觉用递归有更优的方式,暂时没去探讨,等需要用到RSA的时候再研究不迟。)

     

    注:此章中的一些素数检验方法的原理(如Miller’s test)可以留待以后需要用时消化。

    分享到:

    评论

  • for (i=0; i<k; )

    { if (a[i]=1)

    x=(x*power) % m; //power为b幂的迭代计算值,x为求结果的累乘求模值

    power=(power*power) % m;

    }

    程序里面的x为什么没有赋初值啊
    回复小陈说:
    当初漏了,现在看一下应该赋x=1吧
    2010-10-27 15:08:49
  • 你博客文字偏小,黑白背景文字有少许刺眼,不利阅读。
    回复kemin说:
    说得好……不过Blogbus弄出来就是这样,我也懒得改了……
    2008-03-04 21:16:51
  • 检验的方法。。。
    回复FC说:
    哈?
    2007-09-07 09:25:33
  • 这个是我们去年的课本啊……
    回复vczh说:
    不光是去年,今年也一样,这本书真是畅销啊……哈哈……不过是肯定无法满足你的了……嘿嘿
    2007-09-06 23:06:25