16762)=gcd(16762,7378)=gcd(7378,2006)=gcd(2006,1360)=gcd(1360,646)=gcd(646,68)=gcd(68,34)=gcd(34,0)=34求GCD(4655,12075)结果为35欧拉函数φ(n)表示所有小于正整数n且与n互素的正整数的个数。在表中给出了当n=2-13时欧拉函数的值:n2345678910111213φ(n)12242646410412c=0;f=1;fori=kdownto0doc=c*2f=(f*f)modnifbi=1thenc=c+1f=(f*a)modnreturnf注:整数b表示为二进制bkbk-1bk-2….b0下面是abmodn的快速指数算法。请注意,这里的变量c不是必需的,引入它只是为了便于解释算法,c的终值既是指数。f的终值即为算法的结果。表计算abmodn的快速模幂算法,其中,a=7,b=560=1000110000,n=561i9876543210bi1000110000c1248173570140280560f749157526160241298166671运用上述算法,计算5596mod1234.给出计算中的步骤。解答:i9876543210bi1001010100c124511234693186372f525625937595569453591591013RSA算法中密钥的生成和加密解密过程。(1)密钥生成过程:①选两个保密的大素数p和q。②计算n=p×q,φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。③选一整数e,满足1<e<φ(n),且gcd(φ(n),e)=1。④计算d,满足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元,因e与φ(n)互素,由模运算可知,它的乘法逆元一定存在。⑤以{e,n}为公开钥,{d,n}为秘密钥。(2)加密
全文预览
