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

bruceteen

用程序遍历求解：

1. #include <stdio.h>
   
2. #include <limits.h>
   
3. 
   
4. int main()
   
5. {
   
6.     unsigned MinX = UINT_MAX;
   
7.     for( unsigned n=0; ; ++n )
   
8.     {
   
9.         unsigned X = (n*0x53+0x11)^0xa9;
   
10.         if( X<MinX && (X^0x56)%0x53==0x1f )
    
11.             MinX = X;
    
12. 
    
13.         if( MinX!=UINT_MAX && (X|0xFF)>(MinX|0xFF) ) // 已经找到符合条件的数，且其后因为X的高位必大于MinX的高位，，所以不需要再找了
    
14.             break;
    
15.     }
    
16.     printf( "MinX = %x\n", MinX );
    
17. 
    
18.     return 0;
    
19. }

复制代码

hbmhalley

回复 11# bruceteen


    ............. 所以那个式子是找规律找出来的..?

bruceteen

hbmhalley 发表于 2013-02-06 13:17
回复 11# bruceteen
............. 所以那个式子是找规律找出来的..?

嘿嘿，是的

folklore

** vb,

such as fomula, it is easy to see that n <0x53 (0x53 =lcm(0x53,0x53)), and it not cost so much .
(it there are no answer below n<0x53, then the question is no solution.

noword2k

这个问题是在跟踪某游戏字库时碰到的。

这个字库使用这样的结构：
字符的信息放在一个结构数组内（A），经过观察发现，该数组的个数补足到了最小的质数（total_size）。

然后用一个同样大小的，存放32位整数的数组(B)，来得到字符所在的结构数组(数组A)的位置。

如想得到某字符(unichr)在数组A的位置，可用     
（B[ unichr % total_size ] ^ unichr ）％ total_size
来得到。

示例(用了一个比较小的字库，仅有一些数字和符号)：
数组A（仅列出字符内码）：
0 0034
1 0035
2 0037
3 0036
4 0038
5 0039
6 002f
7 0030
8 0031
9 0032
a 0033
b 002f
c ffff

数组B：
0 00000034
1 00000034
2 dca345ea
3 00000035
4 0000003c
5 0000003c
6 00000000
7 00000000
8 00000029
9 00000037
a 00000039
b 0000003b
c 00000039

这里的数组大小是13 (0xD)
如想得到utf16字符u"3"（0x33），则
(B[ 0x33%0xD] ^ 0x33) % 0xD = 0xA。

字符0x36和0xFFFF 与 0xD取余数后，都是指向了B[2] ==> 0xdca345ea
(0xdca345ea ^ 0x36) % 0xd = 3
(0xdca345ea ^ 0xFFFF) % 0xd = 0xC

问题是生成这个数组B时，是如何解决冲突的，这个神奇的0xdca345ea是怎么算出来的呢？

sacry

回复 15# noword2k

早这么说啊，我就不花脑细胞去想了。。。
之前想到的分别求高低位，是基于你那个例子里a9/56巧合的。
#A XOR B = FF，  (X XOR A) ± (X XOR B)刚好能分别消掉高位和低位。

现在这个就完全没头绪了，
扫上两眼觉得和给我几对公私钥让我推导出RSA算法一个难度的 ╮(╯_╰)╭

一介村夫

设X = a * 0x100 + b，0 <= b <= 0xff。
(X^0xa9)%0x53 = 0x11
(X^0x56)%0x53 = 0x1f
即：
( ( a * 0x100 + b ) ^ 0xa9 ) % 0x53 = 0x11
( ( a * 0x100 + b ) ^ 0x56 ) % 0x53 = 0x1f
因为：0xa9 + 0x56 = 0xff，所以两式相加并简化得：
( 2 * a * 0x100 + 0xff ) % 0x53 = 0x30
因为：0xff % 0x53 = 0x6，所以：( 2 * a * 0x7 ) % 0x53 = 0x2A，0x2A / 0x7 = 6，所以 a 的最小值为 3。3 * 0x100 % 0x53 = 0x15。
考虑：( 0x15 + b ^ 0xa9 ) % 0x53 = 0x11，即：( b ^ 0xa9 ) % 0x53 = 0x4f，得到：( b ^ 0xa9 ) = 0x4f 或 0xa2 或 0xf5，即：b = 0xe7 或 0xb 或 0x5c。
结论：X 最小值为 0x30b。

sacry

回复 17# 一介村夫

( ( a * 0x100 + b ) ^ 0xa9 ) % 0x53 = 0x11
( ( a * 0x100 + b ) ^ 0x56 ) % 0x53 = 0x1f
因为：0xa9 + 0x56 = 0xff，所以两式相加并简化得：
( 2 * a * 0x100 + 0xff ) % 0x53 = 0x30

这一步怎么化简的...

其实更想问第一句

设X = a * 0x100 + b，0 <= b <= 0xff。

怎么想到的？
感觉这是破题关键啊，顺着推下去很清爽。

我是不问三七二十一先模运算相加相减，
然后XOR转成十进制的Σ表示死算...

一介村夫

sacry 发表于 2013-02-06 16:00
回复 17# 一介村夫

( b ^ 0xa9 ) + ( b ^0x56 ) = 0xff。

yuanchengjun

/* only 0x00 ~ 0xFF, why not a loop ? */
for (int X=0; X <=0xFF; ++X)
    ...