能力值：
![]()
(RANK：1060 )
|
-
-
2 楼
提示：穷举A
|
能力值：
( LV2，RANK：10 )
|
-
-
3 楼
up版主一个。。。。。。。。
|
能力值：
![]()
(RANK：420 )
|
-
-
4 楼
這個 A 有無窮多組解。
|
能力值：
( LV2，RANK：10 )
|
-
-
5 楼
难道此算法只能沦落到用穷举法吗？解还不唯一？
|
能力值：
![]()
(RANK：1060 )
|
-
-
6 楼
取值范围就[0, 0xffff]，怎么可能有无穷多
|
能力值：
![]()
(RANK：420 )
|
-
-
7 楼
我也好奇的想知道，有無其它更好的方法。
|
能力值：
( LV15，RANK：2473 )
|
-
-
8 楼
B是已知数，不限范围是什么概念？
fg换了这么邪恶的头像
|
能力值：
( LV9，RANK：330 )
|
-
-
9 楼
|
能力值：
( LV15，RANK：2473 )
|
-
-
10 楼
楼上慧眼啊，原来就是求解： A * B ≡ Y (mod 0x10001)
|
能力值：
( LV15，RANK：2473 )
|
-
-
11 楼
g个代码测试一下：
DWORD GetGcd(DWORD a,DWORD b)
{
if (a < b)
{
DWORD temp = a;
a = b;
b = temp;
}
DWORD c = a;
DWORD d = b;
DWORD test = 0;
while((test = c % d) > 0)
{
c = d;
d = test;
}
return d;
}
DWORD GetXY(DWORD a,DWORD b,DWORD *xy)
{
BOOL isChange = FALSE;
if (a < b)
{
DWORD temp = a;
a = b;
b = temp;
isChange = TRUE;
}
DWORD k,p0=1,p1=0,q0=0,q1=1,temp;
int n = 0;
DWORD c = a;
DWORD d = b;
DWORD test = 0;
while((test = c%d) > 0)
{
n++;
k = c/d;
if (n==1)
{
p1 = k;
q1 = 1;
}
else
{
temp = p1;
p1 = p1*k+p0;
p0 = temp;
temp = q1;
q1 = q1*k+q0;
q0 = temp;
}
c = d;
d = test;
}
if (n%2 == 1)
{
p1 = 0 - p1;
}
else
{
q1 = 0 - q1;
}
if (isChange)
{
temp = p1;
p1 = q1;
q1 = temp;
}
xy[0] = q1;
xy[1] = p1;
return 0;
}
DWORD GetInv(DWORD a,DWORD m)
{
DWORD xy[2];
if(GetGcd(a,m) == 1)
{
GetXY(a,m,xy);
DWORD temp = xy[0] % m;
if(temp < 0)
{
temp += m;
}
return temp;
}
return -1;
}
int main()
{
DWORD A,B,X,Y,M;
M = 0x10001;
B = 0x6907;
Y = 0xACA4;
X = GetInv(B,M);
A = X * Y % M;
printf("\nA = 0x%04X",A);
_getch();
return 0;
}
|
能力值：
![]()
(RANK：1060 )
|
-
-
12 楼
感谢欧几里得
|
能力值：
( LV2，RANK：10 )
|
-
-
13 楼
多谢了！
搞明白是求A*B≡ Y (mod 0x10001)的逆运算就有思路了。
源程序里有现成求模0x10001的乘法拟元函数，只需利用此模0x10001乘法拟元函数就行了。
假设B*C≡1 (mod 0x10001)，则A≡A*B*C≡Y*C(mod 0x10001)
而求B模0x10001的乘法拟元C的原理正是楼上提到的“欧几里德算法”，顺便附上代码供大家参考。
00E92650 /$ 55 push ebp
00E92651 |. 8BEC mov ebp, esp
00E92653 |. 83EC 1C sub esp, 1C
00E92656 |. 0FB745 08 movzx eax, word ptr [ebp+8]
00E9265A |. 85C0 test eax, eax
00E9265C |. 75 05 jnz short 00E92663
00E9265E |. 66:33C0 xor ax, ax
00E92661 |. EB 7E jmp short 00E926E1
00E92663 |> C745 FC 01000100 mov dword ptr [ebp-4], 10001
00E9266A |. 0FB74D 08 movzx ecx, word ptr [ebp+8]
00E9266E |. 894D E8 mov dword ptr [ebp-18], ecx
00E92671 |. C745 F8 01000000 mov dword ptr [ebp-8], 1
00E92678 |. C745 E4 00000000 mov dword ptr [ebp-1C], 0
00E9267F |> 8B45 FC /mov eax, dword ptr [ebp-4]
00E92682 |. 99 |cdq
00E92683 |. F77D E8 |idiv dword ptr [ebp-18]
00E92686 |. 8955 F0 |mov dword ptr [ebp-10], edx
00E92689 |. 8B45 FC |mov eax, dword ptr [ebp-4]
00E9268C |. 2B45 F0 |sub eax, dword ptr [ebp-10]
00E9268F |. 99 |cdq
00E92690 |. F77D E8 |idiv dword ptr [ebp-18]
00E92693 |. 8945 F4 |mov dword ptr [ebp-C], eax
00E92696 |. 837D F0 00 |cmp dword ptr [ebp-10], 0
00E9269A |. 75 14 |jnz short 00E926B0
00E9269C |. 837D F8 00 |cmp dword ptr [ebp-8], 0
00E926A0 |. 7D 0C |jge short 00E926AE
00E926A2 |. 8B55 F8 |mov edx, dword ptr [ebp-8]
00E926A5 |. 81C2 01000100 |add edx, 10001
00E926AB |. 8955 F8 |mov dword ptr [ebp-8], edx
00E926AE |> EB 27 |jmp short 00E926D7
00E926B0 |> 8B45 E8 |mov eax, dword ptr [ebp-18]
00E926B3 |. 8945 FC |mov dword ptr [ebp-4], eax
00E926B6 |. 8B4D F0 |mov ecx, dword ptr [ebp-10]
00E926B9 |. 894D E8 |mov dword ptr [ebp-18], ecx
00E926BC |. 8B55 F8 |mov edx, dword ptr [ebp-8]
00E926BF |. 8955 EC |mov dword ptr [ebp-14], edx
00E926C2 |. 8B45 F4 |mov eax, dword ptr [ebp-C]
00E926C5 |. 0FAF45 F8 |imul eax, dword ptr [ebp-8]
00E926C9 |. 8B4D E4 |mov ecx, dword ptr [ebp-1C]
00E926CC |. 2BC8 |sub ecx, eax
00E926CE |. 894D F8 |mov dword ptr [ebp-8], ecx
00E926D1 |. 8B55 EC |mov edx, dword ptr [ebp-14]
00E926D4 |. 8955 E4 |mov dword ptr [ebp-1C], edx
00E926D7 |> 837D F0 00 |cmp dword ptr [ebp-10], 0
00E926DB |.^ 75 A2 \jnz short 00E9267F
00E926DD |. 66:8B45 F8 mov ax, word ptr [ebp-8]
00E926E1 |> 8BE5 mov esp, ebp
00E926E3 |. 5D pop ebp
00E926E4 \. C3 retn
|
|
|
|
