ACM通信

研究突出了

解剖:解决复合搜索问题的新范式

作者:伊泰·迪努尔，奥尔·邓克尔曼，内森·凯勒，阿迪·沙米尔
ACM通讯，2014年10月，Vol. 57 No. 10, 98-105页
10.1145 / 2661434
评论

组合搜索问题通常由一组可能的状态、一组将当前状态映射到下一状态的可能操作以及一对初始和最终状态来描述。算法问题是找到一个动作序列，将给定的初始状态映射到期望的最终状态。在本文中，我们引入了新的概念bicomposite搜索问题，并表明它们可以通过改进的时间和空间复杂性的组合来解决，使用一种新的算法范式，称为解剖．为了展示我们的新范式的广泛适用性，我们展示了如何使用它来解开魔方，并使用比之前描述的任何算法都更好的算法来解决典型的np完全分割问题。

回到顶部

1.简介

设计高效算法的一个核心问题是如何解决搜索问题，在搜索问题中，我们会得到一对状态和一组可能的动作，并要求我们找到如何通过执行一系列动作从第一种状态到达第二种状态。在某些情况下，我们只想确定这样的序列是否存在，而在其他情况下，这样的序列显然存在，但我们被要求找到最短的可能序列。许多这类搜索问题的关联决策问题是np完全的，因此我们不期望找到任何多项式时间的算法可以解决它们的所有实例。然而，我们希望找到新的指数时间算法，其指数小于已知的最好的算法。例如，破解密钥具有n= 100未知位无法通过穷举密钥搜索算法在实际时间内解决，因为它的时间复杂度为2ⁿ即使是目前最大的数据中心也无法达到。然而，如果我们设法找到运行时间为2的更好的密码分析攻击^{n/ 2}，我们可以用适当的努力打破这个方案，尽管这个复杂函数的指数性质。在这种情况下，一个通常很有用的技巧是找到攻击的时间和空间复杂性之间的权衡:详尽搜索需要很多时间，但只需要很少的内存，因此使用更多的内存(以预先计算值的大表的形式)来减少时间(通过跳过许多计算步骤)将是非常有益的。原因在本文的扩展版本中有解释(可在Dinur等人。²)，我们通常认为算法所需的时间和空间的乘积是我们试图最小化的适当的复杂性度量。在上面的例子中，用T= 2ⁿ时间和一个年代= 1空间不可行，用T= 2^{2n/ 3}时间和年代= 2^{n/ 3}空间(其产品TS= 2ⁿ和以前一样)是更好，但仍然是可行的，并打破它T= 2^{n/ 2}时间和年代= 2^{n/ 4}空间(其产品TS= 2^{3.n/ 4}指数更小)是完全可行的。

一个典型的搜索问题是由条件定义的F(例如，以一个CNF布尔公式的形式，它是子句的连词)和一个候选解X(例如，以0/1的形式对中所有变量赋值F)，其目标是在所有可能中找到X至少有一个满足条件F（X)是正确的。这样的表示没有内部结构，因为它使用的是的完整描述F和的全部价值X来决定是否F（X)是满意的。然而，我们通常可以替代全有或全无的选择X通过一系列较小的决定。例如，我们可以从对所有变量赋值为0开始，在每个阶段，我们可以决定翻转其中一个布尔变量的当前值。在这个过程的任何中间点F处于一种状态其中一些条款得到满足而另一些则不满足，我们的目标是达到一种状态其中所有条款同时得到满足。更一般地说，我们说搜索问题是复合如果解决方法可以用一系列原子动作来描述，即通过一系列中间状态将系统从初始状态改变到最终期望状态。大多数搜索问题都有这样的复合结构，可以用执行矩阵中描述的图1．这个矩阵的行表示状态年代₀，年代₁,……,一个nd the solutionX是由一系列的动作来表示的吗一个₁，一个₂,……在图的左边有动作一个_我改变状态年代_我1州年代_我．在许多情况下，原子操作是对状态的可逆操作，这使得映射成为可能年代_我1来年代_我通过使用动作一个_我，并绘制地图年代_我回年代_我1通过使用动作。例如，在布尔公式的情况下，我们允许翻转任意一个变量的当前值X，但是我们可以通过第二次翻转相同的变量来抵消它的影响，所以在这种情况下，动作和它的逆动作是相同的。在本文中，我们只考虑这种可逆的情况，这种情况允许通过对初始状态施加一些正向作用，对最终状态施加一些反向作用，并搜索一个中间相遇(MITM)状态来分割搜索问题。我们新的解剖技术甚至可以应用于某些动作是不可逆的情况下，但这使得它的描述更加复杂，其复杂性略高，如Dinur等人所讨论的。²

