← 返回题目列表

Codeforces · 1310/F

F. 错误的加密技术

中文机器翻译题面 查看原题

在现代密码学中,很大程度上与解决几个问题的算法复杂性有关。此类问题之一是离散对数问题。其公式如下:

让我们修复一个有限域及其两个元素 $$$a$$$ 和 $$$b$$$。人们需要有趣这样的 $$$x$$$ $$$a^x = b$$$ 或检测不存在这样的 x。

现代人类很可能无法解决足够大的场大小的离散对数问题。例如,对于以素数为模的留数字段,1024 或 2048 位的素数被认为是安全的。然而,如此大的数字计算可能会给执行加密操作的服务器带来巨大的负载。因此,通常使用更复杂的字段,而不是简单的模块残差字段。对于这样的字段,不知道使用字段结构的快速算法,可以使用更小的字段并且可以适当地优化操作。

开发人员 Nikolai 不相信普遍接受的方法,因此他想发明自己的方法。最近,他读到了一个非常奇怪的领域——数字,并认为它非常适合这个目的。

nimbers 字段是在从 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 \o加上 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$$$

形式上,该算法可以通过以下伪代码来描述。

可以证明,该操作确实形成了一个字段。此外,比作为博弈论运算是有意义的,但这与问题没有太大关系。借助适当的缓存和操作分组,可以足够快地计算乘积,这对于提高密码算法的速度非常重要。更正式的定义以及其他属性可以在链接的维基百科文章中进行澄清。该任务的作者希望声明中列出的属性对于解决方案来说应该足够了。

这种乘法的供电以相同的方式定义,形式为 $$$a^{\odot k} = \underbrace{a \odot a \odot \cdots \odot a}_{k~\texttt{times}}$$$。

您需要分析所提出的方案的强度。对于数字对 $$$a$$$ 和 $$$b$$$,您需要找到这样的 $$$x$$$,即 $$$a^{\odot x} = b$$$,或者确定它不存在。

输入

在输入的第一行中有一个整数 $$$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$$$,则在给定范围内也有一个。如果有多个好的值,则可以输出其中任何一个。

示例

输入 #1

7
2 2
1 1
2 3
8 10
8 2
321321321321 2
123214213213 4356903202345442785

输出 #1

1
1
2
4
-1
6148914691236517205
68943624821423112