Question

离散数学作业（急求一下题目答案）

1．判断一个数a是否为素数的算法，最多、一般情况下、至少要作多少次除法运算？要达到最少的次数应该附加什么？
观察一正整数a是否素数，要用小于a大于1的整数一一来试除吗？不要。
定理9.2.2 若a是大于1的整数，而所有小于或等于 的素数都不能整除a，则a是素数。
令π(x)表示不超过x的素数个数，可以证明

它表明了:尽管素数个数无穷多，但它比起正整数的个数来少得很多。
2.
定理9.5.3 9整除正整数a iff 9整除a的十进制表示各数字的和。
定理9.5.4 (弃九法) 若ab=c，其中a＞0，b＞0，并且a= •10i，b= •10j，c= •10k，则( )( )≡( )(mod 9)。
例9.5.1 求证1997×57≠113828�
3．欧几里德算法思想及时间复杂度度问题？
本质上是用辗转相除把求两个正整数最大公因数的问题化为求两个较小整数的最大公因数，直到两个整数中的一个为0。
现将定理9.3.2欧几里德算法以伪码形式给出如下：
Euclid(a，b：整数)
if b=0 then return a
while b>0
{ r←a(mod b)
a←b
b←r
}
return a
算法中过程的每一步都是a用b代替，而b用a(mod b)代替。只要b>0，这个过程就重复下去，当b=0时算法终止，此时a的值也就是这一过程的非零余数，即为a和b的最大公因数。
在欧几里德算法中基本操作是除法，为研究欧几里德算法的时间复杂性，需要求出算法中所使用的除法次数，下面拉梅定理给出解答。
定理10.2.1 设a和b是满足a≥b的正整数，则欧几里德算法求得(a，b)而使用除法的次数小于或等于b的十进制位数的5倍。
4．两个n位的二进制整数a和b的乘法算法
可按下面等式进行计算：
ab=a =
首先注意在bi=1时abi=a，而bi=0时abi=0。每当用2乘一项时，结果都是把该项的二进制展开向左移一位并在尾部加上一个0，因此，可把abi的二进制展开向左移i位，再在尾部加上i个0来计算(abi)2i。最后，将n个整数(abi)2i，i=0，1，…，n-1，相加得到ab。
两个正整数a和b二进制展开的乘法算法：
mul(a，b)
for i← 0 to n-1
if bi=1 then ci← a左移i位
else ci← 0 //c0c1…cn-1是部分积
p ← 0
for i← 0 to n-1
p ← p+ci //p是ab的值
读者不难得出：移位个数是O(n2)，位加法个数是O(n2)，这是因为，所有n个整数(abi)2i，i=0，1，…，n-1，需要0+1+2+…+n-1次移位，故移位数是O(n2)，而将(abi)2i从i=0到i = n+1加起来，需要做一次n位整数、(n+1)位整数、…以及2n位整数的加法，这些加法都需要O(n)次位相加，因此完成所有n个数加法需要O(n2)次位加法。

5．最常用的产生伪随机数的方法是线性同余法。U(0,1)
它是递归定义的：
xn+1=(axn+c)(mod m) （1）
Ui=xn/m （2）
其中，m称为模数，a为乘数，c为增量，x0为种数，且2≤a<m，0≤c<m，及0≤x0<m。
有时要求伪随机数为小数，为此使用xn/m。
分析此算法的特点：
6．RSA公钥系统
RSA公钥系统是由MIT的三名研究人员：瑞弗斯特(Ron Rivest)、沙米尔(Adi Sharmir)和阿德莱门(Len Adleman)于1978年联合提出的，它的安全性是基于大整数因数分解困难问题，至今没有有效的算法。
RSA加密算法的过程：
① 选取两素数p和q(保密)
② 计算n = pq(公开)，φ(n)=(p-1)(q-1)(保密)
③ 选取加密公钥e，满足(e，φ(n))=1
④ 计算解密私钥d，满足de≡1(modφ(n))
使用RSA加密之前，应将明文数字化，并取长度小于log n位的数字作为明文块。
加密算法 c=E(m)=me(mod n)
解密算法 D(c)=cd(mod n)

Answer 1

有点乱