到目前为止，通过将解决方案流程划分为一系列原子操作，我们已经将执行矩阵划分为多行。为了应用我们新的解剖技术，我们还必须通过划分每个状态将执行矩阵划分为多个列年代_我成小块年代_我,我我们称之为底物，在图2．但是，只有子状态可以彼此独立操作的分区才对我们有用。我们说一个搜索问题有一个bicomposite结构如果它可以用一个执行矩阵来描述，其中动作的知识一个_我使得惟一确定子状态成为可能年代_我,我从年代_我1，j而且年代_我1，j从年代_我,我，即使我们对矩阵中其他的基态一无所知。这立即意味着，如果我们在执行矩阵中选择任何维度的任何矩形，基态的知识年代_我1，j，年代_我1，j＋1,……，年代_我1，k，沿着它的顶部边缘和行动的知识一个_我,一个_我＋1,……，一个它的左边足以计算基态年代_j,年代_，j＋1,……，年代_k，沿其底部边缘，反之亦然。

不是每个搜索问题都有这样的复合表示，但正如我们在本文中演示的，有许多众所周知的问题可以用这种方式表示。当问题是复合的时候，我们可以使用我们的通用新技术来提高效率。我们的主要观察是，在这种情况下，我们可以通过考虑在部分指定的中间状态只部分匹配两个方向的算法来改进标准MITM算法(在完全中间状态下尝试匹配向前和向后方向)。此外，我们可以逆转MITM算法的逻辑，而不是试图从执行的两端收敛到某个碰巧相同的中间状态，我们可以从所有可能的方式部分猜测这个中间状态开始，对于每个猜测值，我们可以将问题分解为两个独立的子问题，从这个中间状态向两个端点前进(利用这样一个事实，在复合问题中，我们可以确定长序列的动作对部分指定状态的影响)。然后，我们可以通过部分猜测执行矩阵中的附加子状态来递归地解决这些子问题。我们称这种方法为a解剖算法，因为它类似于外科医生在病人身体的不同位置进行一系列的捷径以实施手术的过程。例如，在第4节中，我们将展示如何解决众所周知的组合分区问题，首先猜测执行七分之三操作后的状态的七分之二位，然后再猜测执行七分之五操作后的状态的七分之一位，从而解决其中一个由此产生的子问题。

本文的主要目的是将这些新思想以最简单的方式应用于几个著名的搜索问题。我们有意忽略了几个令人讨厌的问题，这些问题的正确处理不容易解释，并忽略了几个可能的优化，这可以进一步降低我们的算法的复杂性。当我们分析算法的运行时间时，为了清晰起见，我们通常假设我们试图解决的实例是随机选择的，而我们试图猜测的中间状态是均匀分布的。

本文的组织结构如下。在第2节中，我们将魔方的最小步数问题描述为一个复合搜索问题，在第3节中，我们展示了如何用时间复杂度约为搜索空间大小的平方根，以及使用新解剖算法的最简单版本，空间复杂度约为搜索空间大小的四倍方根来解决它。在第4节中，我们描述了基本解剖技术的几个改进，并展示了如何使用它们来解决一个不同的搜索问题，称为“组合分区问题”，具有时间和空间复杂性的组合，这是任何以前发表的算法都无法实现的，而且更适合于大规模的基于fpga的硬件。我们在第5节对本文进行了总结。

回到顶部

2.将魔方表示为一个复合搜索问题

在本节中，我们将展示如何构建一个众所周知的解决标准3 × 3 × 3魔方问题的复合表示。⁶我们可以假设我们始终保持立方体在一个固定的方向上，其中白色的中心颜色在顶部，黄色的中心颜色在左侧，等等。27个子立方体中的一个位于立方体的中心，我们可以忽略它，因为它是完全不可见的。当我们旋转该(或其他)面时，每个面中心的6个子立方体不会移动，因此我们也可以在状态表示中忽略它们。我们可以采取的行动是将立方体的六个面分别旋转90度、180度或270度(我们不允许旋转一个中心切片，因为这会改变上面定义的立方体的标准方向)。因此，我们有18个原子动作，可以应用于多维数据集的每个状态。注意，所有这些动作都是魔方状态上的可逆映射，即90度旋转的逆方向就是270度旋转，并且它们都可以作为原子动作使用。

