数学问题紧急求助！！！！(新的问题在15楼)

noword2k

已知

1. 
   
2. (X^0xa9)%0x53 = 0x11
   
3. (X^0x56)%0x53 = 0x1f
   

复制代码

怎么快速求出X的最小值（^为异或, %为取余数）。

hbmhalley

1. 首先观察 #xa9 #x56
   
2. #xa9 = #b10101001
   
3. #x56 = #b01010110
   
4. 即 #xa9 ^ #x56 = #xff
   
5. 
   
6. 由异或运算性质，原式可写为
   
7. (X + c7 + c5 + c3 + c0) % #x53 = #x11
   
8. (X + c6 + c4 + c2 + c1) % #x53 = #x1f
   
9. 其中 ci = 2^i * (-1或1)
   
10. 原因是：
    
11. 若 X 第 i 位为 0，则 X ^ |ci| == X + |ci| 否则
    
12. 若 X 第 i 位为 1，则 X ^ |ci| == X - |ci|
    
13. 
    
14. 下式减上式得
    
15. 
    
16. (-c7 +c6 -c5 + c4 -c3 +c2 +c1 -c0) % #x53 = #x0e
    
17. 
    
18. 由于 (-c7 +c6 -c5 + c4 -c3 +c2 +c1 -c0) 必为奇数且属于 (-2^8,+2^8)
    
19. 可得只有三种可能，(#x0e + #x53) (#x0e - #x53) (#x0e - 3*#x53)
    
20. 即 #x61 -#x45 -#xeb
    
21. 而通过 (-c7+c6...-c0)，可以唯一确定 (c7..c0) 从而唯一确定 X 后 8 位
    
22. 
    
23. 以 #x61为例：
    
24. #x61 = #b01100001
    
25. 现在需要将此 01 二进制数转换为 (-1/1)“二进制”数
    
26. 由 2^k - 2^(k-1) - (2^k-2) - ... - 2^0 = 1，可得如下构造方法：
    
27. 将每段 000...001 改为 1 -1 -1 ... -1
    
28. 即
    
29. 0    1    1    0    0    0    0    1 =
    
30. 1    -1   1    1    -1   -1   -1   1        ，分别对应
    
31. -c7  c6   -c5  c4   -c3  c2   c1   -c0
    
32. 
    
33. 可得 (c7..c0) = (-1,-1,-1,1,1,-1,-1,-1) ，即 X 后 8 位为 #b11100111
    
34. ps: 由归纳法可知对应(-1/1)串的唯一性，其证明过程与构造过程类似
    
35. 同理，-#x45 -#xeb 分别对应可能的 X 后 8 位为 #b00001011 与 #b01011100
    
36. 即，三个可能的后 8 位为：#xe7 #x0b #x5c
    
37. 
    
38. 已知后 8 位，下求前若干位
    
39. 设 X = Y * 2^8 + Z，其中 Z = #xe7/#x0b/#x5c
    
40. 
    
41. X ^ #xa9 = X + C = Y *　2^8 + Z + C
    
42. 其中 C 为 Z 对应的 (c7,0,c5,0,c3,0,0,c0) ，例如
    
43. Z=#xe7 时 C = (-1, 0,  -1, 0,  1,  0,  0,  -1) =-#x99
    
44. Z=#x0b 时 C = (1,  0,  1,  0,  -1, 0,  0,  -1) = #x97
    
45. Z=#x5c 时 C = (1,  0,  1,  0,  -1, 0,  0,  1 ) = #x99
    
46. 
    
47.      (X ^ #xa9) % #x53 = #x11
    
48. (Y*2^8 + Z + C) % #x53 = #x11
    
49.         (Y*2^8) % #x53 = (#x11 - Z - C) % #x53
    
50.           Y = Y % #x53 = (#x11 - Z - C) * (1/2^8) % #x53
    
51. 
    
52. 其中 1/2^8 = (2^8) ^ (#x53 - 2) % #x53 = #x0c
    
53. 
    
54. 将三个对应 X = Y*2^8 + Z 算出后取最小值即可
    
55. 
    
56. 懒得算了 无责任无脑练手代码一份 未验证 正确率不超过 2.71828%
    
57. (let*
    
58.   ((Z '(#x73, #x0b, #x5c))
    
59.    (C '(#x-99, #x97, #x99))
    
60.    (Y (let ((y (lambda (z c)
    
61.                  (let ((t (remainder
    
62.                             (* (- #x11 z c) #x0c)
    
63.                             #x53)))
    
64.                       (if (< t 0) (+ t #x53) t)))))
    
65.            (map y Z C))
    
66.    (X (let ((x (lambda (y z)
    
67.                  (+ (* y #x100) z))))
    
68.            (map x Y Z)))
    
69.   (min X))

复制代码

folklore

@hbmhalley
so complex?

i just think it will be
(n *0x53 + 0x11) ^0xa9, n=0,1,2, ...

bruceteen

folklore 发表于 2013-02-06 07:36
(n *0x53 + 0x11) ^0xa9, n=0,1,2, ...

你的意思是
由 (X^0xa9)%0x53 = 0x11 推导出 X = (n*0x53+0x11)^0xa9
然后遍历出一切X，再代入到 X = (y*0x53+0x1f)^0x56 中验证
？

bruceteen

X = (0x300 + n*0x5300) + ( 0xe6 或 0x0b 或 0x5c ), n = 0, 1, 2, 3, ……
最小的X是 0x30b

hbmhalley

回复 3# folklore


    没错
    但 lz 不是说快速么
    这样不好估计 n 有多大
    但利用 #xa9 和 #x56 的特点可以把计算量控制在有限个

bruceteen

hbmhalley 发表于 2013-02-06 12:04
回复 3# folklore
这样不好估计 n 有多大

可以的，因为 (n *0x53 + 0x11) ^0xa9 中 ^0xa9 只影响到最后一个字节，所以对于 m?? 和 n??，如果m大于n，则m??^0xa9一样大于n??^0xa9

hbmhalley

回复 7# bruceteen


    不懂 ...

bruceteen 发表于 2013-02-06 08:42
你的意思是
由 (X^0xa9)%0x53 = 0x11 推导出 X = (n*0x53+0x11)^0xa9
然后遍历出一切X，再代入到 X = (y*0x53+0x1f)^0x56 中验证
？

    这个 n 该怎么找?

    & 你的后1byte是怎么找的?

sacry

同问

想到的方法和2楼差不多，
利用余运算，先减了求低8位（有限几个），再加了求高8位，
看5楼答案的结构也是这样的啊，

但是想不通3楼怎么到5楼的...
3楼看起来像完全穷举。

hbmhalley

回复 9# sacry


    有一个问题
    0xe6 ^ 0xa9  ==  0x0b ^ 0xa9 == 0x5c ^ 0xa9 (mod 0x53)
    0xe6 ^ 0x56  ==  0x0b ^ 0x56 == 0x5c ^ 0x56 (mod 0x53)
    这是偶然吗? 如果不是，那就是我想错了 ..