[求助]x ^ 6 % 32 == 17 求 x ？-密码应用-看雪-安全社区|安全招聘|kanxue.com

最新回复 (7)
publickey 雪币： 62 活跃值： (27) 能力值： ( LV3，RANK：20 ) 在线值：发帖 4 回帖 101 粉丝 0 关注私信	publickey 2013-9-20 00:46 2 楼 0 了解如下几点即可： 1、x显然是奇数，奇数显然与32互素，所以问题可以转化为模32的剩余类乘法群来解决； 2、(x^6)^3mod32=17 ->x^18mod32=17->x^2mod32=17->x^4mod32=1->4是x的阶; 3、搜索小于32的所有非1奇数m，若m^4mod32=1且x^2mod32!=1，记录下来，设为m1,m2,...mt，最后的解为mi+32k。附上问题的解：7+32k，23+32k，25+32k
hack一生雪币： 306 活跃值： (85) 能力值： ( LV6，RANK：80 ) 在线值：发帖 29 回帖 195 粉丝 0 关注私信	hack一生 1 2013-9-20 10:58 3 楼 0 LS,比较专业，理解貌似比较麻烦点（x+32)^6%32=x^6%32 其他项包含32肯定被整出， (C6 1 ).. x^6(C6 0) 这样理解，貌似容易点。。
aj3423 雪币： 196 活跃值： (96) 能力值： ( LV6，RANK：90 ) 在线值：发帖 82 回帖 271 粉丝 2 关注私信	aj3423 2 2013-9-20 11:21 4 楼 0 多谢高手们 ~
jeffcjh 雪币： 58 活跃值： (28) 能力值： ( LV2，RANK：10 ) 在线值：发帖 2 回帖 267 粉丝 0 关注私信	jeffcjh 2013-9-21 15:15 5 楼 0 我接着2楼的思路来分析一下。 1、用模32的剩余类乘法群来分析应该是比较规范的； 2、但“3、搜索小于32的所有非1奇数m，若m......”这个我觉得有点不符合LZ的“请勿枚举”本意，虽然穷举空间减少了一半； 3、按照2楼的思路进行纯粹的数论推导来求x是可行的： 3.1 (x^6)^2 = 17^2 = 1 (mod 32) i.e. x^12 - 1 = 0 (mod 32) 3.2 由 x^12-1 = (x^4-1) * (x^8+x^4+1) = 0 (mod 32) 推出 x^4 - 1 =0 (mod32) 3.3 由 x^4 - 1 = (x^2 + 1) * (x^2 - 1) = 0 (mod 32)可推出：2整除(x^2 + 1)，16整除(x^2 - 1) 3.4 利用x^2 - 1 = (x+1)*(x-1)=0 (mod 16)可以推导出： 2整除x+1 且 8整除x-1 或者 8整除x+1 且 2整除x-1 从而分别得到： x=9,17,25 或者 x=7,15,23,31 (注意：起点+8) 3.4 经进一步验证得到： x=7,9,23,25 注意：上述推导过程中用到了一个小知识点： a奇时，a+1与a-1有公因子2^1，不可能有2^2以上
lingyu 雪币： 1022 活跃值： (31) 能力值： ( LV4，RANK：50 ) 在线值：发帖 29 回帖 449 粉丝 0 关注私信	lingyu 1 2013-9-21 22:08 6 楼 0 φ(32)= φ(2^5)= 2^4 = 16. x^6 = 17 mod 32 ==> (x^2)^3 = 17 mod 32 因((x^2)^3)^3 = x^18 = x^(18-φ(32)) = x^2 mod 32 即 17^3 = x^2 = 17 mod 32 然后再用Cipolla's algorithm求解二次剩余。 1、若指数(即例子中的6)与φ()互素，即: x^y = z mod n 因x^φ(n) = 1 mod p 令ans*y = 1 mod φ(n) 所以x^ans = x mod n 2、若φ() + 2 = 0 mod 4，计算二次剩余为： 17^((φ(32)+2)/2) = x mod 32
稻草人Z 雪币： 680 活跃值： (68) 能力值： ( LV6，RANK：90 ) 在线值：发帖 6 回帖 138 粉丝 1 关注私信	稻草人Z 2 2013-9-21 22:24 7 楼 0 ls好专业
publickey 雪币： 62 活跃值： (27) 能力值： ( LV3，RANK：20 ) 在线值：发帖 4 回帖 101 粉丝 0 关注私信	publickey 2013-9-21 22:53 8 楼 0 第3步确实可以用更简单的方法求得，不过需要用到有限群的分解方面的知识，对于模数为2^n的情况，还可以有一般化的方法。
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复

