Bad Cryptography
Contest: VK Cup 2019-2020 - Elimination Round (Engine)
Difficulty rating: 3400
Tags: math, number theory

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

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.

Input format:
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 < 2^{64}$$$).

Output format:
For each pair you should print one integer $$$x$$$ ($$$0 \le x < 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.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
7
2 2
1 1
2 3
8 10
8 2
321321321321 2
123214213213 4356903202345442785

Example output:
1
1
2
4
-1
6148914691236517205
68943624821423112

Editorial:
One of the well-known algorithms for the discrete logarithm problem is baby step giant step algorithm based on the meet in the middle idea. It can solve the problem in $$$O(\sqrt{|F|})$$$ time, which is definitely too much for the field of size $$$2^64$$$.
Multiplicative group of field has size $$$F = 2^64 - 1 = 3 \cdot 5 \cdot 17 \cdot 257 \cdot 641 \cdot 65537 \cdot 6700417$$$. We can see, that all numbers in this factoring are not too big. Let's try to find an answer modulo each of these primes. If we do that, we can restore the answer by the Chinese remainder theorem, and we are done.
Let $$$p$$$ be one of divisors. So, if $$$x = k * p + y$$$ is answer, than $$$a^{kp + y} = b$$$, than $$$a^{kF + y\frac{F}{p}} = b^{\frac{F}{p}}$$$. $$$a^F$$$ is equal to 1, so problem is equivalent to searching such an $$$y$$$, that $$$(a^{\frac{F}{p}})^y = b^{\frac{F}{p}}$$$, which is discrete logarithm problem on multiplicative subgroup of size $$$p$$$. So it can be solved using $$$O(\sqrt{p})$$$ multiplications, which is about 6000 multiplications total for all values of $$$p$$$.
If one of the discrete logarithms not exists, the total answer obviously not exists. Another corner case, that both values in subproblem can be equal to $$$1$$$. That means, that any value for this module is good. Also, this means, that $$$a$$$ and $$$b$$$ both have a smaller period, so any of these values would lead us to the correct answer.
Another part of problem is making multiplication fast enough. The first idea is to cache multiplications for powers of 2. This solution works for about 5 seconds in my implementation, and probably can be squeezed in time limit with some hacks. But multiplication can be done asymptotically faster. Let's $$$a = a_1 \cdot P + a_2$$$, $$$b = b_1 \cdot P + b_2$$$ is decomposition to first and second half of bits (in fact P is equal to power in multiply_powers_of_2 function). Then $$$a \odot b = (a_1 \cdot P + a_2) \cdot (b_1 \cdot P + b_2) = (a_1 \odot P \oplus a_2) \odot (b_1 \odot P \oplus b_2) = (a_1 \odot b_1) \odot (P \odot P) \oplus (a_2 \odot b_2) \oplus ((a_1 \odot b_2)\oplus(a_2\odot b_1))\odot P$$$.
As in Karatsuba algroithm, this 4 products can be reduce for 3, if one notice, that $$$(a_1 \odot b_2)\oplus(a_2\odot b_1) = (a_1 \oplus a_2) \odot(b_1\oplus b_2) \oplus (a_1\odot b_1)\oplus(a_2\odot b_2)$$$. The only diffrenece is instead of shift for multiplying on $$$P\cdot P$$$ we need to do one more multiplication.
But $$$P\odot P = P \oplus \frac{P}{2}$$$. We can multiply by them separately. Multiplying on $$$P$$$ is easy. The other one is multiplying on the power of 2, which can be done by the naive algorithm in linear time. On the other hand, we can just call multiply for the second one recursively, and it will work fast enough because most of the branches will lead to multiplying on zero. Also, to make things fast, one can precompute all multiplications for numbers smaller than 256. This makes multiplication about 5 times faster than naive approach.