應用密碼學習題答案4

應用密碼學習題答案4應用密碼學習題答案4應用密碼學習題答案4應用密碼學習題答案4編制僅供參考審核批準生效日期地址：電話：傳真:郵編:《應用密碼學》習題和思考題答案第4章密碼學數(shù)學引論4－1編寫一個程序找出100~200間的素數(shù)。略4－2計算下列數(shù)值：7503mod81、(－7503)mod81、81mod7503、(－81)mod7503。解：7503mod81＝51(－7503)mod81＝3081mod7503＝81(－81)mod7503＝74224－3證明：（1）（2）證明：（1）設，，則（為某一整數(shù)），（為某一整數(shù)）。于是有：于是有：（2）設，，，則（為某一整數(shù)），（為某一整數(shù)），（為某一整數(shù)）。于是有：于是有：4－4編寫一個程序，用擴展的歐幾里德算法求gcd(4655,12075)和550－1mod1723。略。4－5求25的所有本原元。解：25的所有本原元是：2,3,8,12,13,17,22,23。4－6求Z5中各非零元素的乘法逆元。解：Z5中各非零元素分別為1、2、3、4，它們的乘法逆元（mod5）分別是：1、3、2、4。4－7求。解：4－8利用中國剩余定理求解：解：M=3×5×7=105;M/3=35;M/5=21;M/7=15。 35b1＝1(mod3) 21b2＝1(mod5)15b3＝1(mod7) 因此有：b1=2;b2=1;b3=1。則：x＝2×2×35+1×1×21+1×1×15＝176(mod105)＝714－9解釋：群、交換群、有限群、有限群的階、循環(huán)群、生成元、域、有限域、不可約多項式。答：群由一個非空集合組成，在集合中定義了一個二元運算符“·”，滿足：封閉性：對任意的，有：；結合律：對任何的，有：；單位元：存在一個元素(稱為單位元)，對任意元素，有：；逆元：對任意，存在一個元素(稱為逆元)，使得：。如果一個群滿足交換律，則稱其為交換群。如果一個群的元素是有限的，則稱該群為有限群。有限群的階就是群中元素的個數(shù)。如果群中每一個元素都是某一個元素的冪(為整數(shù))，則稱該群是循環(huán)群。在循環(huán)群中，認為元素生成了群，或是群的生成元。域是由一個非空集合組成，在集合中定義了兩個二元運算符：“+”(加法)和“·”(乘法)，并滿足：(1)關于加法“+”是一個交換群；其單位元為“0”，的逆元為。(2)關于乘法“·”是一個交換群；其單位元為“1”，的逆元為。(3)(分配律)對任何的，有：；(4)(無零因子)對任意的，如果，則或。如果域只包含有限個元素，則稱其為有限域。不可約多項式是指不能再分解為兩個次數(shù)低于該多項式最高次的多項之積的多項式。4－10基于最優(yōu)化正規(guī)基表示的域，計算和分別等于多少解：按照最優(yōu)化正規(guī)基表示的乘法計算方法，有：。4－11什么是計算復雜性它在密碼學中有什么意義答：計算復雜性理論提供了一種分析不同密碼技術和算法的計算復雜性的方法，它對密