在27个可移动的子立方体中，12个有两种可见颜色，称为边子立方体，8个有三种可见颜色，称为角子立方体(图3)．每个这样的子立方体都可以通过其上的颜色组合来唯一地描述，例如蓝白(BW)边子立方体或绿橙红(GOR)角子立方体。此外，立方体上的每个位置都可以用它的相关边来描述(例如，顶部/底部、左边/右边、前面/后面的组合)。因此，我们可以用长度为20的向量来描述立方体的任何状态我的当前位置我子立方体(例如，向量的第一项总是指向蓝绿边子立方体，并指定它当前位于最前面的位置)。为了完成规范，我们还必须选择一些颜色的标准方向，并注意边子立方体可以是标准的(如BW)或倒置的(如WB)状态，每个角子立方体可以是三种可能的方向之一(如GOR, ORG，或RGO)。注意，任何可能的操作只能移动边子立方体到边子立方体，角子立方体到角子立方体。如果我们使用状态向量中的前12个位置来描述12个边子立方体的当前位置(以某种固定的顺序)，那么这些位置中的每个条目都可以用1到24之间的数字来描述(指定它当前位于12个可能位置中的哪一个，以及它的2个可能方向中的哪一个)。类似地，当我们使用状态向量中的最后8个位置来描述8个角子立方体的当前位置时(以某种固定的顺序)，那么这些条目中的每一个都可以再次包含1到24之间的数字，这次指定它位于8个可能位置中的哪一个，以及它位于3个可能方向中的哪一个。因此，我们可以用一个长度为20的向量来描述魔方的任何状态，这个向量的条目是1到24之间的数字。18个原子操作中的任何一个都将改变这个向量中的8个条目，通过将4个边子立方体和4个角子立方体移动到新的位置和方向，而保持其余12个条目不变。

现在，解决魔方的问题可以形式化为以下搜索问题:我们已知第一个长度为20的向量(表示魔方的初始无序状态)和第二个长度为20的向量(表示魔方的标准无序状态)。我们想找到一个原子动作序列(以脸部旋转的形式)，它将把第一个向量变成第二个向量。发现一些序列是很容易的，在娱乐数学文献中描述了许多算法来实现这一点(其中一些在Slocum中描述⁶)．然而，这些算法通常非常浪费，使用50到100个操作，以某种固定的顺序将子数据集移动到正确的位置，忽略了这些操作对其他子数据集的影响。有些算法使用的动作更少，但它们也更难描述，因为它们需要在选择第一个动作之前对整个状态进行非常详细的案例分析。最近，Davidson等人。¹证明如果我们想解决问题，20个行动是必要和充分的任何魔方的可解状态，但这是一个存在的结果，作者并没有给出一个有效的方法来找到这样的序列。注意，20个原子操作的可能序列的数量是18^20.= 12748236216396078174437376 2⁸³，但我们可以将搜索空间的大小略微减少到18 × 15¹⁹= 399030807609558105468750 2⁷⁸注意到连续两次旋转同一张脸是没有意义的。然而，即使这种缩小的大小也不能在可行的时间内进行彻底搜索。

为了表明我们对搜索问题的表示是复合的，假设我们知道特定子立方体的当前位置和方向(即，我们知道的值年代_我1，j在执行矩阵中以1到24之间的数字表示)，我们对其应用一些已知的面部旋转动作。然后，我们可以惟一地确定特定子立方体的新位置和方向(即年代_我,我)，即使我们不知道任何其他子立方体的当前位置和方向(即所有其他子立方体)年代_k,执行矩阵中的值)。请注意，许多其他魔方状态的自然表示没有这样的复合结构。例如，如果我们将状态向量中的第一项与一个特定的立方体位置(如top-front)相关联，并使用它来表示哪个边子立方体(如BW)当前位于其中以及处于哪个方向，那么仅在第一状态中的这一项并不能告诉我们，如果我们将顶面旋转90度，那么哪个边子立方体(如GR)将取代它在top-front位置。这样的表示需要执行矩阵中其他列的知识，这取决于对状态应用的是哪个动作，因此我们不能在新的解剖技术中使用它。

