CF1310F.Bad Cryptography

In modern cryptography much is tied to the algorithmic complexity of solving several problems. One of such problems is a discrete logarithm problem. It is formulated as follows:

Let's fix a finite field and two it's elements $a$ and $b$. One need to fun such $x$ that $a^x = b$ or detect there is no such x.

It is most likely that modern mankind cannot solve the problem of discrete logarithm for a sufficiently large field size. For example, for a field of residues modulo prime number, primes of 1024 or 2048 bits are considered to be safe. However, calculations with such large numbers can place a significant load on servers that perform cryptographic operations. For this reason, instead of a simple module residue field, more complex fields are often used. For such field no fast algorithms that use a field structure are known, smaller fields can be used and operations can be properly optimized.

Developer Nikolai does not trust the generally accepted methods, so he wants to invent his own. Recently, he read about a very strange field — nimbers, and thinks it's a great fit for the purpose.

The field of nimbers is defined on a set of integers from 0 to $2^{2^k} - 1$ for some positive integer $k$ . Bitwise exclusive or ($\oplus$) operation is used as addition. One of ways to define multiplication operation ($\odot$) is following properties:

• $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)$
• If $a = 2^{2^n}$ for some integer $n \gt 0$, and $b \lt a$, then $a \odot b = a \cdot b$.
• If $a = 2^{2^n}$ for some integer $n \gt 0$, then $a \odot a = \frac{3}{2}\cdot a$.

For example:

• $ 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$

Formally, this algorithm can be described by following pseudo-code.

multiply(a, b) {   ans = 0   for p1 in bits(a)       // numbers of bits of a equal to one       for p2 in bits(b)   // numbers of bits of b equal to one          ans = ans xor multiply_powers_of_2(1 << p1, 1 << p2)   return ans;}multiply_powers_of_2(a, b) {    if (a == 1 or b == 1) return a * b    n = maximal value, such 2^{2^{n}} <= max(a, b)    power = 2^{2^{n}};    if (a >= power and b >= power) {        return multiply(power * 3 / 2, multiply_powers_of_2(a / power, b / power))    } else if (a >= power) {        return multiply_powers_of_2(a / power, b) * power    } else {        return multiply_powers_of_2(a, b / power) * power    }}

It can be shown, that this operations really forms a field. Moreover, than can make sense as game theory operations, but that's not related to problem much. With the help of appropriate caching and grouping of operations, it is possible to calculate the product quickly enough, which is important to improve speed of the cryptoalgorithm. More formal definitions as well as additional properties can be clarified in the wikipedia article at link. The authors of the task hope that the properties listed in the statement should be enough for the solution.

Powering for such muliplication is defined in same way, formally $a^{\odot k} = \underbrace{a \odot a \odot \cdots \odot a}_{k~\texttt{times}}$.

You need to analyze the proposed scheme strength. For pairs of numbers $a$ and $b$ you need to find such $x$, that $a^{\odot x} = b$, or determine that it doesn't exist.

在现代密码学中，许多内容都与求解若干问题的算法复杂度密切相关。其中一个问题便是离散对数问题，其定义如下：

我们固定一个有限域及其两个元素 $a$ 和 $b$。目标是找出满足 $a^x = b$ 的整数 $x$，或判定这样的 $x$ 不存在。

目前，人类极有可能无法在足够大的域规模下高效求解离散对数问题。例如，在模素数的剩余类域中，长度为 1024 或 2048 比特的素数被认为具有足够安全性。然而，对如此大整数进行运算会给执行密码操作的服务器带来显著计算负载。因此，实践中常采用比简单模剩余类域更复杂的域结构：这类域上尚无利用其代数结构的快速算法，因而可选用更小规模的域，同时还能对运算进行恰当优化。

开发者尼古拉伊不信任当前通用的方法，因此希望自行设计一种新方案。最近，他了解到一种非常奇特的域——Nimber（尼姆数），并认为它非常适合该用途。

尼姆数域定义在整数集合 $\{0, 1, \dots, 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 = 8$
• $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$

形式上，该乘法算法可用如下伪代码描述：

multiply(a, b) {   ans = 0   for p1 in bits(a)       // a 中值为 1 的比特位编号       for p2 in bits(b)   // b 中值为 1 的比特位编号          ans = ans xor multiply_powers_of_2(1 << p1, 1 << p2)   return ans;}multiply_powers_of_2(a, b) {    if (a == 1 or b == 1) return a * b    n = 最大整数，使得 2^{2^{n}} <= max(a, b)    power = 2^{2^{n}};    if (a >= power and b >= power) {        return multiply(power * 3 / 2, multiply_powers_of_2(a / power, b / power))    } else if (a >= power) {        return multiply_powers_of_2(a / power, b) * power    } else {        return multiply_powers_of_2(a, b / power) * power    }}

可以证明，上述加法与乘法运算确实构成一个域。此外，这些运算亦可在博弈论中赋予意义，但这与本题关系不大。借助适当的缓存策略与运算分组，该乘法可被足够快速地计算，这对提升密码算法的整体速度至关重要。更严格的定义及其他性质可参见维基百科文章：链接。本题作者认为，题干中所列性质已足以支持求解。

对于该乘法运算，幂运算以通常方式定义，即形式化地记为

$$a^{\odot k} = \underbrace{a \odot a \odot \cdots \odot a}_{k~\texttt{次}}.$$

你需要分析该方案的安全性：对给定的数对 $(a, b)$，请找出满足 $a^{\odot x} = b$ 的整数 $x$；若不存在这样的 $x$，则予以判定。

In the first line of input there is single integer $t$ ($1 \le t \le 100$) — number of pairs, for which you need to find the discrete logarithm.

In each of next $t$ line there is a pair of integers $a$ $b$ ($1 \le a, b \lt 2^{64}$).

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示需要求离散对数的数对个数。

接下来的 $t$ 行中，每行包含一对整数 $a$ $b$（$1 \le a, b \lt 2^{64}$）。

For each pair you should print one integer $x$ ($0 \le x \lt 2^{64}$), such that $a^{\odot x} = b$, or -1 if no such x exists. It can be shown, that if any such $x$ exists, there is one inside given bounds. If there are several good values, you can output any of them.

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