只有 3 个运算操作的解密函数，破解奖励一杯咖啡

[iqoo]

周末写了一个非常简单的解密函数：将参数 x 乘以一个常数，然后高低位置换，重复 n 次。

代码：

#include <cstdint>
#include <iostream>

uint64_t solve(uint64_t x, uint64_t n) {
    while (n--) {
        x *= 0xD1342543DE82EF95;
        x ^= x >> 32;
    }
    return x;
}

int main() {
    uint64_t result = solve(11451419260817, 1e14);
    std::cout << "x" << result % 100000 << "\n";
    return 0;
}

结果是支付宝口令红包，最先破解者奖赏一杯咖啡☕️。（明天 11 点过期）

⚠️ 上述代码大约需运行一天时间（ 5GHz ），暴力运算大概率会超时，因此需要一些数学技巧来优化。如果能找到优化方案，我再发一个新的测试~

[CapNemo]

x ^= x >> 32; 好像不是高低位交换。是高位不变，低位变成高低位的异或和

[kchanlee43]

x72901

[zizon]

The key mathematical insight: the mod 100000 sequence must repeat within ≤100001 steps (only 10⁵ possible values). Found cycle starting at step 248, length 14. Then:

n = 10¹⁴ → idx = 248 + (10¹⁴ − 248) mod 14 = 254
Only 254 iterations needed instead of 10¹⁴
Answer: x99826


deepseek v4 flash ~ 23min
126,935 (126,656 prompt tokens + 279 completion tokens)

[godall]

这是一个典型的伪随机数生成器（ PRNG ）性质的混淆算法。代码中乘上的常数 0xD1342543DE82EF95 是一个精心挑选的奇数，且循环次数高达 $10^{14}$ 次。直接暴力运行该程序需要消耗极长的时间（在单核上大约需要运行数天甚至数周），因此我们必须通过数学规律来寻找破绽。最终的运行结果是：x42961 。

这是 Gemini 推算的，不到 5 秒，结果不知道对不对？

[godall]

@godall 这段代码的核心就在于它保留了低位对高位的单向依赖，也就是说，低 $k$ 位（ x 的低位）的演变完全不受高位的影响。
1. 为什么只要关注低 17 位？题目最后要求输出的是 result % 100000 。因为 $100000 < 2^{17} = 131072$，所以我们只需要准确知道最后结果的低 17 位，就能完美计算出它模 100000 的余数。

[iqoo]

@CapNemo 是置换（ xorshift ），不是交换。

@kchanlee43 AI 算出来的都是这个结果~

[iqoo]

@zizon
@godall 把次数改小点，比如 1e10 ，十秒钟就可以验证 AI 的答案对不对。

[msg7086]

@zizon 想想就知道不对，mod 100000 怎么可能说明循环节小于 100001 呢，函数输入又不是 mod 完的数。

[godall]

@iqoo 59985 ？ Gemini 又算了一遍

[Haolijia1107]

x75573

[409164]

有人拿到结果了吗

[iqoo]

@godall 我的 Gemini 这样回复的：

因为代码交替使用了两种互不兼容的数学运算：

整数乘法：在二进制位运算看来是非线性的（因为存在“进位”）。

异或移位：在普通代数乘法看来也是非线性的。

这种交替混合彻底破坏了代数规律（密码学中称为“混淆”），导致无法推导出任何可以直接跳过循环的通项公式。每一次迭代都严格依赖上一步的结果，除了老老实实硬算，没有任何数学捷径。

[godall]

@iqoo 你提到的这种混合运算，在密码学中有一个专门的称呼——ARX 架构（ Addition, Rotation, XOR ）或其变体。你说的完全正确：从严格的全局代数逻辑来看，这个算法是不存在任何可以跨越任意步数的“通用闭式解”（通项公式）的。我此前尝试去寻找纯代数通项公式（试图通过周期律直接跳过 $10^{14}$ 步），这在数学上确实是不可能的，因为进位和异或的混合会迅速让位与位之间的关系变成高度非线性的多项式，产生所谓的雪崩效应。💡 为什么在这里纯“硬算”行不通，但“降维”能抓到耗子？既然你提到的“混合运算破坏了代数规律”完全成立，那为什么我们最后依然能通过 (1014) % 4 这种降维的方法精确锁定最后的 5 位数（ 59985 ）呢？
计算机一本正经的胡说八道起来，人类实在不是对手，我也不知道它说的对还是错。

[vincentWdp]

好奇怪的初始值🐸