纠结着我的难题——一个密码的相关算法
大家好，今天被一个密码算法给纠结住了，在这里顺便请教大家：已知：
1. x, c, r为4字节正整数(DWORD类型)，
2. (x*c)%0x100000000 = r (0x100000000为16进制数，且为DWORD的最大数值加1，即0xFFFFFFFF+1)
3. c一般为奇数，且0x100000000%c != 0
4. 现在如果已经知道c和r的值，x值未知
5. 在我现在项目中，c已经是一个固定值0x11FA73B(16进制), 但r的值为任意值，
6. 我的难题：怎样才可以快速求出x的值？
望得到大家的提示！谢谢！
x ≡ r*c-1=0xFFE699F3 * r (mod 232) x ≡ r*c-1=0xFFE699F3 * r (mod 232)
gxqcn 发表于 2010-10-19 16:24 http://bbs.emath.ac.cn/images/common/back.gif
确实太高明了！经过验证了两个，都是正确的。
能否问问：0xFFE699F3 这个数值是怎样求出来的？ 我用 HugeCalc 计算 c 关于 2^32 的模逆，即可得到该常数。
模逆的计算通常可用扩展GCD算法实现，或用本论坛曾讨论过的：快速求大整数关于 2^n 的模逆
页:
[1]