CF1310F Bad Cryptography

在现代密码学中，许多内容都与解决若干问题的算法复杂度有关。其中一个问题是离散对数问题。其表述如下： 我们固定一个[有限域](https://en.wikipedia.org/wiki/Finite_field)及其两个元素 $a$ 和 $b$。需要找到一个 $x$，使得 $a^x = b$，或者判断不存在这样的 $x$。对于足够大的域规模，现代人类很可能无法解决离散对数问题。例如，对于模素数剩余域，1024 或 2048 位的素数被认为是安全的。然而，使用如此大的数字进行计算会给执行密码操作的服务器带来显著负担。因此，实际中常常使用更复杂的域结构，这样可以使用更小的域并对运算进行优化，因为目前尚无利用这些域结构的快速算法。 开发者 Nikolai 不信任通用的方法，因此他想发明自己的方法。最近，他读到了一种非常奇特的域——[nimbers](https://en.wikipedia.org/wiki/Nimber)，并认为它非常适合这个目的。 nimber 域定义在从 $0$ 到 $2^{2^k} - 1$ 的整数集合上，其中 $k$ 是某个正整数。加法使用按位异或（$\oplus$）操作。乘法（$\odot$）的一种定义方式如下： - $0 \odot a = a \odot 0 = 0$ - $1 \odot a = a \odot 1 = a$ - $a \odot b = b \odot a$ - $a \odot (b \odot c)= (a \odot b) \odot c$ - $a \odot (b \oplus c) = (a \odot b) \oplus (a \odot c)$ - 如果 $a = 2^{2^n}$，其中 $n > 0$，且 $b < a$，则 $a \odot b = a \cdot b$。 - 如果 $a = 2^{2^n}$，其中 $n > 0$，则 $a \odot a = \frac{3}{2}\cdot a$。 例如： - $4 \odot 4 = 6$ - $8 \odot 8 = 4 \odot 2 \odot 4 \odot 2 = 4 \odot 4 \odot 2 \odot 2 = 6 \odot 3 = (4 \oplus 2) \odot 3 = (4 \odot 3) \oplus (2 \odot (2 \oplus 1)) = (4 \odot 3) \oplus (2 \odot 2) \oplus (2 \odot 1) = 12 \oplus 3 \oplus 2 = 13$ - $32 \odot 64 = (16 \odot 2) \odot (16 \odot 4) = (16 \odot 16) \odot (2 \odot 4) = 24 \odot 8 = (16 \oplus 8) \odot 8 = (16 \odot 8) \oplus (8 \odot 8) = 128 \oplus 13 = 141$ - $5 \odot 6 = (4 \oplus 1) \odot (4 \oplus 2) = (4\odot 4) \oplus (4 \odot 2) \oplus (4 \odot 1) \oplus (1 \odot 2) = 6 \oplus 8 \oplus 4 \oplus 2 = 8$ 形式化地，这个算法可以用如下伪代码描述：  可以证明，这些运算确实构成了一个域。此外，这些运算在博弈论中也有意义，但这与本题关系不大。通过适当的缓存和分组操作，可以较快地计算乘积，这对于提升密码算法的速度很重要。更正式的定义及其他性质可参考维基百科的[相关条目](https://en.wikipedia.org/wiki/Nimber)。本题所列出的性质应足以解决问题。 对于这种乘法，幂运算的定义与通常相同，形式上 $a^{\odot k} = \underbrace{a \odot a \odot \cdots \odot a}_{k~\texttt{次}}$。 你需要分析所提出方案的强度。对于给定的数对 $a$ 和 $b$，你需要找到一个 $x$，使得 $a^{\odot x} = b$，或者判断不存在这样的 $x$。

第一行包含一个整数 $t$（$1 \le t \le 100$），表示需要求解离散对数的数对数量。 接下来的 $t$ 行，每行包含一对整数 $a$ 和 $b$（$1 \le a, b < 2^{64}$）。

对于每一对数，输出一个整数 $x$（$0 \le x < 2^{64}$），使得 $a^{\odot x} = b$，如果不存在这样的 $x$，则输出 $-1$。可以证明，如果存在这样的 $x$，则一定在给定范围内。如果有多个满足条件的 $x$，输出其中任意一个即可。

由 ChatGPT 4.1 翻译