如第3节所示，我们可以使用双复合表示，对任何给定的魔方初始状态，使用完全可行的时间复杂度(即搜索空间大小的平方根)组合来找到一个多达20个面旋转的序列³⁹步骤，或在标准PC上几分钟)和一个空间复杂度大约是这个数字的四次方根(即大约2^19.5内存位置，或几兆字节)。最终的算法是完全通用的，除了它的双复合性之外，没有使用问题的细节，并匹配了之前解决魔方的最佳算法(大约25年前设计，见Fiat et al.)的复杂性。^3.)具有高度的特异性，并且依赖于魔方所定义的排列集合的群论性质。

回到顶部

3.基本解剖技术

我们现在假设我们有一个初始状态向量年代₀最后一个状态向量年代我们的目标是找到一系列的原子动作一个₁，一个₂,……，一个将初始态转化为最终态。如上一节所述，我们知道这一点= 20足够找到一个解决方案，因此我们的目标是找到一个₁，一个₂,……，一个_20.．

我们的解剖算法是经典MITM算法的扩展，MITM算法于1974年由Horowitz和Sahni首次提出⁵来解决背包问题我们可以将MITM算法应用于几乎任何具有可逆动作的复合问题。当搜索空间的大小为2时ⁿ， MITM算法大约需要2^{n/ 2}时间和2^{n/ 2}空间。为了完整起见，下面我们将描述如何将该算法应用到魔方的情境中，魔方的搜索空间约为2⁷⁸州。在这个例子中，时间复杂度是2^78/2= 2³⁹是可行的，但是空间复杂度为2^78/2= 2³⁹随机访问内存位置的开销太大。

文中给出了算法的完整细节图4．算法的第一步是迭代所有可能的20/2 = 10的动作序列一个₁,……，一个₁₀．我们有18 × 15⁹2³⁹这样的序列，对于每一个，我们将其操作应用于年代₀的可能值年代₁₀．我们存储2³⁹的值一个₁,……，一个₁₀的对应值旁边的列表中年代₁₀,^一个根据的列表年代₁₀．接下来，我们迭代所有可能的动作向量一个₁₁,……，一个_20.．大概有2个³⁹这样的作用向量，对于每一个，我们用它的反向作用年代_20.的可能值年代₁₀．现在我们在排序列表中搜索这个值年代₁₀，对于每一个匹配，我们获得对应的值一个₁,……，一个₁₀从列表和输出一个₁，一个₂,……，一个_20.作为解决方案。

MITM算法大约需要2³⁹内存单元用来存储排序后的列表，其时间复杂度约为2³⁹，这是迭代每个动作向量所需的时间一个₁,……，一个₁₀而且一个₁₁,……，一个_20.．

3.1.利用解剖改进MITM算法

在本节中，我们将展示如何通过使用我们新的解剖技术的基本版本来改进魔方上的经典MITM算法。这里的主要思想是通过迭代中间状态的某些部分的所有可能值来“解剖”中间的执行矩阵年代₁₀．部分的大小年代₁₀我们选择的迭代是这样的，它包含大约2^{n/ 4}= 2^19.5部分国家。自年代₁₀表示为一个20个条目的向量，其中每个条目可以获得24个值，我们选择迭代它的前4个条目，这可以假设大约24⁴2^18.5值。的每个这样的部分值年代₁₀，我们使用问题的复合结构，以便独立地处理两个部分执行矩阵，如图5作为红色和蓝色的矩形，最后结合部分解以获得完整的动作向量。

文中给出了算法的完整细节图6．我们有一个外部循环，它迭代所有可能的值年代_10、1，年代_10、2，年代_10日,3，年代_10、4．假设这个值的猜测是正确的，我们首先集中在执行矩阵的上部，并找到所有的部分动作向量一个₁,……，一个₁₀的变换年代_{0 1}，年代_{0, 2}，年代_{0, 3}，年代_{0, 4}成年代_10、1，年代_10、2，年代_10日,3，年代_10、4．这是在这个较小的执行矩阵上使用一个简单的MITM算法完成的。对于每一个解决方案一个₁,……，一个₁₀在我们使用MITM算法得到的，我们应用它的动作到完整的状态年代₀，获取完整的候选值年代₁₀状态，并存储在旁边一个₁,……，一个₁₀在一个列表。在MITM算法填充完列表后，我们根据的值对其进行排序(例如，按某种字典顺序)年代₁₀．

