在现代密码学中,很大程度上与解决几个问题的算法复杂性有关。此类问题之一是离散对数问题。其公式如下:
让我们修复一个有限域及其两个元素 $$$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