最新回复 (7)
publickey 雪币： 62 活跃值： (27) 能力值： ( LV3，RANK：20 ) 在线值：发帖 4 回帖 101 粉丝 0 关注私信	publickey 2013-9-20 00:46 2 楼 0 了解如下几点即可： 1、x显然是奇数，奇数显然与32互素，所以问题可以转化为模32的剩余类乘法群来解决； 2、(x^6)^3mod32=17 ->x^18mod32=17->x^2mod32=17->x^4mod32=1->4是x的阶; 3、搜索小于32的所有非1奇数m，若m^4mod32=1且x^2mod32!=1，记录下来，设为m1,m2,...mt，最后的解为mi+32k。附上问题的解：7+32k，23+32k，25+32k
hack一生雪币： 306 活跃值： (85) 能力值： ( LV6，RANK：80 ) 在线值：发帖 29 回帖 195 粉丝 0 关注私信	hack一生 1 2013-9-20 10:58 3 楼 0 LS,比较专业，理解貌似比较麻烦点（x+32)^6%32=x^6%32 其他项包含32肯定被整出， (C6 1 ).. x^6(C6 0) 这样理解，貌似容易点。。
aj3423 雪币： 196 活跃值： (96) 能力值： ( LV6，RANK：90 ) 在线值：发帖 82 回帖 271 粉丝 2 关注私信	aj3423 2 2013-9-20 11:21 4 楼 0 多谢高手们 ~
jeffcjh 雪币： 58 活跃值： (28) 能力值： ( LV2，RANK：10 ) 在线值：发帖 2 回帖 267 粉丝 0 关注私信	jeffcjh 2013-9-21 15:15 5 楼 0 我接着2楼的思路来分析一下。 1、用模32的剩余类乘法群来分析应该是比较规范的； 2、但“3、搜索小于32的所有非1奇数m，若m......”这个我觉得有点不符合LZ的“请勿枚举”本意，虽然穷举空间减少了一半； 3、按照2楼的思路进行纯粹的数论推导来求x是可行的： 3.1 (x^6)^2 = 17^2 = 1 (mod 32) i.e. x^12 - 1 = 0 (mod 32) 3.2 由 x^12-1 = (x^4-1) * (x^8+x^4+1) = 0 (mod 32) 推出 x^4 - 1 =0 (mod32) 3.3 由 x^4 - 1 = (x^2 + 1) * (x^2 - 1) = 0 (mod 32)可推出：2整除(x^2 + 1)，16整除(x^2 - 1) 3.4 利用x^2 - 1 = (x+1)*(x-1)=0 (mod 16)可以推导出： 2整除x+1 且 8整除x-1 或者 8整除x+1 且 2整除x-1 从而分别得到： x=9,17,25 或者 x=7,15,23,31 (注意：起点+8) 3.4 经进一步验证得到： x=7,9,23,25 注意：上述推导过程中用到了一个小知识点： a奇时，a+1与a-1有公因子2^1，不可能有2^2以上
lingyu 雪币： 1022 活跃值： (31) 能力值： ( LV4，RANK：50 ) 在线值：发帖 29 回帖 449 粉丝 0 关注私信	lingyu 1 2013-9-21 22:08 6 楼 0 φ(32)= φ(2^5)= 2^4 = 16. x^6 = 17 mod 32 ==> (x^2)^3 = 17 mod 32 因((x^2)^3)^3 = x^18 = x^(18-φ(32)) = x^2 mod 32 即 17^3 = x^2 = 17 mod 32 然后再用Cipolla's algorithm求解二次剩余。 1、若指数(即例子中的6)与φ()互素，即: x^y = z mod n 因x^φ(n) = 1 mod p 令ans*y = 1 mod φ(n) 所以x^ans = x mod n 2、若φ() + 2 = 0 mod 4，计算二次剩余为： 17^((φ(32)+2)/2) = x mod 32
稻草人Z 雪币： 680 活跃值： (68) 能力值： ( LV6，RANK：90 ) 在线值：发帖 6 回帖 138 粉丝 1 关注私信	稻草人Z 2 2013-9-21 22:24 7 楼 0 ls好专业
publickey 雪币： 62 活跃值： (27) 能力值： ( LV3，RANK：20 ) 在线值：发帖 4 回帖 101 粉丝 0 关注私信	publickey 2013-9-21 22:53 8 楼 0 第3步确实可以用更简单的方法求得，不过需要用到有限群的分解方面的知识，对于模数为2^n的情况，还可以有一般化的方法。
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复