现在我们关注底层的执行矩阵，并找出所有的部分动作向量一个₁₁,……，一个_20.的变换年代_10、1，年代_10、2，年代_10日,3，年代_10、4成年代_20日,1，年代_20日,2，年代_20日,3，年代_20日,4．我们使用与上面部分相同的思想，也就是，我们在底层执行矩阵上执行MITM算法。对于每一个解决方案一个₁₁,……，一个_20.我们得到的，我们应用它的逆作用年代_20.的值年代₁₀．然后，我们检查匹配年代₁₀在排序后的列表中，对于每个匹配，我们输出一个完整的解决方案一个₁，一个₂,……，一个_20.．

为了对算法进行分析，我们确定了年代_10、1，年代_10、2，年代_10日,3，年代_10、4并估计上(小)执行矩阵的平均解数。即，我们计算动作向量的期望数量一个₁,……，一个₁₀的变换年代_{0 1}，年代_{0, 2}，年代_{0, 3}，年代_{0, 4}成年代_10、1，年代_10、2，年代_10日,3，年代_10、4．首先，我们注意到可能的动作向量的数量一个₁,……，一个₁₀大约是2³⁹．每个这样的动作向量都在变换年代_{0 1}，年代_{0, 2}，年代_{0, 3}，年代_{0, 4}转换成任意匹配的部分状态年代_10、1，年代_10、2，年代_10日,3，年代_10、4概率约为1/(24⁴) 2^18.5(这与可能值的数量成反比年代_10、1，年代_10、2，年代_10日,3，年代_10、4)．因此，解的期望数量(我们存储在排序列表中)是2³⁹×2^18.5= 2^20.5．

一般情况下，MITM算法的时间复杂度约为搜索空间的平方根，因此其在上执行矩阵上的时间复杂度约为2^39/2= 2^19.5．然而，由于在这种情况下，我们不能将问题分成完全相同大小的两部分，所以我们希望是2^20.5解决方案(我们枚举和存储)，因此它的时间复杂度略微增加到2^20.5．这也是底部的MITM算法的预期时间复杂度(虽然这里我们不存储解决方案，但立即检查每一个)。因为我们有一个外部循环，我们执行24⁴2^18.5乘以，整个算法的期望时间复杂度约为2^{18.5 + 20.5}= 2³⁹．预期的内存复杂度是2^20.5，需要在上面的部分存储MITM的解决方案(注意，我们重用这个内存的每个猜测年代_{0 1}，年代_{0, 2}，年代_{0, 3}，年代_{0, 4})．

回到顶部

4.解剖技术的提高

仔细观察第3节给出的算法，可以发现该算法对执行矩阵的顶部和底部的处理是不同的。事实上，虽然上面部分的建议存储在表中(l₁₀在这个例子中图6)时，将根据表值实时检查底部部分的建议。因此，虽然上面部分的建议数量由上面的算法可用内存大小限制，但下面部分的建议数量可以任意大，并以任意顺序实时生成。

这表明，对执行矩阵进行非对称分割，使执行矩阵的下半部明显大于上半部，可以提高算法的性能。

在本节中，我们将说明事实确实如此。由于第3节中给出的解魔方算法在PC上已经很实用了，因此对其进一步改进没有显著的价值，我们选择了另一个经典的搜索问题，称为组合分区问题作为本节的运行示例。

问题定义如下。我们有一组n整数,U= {x₁，x₂,……，x_n}。我们的目标是分割U分成两个互补的子集U₁，U₂它们的元素和是相同的数，也就是，

已知组合划分问题是np完全的，⁴因此，一般情况下我们不能期望得到次指数解。然而，有各种技术可以在不同的情况下有效地找到解决方案，特别是当存在许多分区(U₁，U₂)，满足式(1)。因此，我们考虑问题的“最难”实例，其中每一个x_我年代的n二进制表示的数字(即:x_我2ⁿ)．在这种情况下，最多只有几个解(U₁，U₂)的存在，且该问题没有已知的次指数算法。为了简单起见，我们将重点放在模块化式(1)略变为

