主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 I: 窃听者

问题 I: 窃听者

时间限制: 2 Sec  内存限制: 128 MB
提交: 224  解决: 76
[提交][状态][讨论版]

题目描述


众所周知,西电密码学于国内当执牛耳。密码学中有个非常著名的密钥协商算法叫做Diffie-Hellman算法
算法描述如下:
1,有两个全局公开的参数,一个素数q和一个整数a,a是q的一个原根.
2,假设用户A和B希望交换一个密钥,用户A选择一个作为私有密钥的随机数XA(XA<q),并计算公开密钥YA=a^XA mod q。A对XA的值保密存放而使YA能被B公开获得。类似地,用户B选择一个私有的随机数XB<q,并计算公开密钥YB=a^XB mod q。B对XB的值保密存放而使YB能被A公开获得.
3,用户A产生共享秘密密钥的计算方式是K = (YB)^XA mod q.同样,用户B产生共享秘密密钥的计算是K = (YA)^XB mod q.这两个计算产生相同的结果: K = (YB)^XA mod q = (a^XB mod q)^XA mod q = (a^XB)^XA mod q (根据取模运算规则得到) = a^(XBXA) mod q = (a^XA)^XB mod q = (a^XA mod q)^XB mod q = (YA)^XB mod q 因此相当于双方已经交换了一个相同的秘密密钥.

现在youqh和xingxing在通信,为方便计算,他们选择的素数q = 2147483647,a = 3
youqh生成了自己的随机数XA,并计算公开密钥YA, xingxing生成了自己的随机数XB,并计算公开密钥YB
正准备通信时,已知YA,YB这两个数被数学爱好者cyt窃听到,并由此计算出了公共密钥K,请问K是多少

输入

多组数据,不超过20组

窃听得到的数YA,YB

输出

K,如果无解则输出No Solution

样例输入

955181137 449121451
5 6

样例输出

2098167979
No Solution

提示

[提交][状态][讨论版]