85的7次方mod143怎么求?希望有达人帮我,如果可以帮我讲讲RSA加密算法,

Question

85的7次方mod143怎么求?
希望有达人帮我,如果可以帮我讲讲RSA加密算法,

Answer 1

设x=85^7
易知143=11*13
设x=a(mod11),x=b(mod13).求出a和b,然后根据中国剩余定理就可以了.
先求出a：
由于85=11*7+8
所以85^7=8^7=2^21(mod11),而根据欧拉定理知道:2^10=1(mod11)
所以85^7=2^21=2(mod11),即a=2
下面求b：
由于85=13*6+7
所以85^7=7^7(mod13)
计算7^7=823543=6(mod13),这边我实在想不出什么好方法算7^7(mod13)
即b=6
所以得到一个同余方程组：
x=2(mod11),x=6(mod13)
13*6=1(mod11),11*6=1(mod13)
所以x=2*13*6+6*11*6=123(mod143)
RSA:
原理：
选择两个随机大素数 p,q
计算模数 N=p.q
选择一个随机加密密钥匙 e :e