作为一个具体的数值例子，考虑这种情况n= 112。在本例中，检查所有2¹¹²当然，可能的分区是完全不可行的。标准MITM算法允许将时间复杂度降低到2⁵⁶，但将空间复杂度增加到2⁵⁶这在目前是不可行的。如下所示，该问题可以表示为一个复合问题，因此，可以应用第3节的技术来获得更好的权衡T= 2⁵⁶而且年代= 2²⁸．虽然这些数字几乎是实际的，相对较大的内存要求不允许在计算中使用fpga，这使得它几乎是可行的。下面用an表示不对称通过解剖算法的变体，我们可以得到其复杂性T= 2⁶⁴(只有2⁸倍)和年代= 2¹⁶(2¹²times small)，它允许使用内存受限的fpga实现更快的计算。注意，根据复杂度衡量，非对称解剖算法的性能是对称算法的16倍年代×T(复杂性为2⁸⁰与2⁸⁴)．这样一个因素，虽然不是特别大，但在实际场景中会产生影响。

4.1.将组合划分表示为一个复合搜索问题

为了将分解算法应用于组合划分问题，我们必须找到一种将其表示为复合搜索问题的方法。

首先，我们把它表示成一个复合问题。我们处理选择分区的问题(U₁，U₂)作为一个序列n原子决策，其中我决定是是否分配x_我U₁或x_我U₂．我们引入了一个计数器C它最初被设为0，然后在我第一步，如果选择是x_我U₁然后C取而代之的是C+x_我(国防部2ⁿ)，如果选择的话x_我U₂，C取而代之的是Cx_我(国防部2ⁿ)．注意，的值C后nth步骤是(国防部2ⁿ)，因此，当且仅当的最终值为C是零。

在这种表示中，划分问题具有复合问题的所有元素:初始状态(C_最初的= 0)，最终状态(C_最后= 0)，以及序列n步骤，这样在每个步骤中，我们必须从两个可能的原子操作中选择一个。我们的目标是找到从初始状态到最终状态的一系列选择。根据执行矩阵，我们定义年代_我的价值C后我第一步n-bit二进制数)和一个_我成为行动的转变年代_我1来年代_我，其可能的值为eitherCC+x_我(国防部2ⁿ)或CCx_我(国防部2ⁿ)．

第二步是将问题表示为一个复合问题。我们在这里使用的主要观察结果是，对于任意两个整数a、b,米的第一个最低有效位一个+b(国防部2ⁿ)只取决于米lsb的一个而且b(而不是用其他手指)。因此，如果我们知道米lsb的年代_我1和行动一个_我，我们可以计算米lsb的年代_我．

利用这个观察，我们定义年代_我,我是jth LSB的年代_我．这就导致了n——- - - - - -n执行矩阵年代_我,我为我,我1、2、…n如果我们在执行矩阵中选择任何一个矩形哪个包含矩阵的最右列，关于基态的知识沿其顶边和知识的动作一个_我,一个_我＋1,……，一个它的右边足以计算基态沿着它的底部边缘。

请注意，我们的执行矩阵所满足的条件比复合问题定义中给出的条件要弱，因为在我们的例子中，“矩形”属性只适用于特定类型的矩形，而不是所有的矩形。然而，正如我们在下一小节中所展示的，即使这个较弱的性质也足以应用我们所介绍的所有解剖算法。^b

4.2.组合划分问题的解剖算法

算法的基本思想是将状态矩阵分成7(!)部分n/每7个步骤，其中三个部分属于顶部年代^t四部分属于底部年代^b．分区是通过枚举2得到的n/7状态的lsb年代_{3.n/ 7}．

为每个值v在这些比特中，我们在顶部执行一个简单的MITM算法，其结果约为2^{3.n/ 7}×2^{2n/ 7}= 2^{2n/ 7}可能的动作组合一个₁，一个₂,……，一个_{3.n/ 7}这导致了一个国家年代_{3.n/ 7}的2n/ 7lbs等于这个向量v．对于每一个组合，我们计算状态的全部值年代_{3.n/ 7}．的结果值年代_{3.n/ 7}存储在一个表中，以及对应的一个₁，一个₂,……，一个_{3.n/ 7}．

然后我们考虑底部的部分，并对其应用第3节所述的分割算法(即将其划分为4个块)n/ 7步骤每个)。结果是2^{4n/ 7}×2^{2n/ 7}= 2^{2n/ 7}可能的动作组合一个_{(3n/ 7) + 1}，一个_{(3n/ 7) + 2},……，一个_n是什么导致(反方向)一个状态年代_{3.n/ 7}的2n/ 7lbs等于这个向量v．对于每一种组合，我们计算全部值年代_{3.n/ 7}并与表格中的值进行比较。如果找到匹配，这意味着相应的序列{一个₁，一个₂,……，一个_{3.n/ 7}},一个_{(3n/ 7) + 1}，一个_{(3n/ 7) + 2},……，一个_n匹配产生问题的解决方案。注意，如果存在一个解决方案，那么我们的方法必须找到它，因为它实际上会遍历所有可能的操作组合(尽管，以一种复杂的方式)。文中给出了该算法的伪代码图7．

该算法的内存复杂度为O（2^{n/ 7})，因为无论是对顶部的标准MITM算法还是对底部的解剖算法都具有这种复杂性。对于底层算法，复杂度为(2^{4n/ 7}）^1/4= 2^{n/ 7}．）

时间复杂度是2^{4n/ 7}．事实上，在国家的枚举年代_{3.n/ 7}执行超过2次^{2n/ 7}值时，上半部的标准MITM算法和下半部的解剖算法都需要2^{2n/ 7}时间，剩下2个^{2n/ 7}可能的组合一个_{(3n/ 7) + 1}，一个_{(3n/ 7) + 2},……，一个_n立即检查。这导致时间复杂度为2^{2n/ 7}×2^{2n/ 7}= 2^{4n/ 7}．

在特殊情况下n= 112, 7个chunk中每个chunk包含16个步骤，对状态的28个lbs执行枚举年代₄₂，内存复杂度为2^{n/ 7}= 2¹⁶，时间复杂度为2^{4n/ 7}= 2⁶⁴．

4.3.先进的分离算法

第3节和本节中介绍的算法是两个最简单的解剖算法，它们演示了该技术背后的一般思想。在论文的扩展版中，²我们提出了更高级的解剖算法，其中包括将矩阵划分为“奇异”数量的部分，如11和29，并在我们的一般框架内展示了这种选择的最优性。

到目前为止，我们只考虑了不允许失败的搜索算法(即，如果问题有任何解决方案，那么我们的算法总是会找到所有的解决方案，但如果实例不是随机选择的或解决方案的数量太大，它的运行时间可能会比预期的长)。在Dinur等人的研究中，²我们还考虑了在小概率下可能无法找到解决方案的算法，并展示了如何通过将它们与一种称为“经典技术”的方法相结合来提高我们的算法的效率并行碰撞搜索，由维纳和范·奥尔肖特在1996年设计。⁷

回到顶部

5.结论

在本文中，我们引入了复合搜索问题的概念，并发展了一种新的算法技术，称为解剖算法，以改进时间和空间的复杂性来解决这类问题。我们通过将这些技术应用于两种标准类型的问题(魔方和组合分区)来演示如何使用这些技术。然而，这些技术的一些最令人兴奋的应用是在密码分析中，这超出了本文的范围。例如，许多银行仍在使用一种称为3该软件使用三个独立的密钥对敏感的金融数据进行三次加密。一个自然的问题是是否使用quadruple-DES(使用四个独立的密钥对数据进行四次加密)将提供更大的安全性，因为它的密钥更长，加密过程更复杂。通过我们新的分解技术，我们可以得到一个惊人的结果，即四倍des加密方案的全密钥查找与简单的三倍des加密方案的全密钥查找在时间和空间上基本相同，因此将三倍des加密方案升级为四倍des没有显著的安全优势。

回到顶部

致谢

第二作者(O.D.)部分获得了以色列科学基金会(Israel Science Foundation)的827/12号拨款，部分获得了德国-以色列科学研究与发展基金会(german -Israel Foundation for Scientific Research and Development)的2282-2222.6/2011号拨款。第三位作者(N.K.)得到阿隆奖学金的支持。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2014 ACM股份有限公司

---

没有发现记录