常数深度量子电路的复杂性分析及应用

1FFFFFF等深度精确量子回路体系的坍缩高桥康弘和谷诚一郎NTT通信科学实验室，NTT Corporation{takahashi. 你是我的朋友。seiichiro}@lab. ntt。co。JP摘要研究了具有无限扇出门的常数深度多项式量子电路（称为QNC0电路）可精确实现的量子操作的量子复杂性类QNC0我们的主要结果是量子OR操作在QNC0中，这是一个肯定的结果，并且证明了量子OR操作是H_∞和S_∞的等价. 在对复杂的复杂性计算的结构性分析中：NC0AC0TC0，我们与H？y？r和S？palek一起使用时对应量子的层次：QNC0=QAC0=QTC0。然后，我们证明，f f f存在用于量子阈值操作的恒定深度次二次尺寸量子电路这意味着QNC0和QTC0电路之间的大小差异，以实现相同f f量子操作 最后，我们证明，如果量子傅里叶变换模一个素数是在QNC0中，存在一个利用QNC0预言机求解离散对数问题的多项式时间精确经典算法这意味着，在一个合理的假设下，存在一个经典的困难的问题，这是可以解决的QNC0电路与门的量子傅里叶变换。1介绍和结果量子计算机有望比经典计算机更快地解决一些问题（例如，Shor的f ac t o r i n g a l go r it h m [ 2 1 ]）。 也就是说，对于相当大的输入大小，如何使一个量子计算机能够执行量子算法。实现量子计算机的一个主要障碍是，即使我们可以准备许多量子位，由于相干时间，我们只能在很短的时间内使用它们。为了有效地使用这种脆弱的量子比特，重要的是要了解使用它们的可能性和局限性。这促使我们研究具有少量计算时间的量子电路的计算能力[16，12，10，15，9，2，3]。在本文中，我们专注于常数深度多项式尺寸量子电路的计算能力的理论分析，这使我们能够分析，多量子深度的。基本门是单量子位、CNOT和无界扇出门。无界扇出门是一个模拟的经典的一个通常被认为是一个基本的门的理论研究的经典电路[24]。n+1个量子比特上的门在叠加中产生经典源比特的n个副本从理论上讲，将门作为基本门来处理是很有趣的，因为门的使用澄清了量子电路和经典电路之间的许多差异[12，15]，并将量子电路模型与单向模型[6]联系起来。研究恒定深度经典电路有三个重要的设置。所有设置都允许使用（经典）无界扇出门。第一个设置处理常数深度多项式大小的经典电路组成的非门和或和与门有界扇入。经典复杂性类NC0是可由经典电路（的均匀族）在该设置中解决的问题的类第二种设置是第一种设置，增加了具有无界扇入的OR和AND门，定义了AC0类。第三个设置是第二个设置，增加了具有无界扇入的阈值门，定义了TC0类。阈值门实现阈值功能，该阈值功能输出表示输入的汉明权重是否小于预定阈值的比特。这些类形成严格的层次结构：NC0AC 0TC0 [11，24]。一些作者考虑了上述设置的量子对应物[16，12，15]。虽然很难确定正确的对应物是什么，但我们将以下设置视为对应物[12]，其中所有设置都允许使用无界扇出门。第一设置arXiv：1112.6063v2 [quant-ph] 2012年92FFFFFFFFFFFnnn√FFFFFFFFFFFFFFFFFFF处理由一个量子比特和CNOT门组成的常数深度多项式大小的量子电路量子复杂度类QNC0，对应于NC0，是可由设置中的量子电路（称为QNC0电路）（的均匀族）精确实现的量子操作的类。第二种设置是第一种设置，增加了具有无界扇入的或门的量子版本，其定义了类QAC0，对应于AC0。第三个设置是第二个设置，增加了具有无界扇入的量子版本的阈值门，定义了类QTC0，对应于TC0。它认为QNC0<$QAC0=QTC0[15]。首先，为了研究QNC0和QAC0之间的关系，我们考虑所提出的问题f f本文通过H_（15）和S_（15）证明了一个O（1）-depp_（n）-sizesquan_n的递归算法对于量子运算ORn ，它计算n位的OR函数。他们证明了存在一个O（ logn）-深度O（nlogn）-大小的量子电路。它是OR归约的重复，表示为O（1）深度电路，它将n位OR函数的计算精确地减少到O（logn）位。根据他们的工作，我们对这个问题给出了肯定的回答：定理1存在一个O（1）-深度O（nlog n）-大小的量子电路（或n）.定理1直接意味着ORn在QNC0中，因此QNC0=QAC0。因为QAC0=QTC0，如上所述，QNC0、QAC0和QTC0的层次结构崩溃，即，QNC0=QAC0=QTC0。这f f f f f f与相应的经典类的严格等级形成鲜明对比：NC0AC0TC0。更重要的是，具有高度优先级和S级优先级的1号或1号存储器的存储器完全依赖于以下存储器的优先级多量子深度精确量子电路崩溃，即， QNCk=QACk =QTCk 对于任何整数k≥0，其中QNCk、QACk和QTCk分别与QNC0、QAC0和QTC0类似地定义只不过他们处理的是O（logkn）深度的电路，而不是O（1）深度的电路。我们认为，如果要在电路中进行故障检测，首先要考虑的是一个简单的硬件和软件包，我们在O（logn）位上计算OR函数，深度为O（1），大小为logn。指数大小电路是基于OR函数的表示，作为指数许多奇偶函数的R线性组合。定理1的证明依赖于这样的事实，即在QNC0电路中，无界扇出门可以用作奇偶校验门[12]，其实现奇偶校验。功能然而，我们注意到，QNC0=QAC0 不能只从在相应的经典电路中的奇偶校验门的计算能力，即，在NC0电路中这是因为，即使NC0电路中允许奇偶校验门，NC0中也没有OR功能[15]。其次，我们应用定理1研究了QNC0QTC0详细为此，我们考虑为量子阈值操作THt构造O（1）深度的小尺寸量子电路的问题，该量子电路计算阈值函数，阈值t为n比特。定理1简单地给出了一个O（1）-深度O（tnlogn）-大小的量子电路，其中THt满足1≤t≤n/2一个O（1）-深度O（（n-t+1）nlogn）-大小的电路，其中≤t≤n。我们证明，使用定理1，对于任何t，使得t和n-t的最小值是非常数，存在一个较小的电路：定理2对于 THt，存在如下O（1）-深度量子电路：• 对于任意1 ≤ t ≤ log n或n − log n ≤ t ≤ n，一个时间复杂度为O（n log n）的电路。• 一个O（n≠t log n）大小的电路，对于任何log n ≤ t ≤n/2 n。• 一个时间复杂度为O（n（n − t）log n）的电路，对于任何<$n/2 <$t ≤ t ≤ n − logn。定理2意味着用于实现相同的QNC0和QTC0电路之间的大小差异f f量子操作设Un是n个量子比特上的量子操作假设我们有一个最优尺寸QTC0电路，其尺寸用多项式s（n）表示同样，让t（n）（≥s（n））是最优QNC0电路尺寸。QNC0的定义仅在t（n）处使用th，bounddabovebypoly（n）. 算法的复杂度为O（s（n）s（n）llogn）。我是我是因为我们可以通过转换每个阈值来获得O（s（n）s（n）logn）大小的QNC0电路通过定理2将最佳大小的QTC0电路选通到QNC0电路中f f定理2中的电路的关键成分是用于量子计数操作的O（1）深度O（n2）大小的量子电路，其计算n位上的计数函数，该计数函数输出3FFFFFFFFF⌈⌉FFFF输入的汉明权重的二进制表示。我们构造该电路的思想是，在一个可编程的H∞和S∞palek的O RRRi in的基础上，在O（log n）个量子比特上，在深度O（1）和大小指数为log n的情况下，实现一个四阶傅里叶变换（QFT）的并行化的QFT部分并行执行许多投影测量，并将定理1中的电路应用于测量的经典结果以估计傅立叶状态的相位。它类似于O（logn）-深度O（nlogn）-大小的量子电路，用于近似n个量子比特上的QFT [8]。主要区别在于QFT部分需要比[8]中的门指数更多的门来构造O（1）深度的精确电路。然而，由于输入大小是O（logn），因此大小仍然是poly（n最后，我们应用定理1研究了QNC0高效的古典计算更具体地说，定理1的基础上，我们研究的存在性的经典困难的问题1是可解的QNC0电路，其中的问题被称为是经典困难的，如果它不能解决的多项式时间有界误差的经典算法。要做到这一点，我们考虑的问题，是否多项式时间精确的经典算法使用QNC0的预言可以构建一个离散对数问题（DLP），似乎经典硬。在这里，QNC0oracle解决了，经典的常数时间，一个问题，这是解决完全由QNC0电路. 这样的算法的DLP意味着在DLP是经典困难的合理假设下存在所需的问题。这是因为具有QNC0预言的多项式时间有界误差经典模拟的算法将暗示DLP不是经典困难的。根据Shor的有界性要求，对于一般的D L P [ 2 1 ]，H_（？）y和S_（？）表明存在使用QNC0oracle的有界误差版本的多项式时间有界误差经典算法[15]。然而，很难将该算法直接转换成一个exactonee。根据Dam的针对一般DLP[23]的期望算法，其中，对于Mos_ca和Z_ka的[17]而言，其是非常简单的，因此，使用该算法1，并且根据QFT，存在针对特定类型的DLP的期望算法，其看起来是经典困难的定理3设q是安全素数，即，对于某个素数p，一个素数的形式为2 p+1，n=log q。 如果QFT模p在QNC0中，则存在使用QNC 0预言机的整数模q的乘法群上的DLP的poly（n）时间精确经典算法。我们注意到，在密码学文献中，我们假设存在无限多个安全素数。由于我们需要关于QFT的假设，定理3并不意味着存在上述问题（在一个合理的假设下）。然而，它使我们能够加深我们对QNC0，QFT和有效的经典计算之间的关系的事实上，这意味着，在定理3中的DLP是经典困难的合理假设下，存在一个经典困难的问题，该问题可由具有QFT模p的门的QNC0电路精确求解。定理3提出了以下关键问题，以进一步理解QNC0和有效的经典或量子计算：QFT模p在QNC0中吗？如果这是在这种情况下，定理3意味着存在一个经典的困难问题，可以通过一个QNC0电路（在合理假设下）。 如果不是，QNC0严格弱于有效量子f f更准确地说，它严格包含在可实现的量子运算类近似地（甚至精确地）通过多项式大小的量子电路。这是因为QFT模p属于后一类[17，13，15]。我们把QFT模p问题作为一个开放问题。f的算法（一种简单的模乘算法）和用于DLP的Dam算法都是QFT模p、算术运算（我们对算法的严格分析表明，除了QFT之外的这些组件可以通过使用OR函数和预先计算值的迭代乘法来实现多项式时间精确经典算法。根据定理1的分析，推论出定理3。本文的其余部分组织如下。在第二节中，我们给出了一些定义和OR约化的概念，以精确地描述我们的结果在第3节和第4节中，我们分别描述定理1和定理2中的在第5节中，我们描述了定理3中的算法在第6节中，我们给出了一些开放的问题。大部分证明都在附录A中给出。1我们不仅处理决策问题，而且处理关系问题，其中关系问题对于输入可以有许多有效（多项式长度）输出一个解决这样一个问题的算法输出其中任何一个[1]。4nn1j=0nnnnnnFFFnKj=0J J0n−1nn222nnnnnMy=0时M2预赛2.1量子电路和复杂性类我们使用量子态的标准符号和量子电路的标准图[18]。量子电路由基本门组成，其中基本门是单量子位、CNOT和无界扇出门（除非另有说明）。k+ 1个量子位上的无界扇出门实现定义为|yOk−1j=0|y|y⟩Ok−1j=0|xj⊕y⟩,其中y，xj∈ {0，1}，k≥ 1，且k表示模2加法。第一输入量子位，即，量子比特的状态|称为控制量子位。当k= 1时，门是CNOT门。 由于无界函数使类的可操作性更强，因此我们可以称之为“可操作性”，而这种可操作性是新的。量子电路的复杂性度量是它的大小和深度。量子电路的大小被定义为其中所有基本门的总大小，其中基本门的大小被定义为受门影响的量子比特的数量量子电路的深度定义如下。输入量子位被认为具有深度0。对于每个门G，G的深度等于1加上G所依赖的门的最大深度量子电路的深度定义为其中门的最大深度直观地说，深度是电路中的层数，其中一层由可以并行应用的门组成 量子电路可以使用初始化为|0分。对于a=a0···an−L1∈{0，1}n\{0n}，具有vanbits，dentdapAa的parityfionn定义为PA a（x）=n−1a x，其中x= x· · ·x∈ {0，1}。 我们将PA表示为PA。为例如，PA10（x）= x0，PA01（x）= x1，PA11（x）= PA 2（x）= x0x1。对于任意整数1≤t≤n，具有三个存储块的三个存储函数，定义为THt（x）=1，如果|X|≥t否则为0，其中x = x0···xn−1∈ {0，1}n，|X|=n−1xj，x的汉明重量。的在n位上的OR函数（表示为ORn）被定义为TH1。在n位上的AND函数（表示为ANDn）被定义为THn。对于任何整数1≤t≤n，值为t的n位精确函数，记为作为EX t，其定义类似于TH t， 除了|X|TH定义中的≥ t t替换为|X|= t。函数EX0被定义为ORn的否定。 用于计算PAa的量子运算是定义为n−1On−1j=0|z→|z⟩›→j=0|z<$P A a（x）<$，|z⊕PAa(x)⟩,其中xj，z∈ {0， 1}且x=x0···xn−1。为了简单起见，该操作也被表示为PAa。的类似地定义量子运算THt、ORn、ANDn和EXt 对于任何整数m>0，n nquantumFo rrtransformurmurt ra n s f o r m ur dasFm ，是quan tu mopprat ionns f o r m u r a n s f o rm u ra n s f o r m u r d asf o r m u r a n s f o r m u r a n s f o r m u r d a s f o r m u r a n s f or m u r a n n s f o r m ur a n s f o r m u r a n n s f o r m u r a n s f o r m u r a n s f o r a n s f o r m u r a n s f o r m u r a m u r定义为|x<$→1m−1ωxy|y，其中0≤x≤m− 1且ω=e2 πi/m。量子复杂度类QNC0量子运算的种类是否可以精确由（统一的家庭）常数深度多项式大小的量子电路组成的上面描述的门。QAC0的定义与QNC0除了量子电路可以使用ORk的门作为由任意poly（n）限定的任何k的基本门，对于输入长度n。 QTC0的定义与QAC0的定义相同，只是量子电路f f可以使用一个门THt 作为由任意poly（n）限定的任意k的基本门，1≤t≤k。 虽然一些作者假设量子电路只能使用有限数量的不同的单量子比特门[15]，但我们并没有这样假设，因为我们考虑了确切的设置。因此，本文中的复杂度类等于或大于仅考虑有限数量的不同单量子位门的论文中的复杂度类。然而，我们注意到，在我们的电路中使用的单量子比特门对于任何整数k≥0仅是Hadamard门H和Z（±π/2k）门，其中，对于任何θ∈R，.1H=0.021 11−1- 是的，Z（θ）=Σ1 00eiθ。M5H2222k=0√nn一nnnnx0x0X1x1x2x2X3x3020 00 00 0图1：用于准备的量子电路|当n = 4时， 阿达玛门旁边的门是四个量子位上的无界扇出门，其中顶部量子位是控制量子位。 门电路的R_e表示为“2“，即Z（π / 2 2）g。2.2H.E. R. R.E.R.D.S.P. A. O. R. R. D. D.D. R. D. D. DOR约简被描述为一个O（1）深度O（n log n）大小的量子电路，用于将计算OR n的问题精确地约简为计算OR m的问题，其中m = n log（n+1）n。我们解释这个想法在我们的电路中将使用该电路。 我们不能把ORNNDLT|xx=|x0分···|xn−1m−1是一个输入状态，其中xj∈ {0，1}。 该电路输出m量子比特状态H|在哪里？iπ|X||ϕk⟩ = |0 ⟩ + e22K |1⟩0≤k≤m− 1。如果|X|为|x0· · ·xn−1| = 0，H|k|对于任何0 ≤k≤m− 1，0为零，因此输出状态为|0毫米。 如果|X|≥ 1，存在0 ≤ a ≤ m − 1且b ≥ 0，使得|X|= 2 a（2 b +1）。 计算表明，H|a|因此，输出状态正交于|0毫米。因此，该电路精确地将计算ORn的问题简化为计算ORm的问题。 对于任意0 ≤ k ≤ m − 1，|量子电路的时间复杂度为O（1），时间复杂度为O（n）。1.一、通过使用无界扇出门，|可以并行地准备电路，因此用于OR简化的电路的深度和大小分别为O（1）和O（nm）= O（n log n）。3OR功能3.1指数规模电路对于任意满足fn（0n）= 0的布尔函数fn：{0， 1}n→ { 0， 1}，存在一个实数集{ra}a∈{0， 1}n\{0n}，使得fn（x）=Σa∈{0，1}n\{ 0n}raPAa（x）对于任何x∈ {0， 1}n。这是通过使用fn的傅里叶展开[19]，更准确地说，通过用奇偶函数PA组成的基替换fn的傅里叶展开中的傅里叶基来示出的特别地，ORn的以下表示可以通过使用ORn的傅立叶展开来获得。证明见附录A.1。引理1对任意x∈ { 0， 1}n， ORn1 Σ2n−1a∈{0，1}n\{ 0n}PA a（x）.ORn的表示意味着ORn的量子电路的时间复杂度为O（1）-depthO（n2n）-size。这个想法是，当输入x给定时，我们并行计算每个a的PAa（x），并准备状态（|0分（2- 1）+（−1）ORn（十）|1⟩⊗(2−1) ）/n二是基于代表性。 应用无界扇出门和阿达玛门的状态给出了所需的状态|或n（x）= 0。关键是，n = 0（）-n = 0（|一|由Hadamard门和一个无界量子电路组成的 P A a 量 子 电路如图2所示的扇出门[12]。（x）=6HHHHHHHHn一JnnJnnnPAa（x）n n nx0x0X1x1x2x2zzx0x1x2图2：PA3的量子电路 [12]。为了更精确地描述OR n的电路，令|xx = |x0分· · ·|xn−1是一个输入状态。电路描述如下：1. 请输入以下内容|x{\displaystylex{\displaystylex}}apN{\displaystylepN}将PAa的循环计算用于对va∈{0，1}n\{0n}进行运算与此同时，a∈{0，1}n\{0n} |PA n (x)⟩.2. 将Hadamard门和无界扇出门应用于双通道量子位（初始化为|0分）至2019- 02 - 22 00：00：00 00：00 |0（2n −1）+|1（2n −1））/2。3. 将受控-Z（π/2n−1）门与步骤1和2中的状态并行应用，以准备状态niπ1Σ|0⟩⊗(2−1)+ e2n−1a∈{0,1}n\{0n}n|1分（2−1） |0（2−1）+（−1）ORn（x）|1个月（2）−1）2=其中引理1暗示了等式。2002年，4. 对步骤3中的状态应用无界扇出门和Hadamard门，以准备所需的状态|或n（x）= 0。对于任意0≤j≤n− 1，设e（j）=e0· · ·en−1∈ { 0， 1}n，使得如果k=j，则ek= 1，否则为0。在第1步中，请输入|xx=|PAe（j）（x）是一种有效的方法，它能够有效地完成数据|PAa（x）=0a∈ {0，1}n，使得|一|≥ 2。 为了让各州同时做好准备，我们要求各州|x（2n−1−1），对于任何0 ≤ j ≤ n − 1。因此，在将电路应用于PA a之前，我们将无界扇出门应用于输入队列中，|xjand2n−1−1ancillaryqubitsforrevery0≤j≤n−1inparallel. 在Step2中，我们将无界扇出门应用于状态（H）中的辅助量子位|0分）|0（2n −2）。在步骤3中，我们使用状态中的量子位|PA a（x）作为受控-Z（π/2 n−1）门的控制量子位。在第4步中，我们将一个未绑定的数据集从Step3中删除，以确定是否存在2n−2个数据集，并我的天啊，我的天啊，我的天啊，|0n+（−1）ORn（x）|1分）/2。因此，该hadadgateut h es i d a tethesidate。By整个电路的结构、深度不依赖于n。由于步骤1是主要部分，并且在2n−1个量子位上使用n个无界扇出门，因此整个电路的大小为O（n2n）。这意味着下面的引理。证明的细节见附录A.2。引理2存在一个O（1）-深度O（n2 n）-大小的量子电路（或n）.注：Hoban等人考虑了基于测量的量子计算的限制模型，其中测量的自适应性被移除[14]。他们表明，如果我们允许在步骤2中使用（2n−1）量子比特态，则任何布尔函数fn都可以在模型中通过基于上述fn表示的过程精确计算。引理2中的电路可以被认为是模型中计算ORn的过程的模拟无界扇出门主要用于准备（2n− 1）量子比特态和计算PAa。3.2定理1我们将介绍如何1使用H.R.Y和S.P.A. L. Let|xx=|x0分···|xn−1成为一个输入状态。 电路描述如下：7Fk=0FFFFFnnnnnnnnnFFFFFFFFFk=0nk=0nnffn1. ANpplyHyerandS palek的O R e t u c t e|x必须执行m-qubit statem−1H|其中m = log（n +1）。2. 将引理2中的电路应用于步骤1中的状态，以准备所需的状态|或n（x）= 0。由于步骤1精确地将计算ORn的问题简化为计算深度为O（1）且大小为O（nlogn）的ORm的问题由于步骤2的输入大小是m，所以步骤2中的电路的深度和大小分别为O（1）和O（m2m）=O（nlogn）。因此，整个电路的深度和大小分别为O（1）和O（nlogn）这就完成了证明。定理1直接意味着ORn在QNC0中，因此以下关系成立：推论1 QNC0 = QAC0。由于QAC0=QTC0[15]，因此QNC0=QAC0 =QTC0。 推论1和关系QAC0=QTC0直接意味着对于任何整数，QNCk=QACk和QACk=QTCkf f f f f fk≥0，其中QNCk、QACk和QTCk分别与QNC0、QAC0和QTC0类似地定义只不过他们处理的是O（logkn）深度的电路，而不是O（1）深度的电路。因此，更一般地，对于任何整数k≥0，QNCk =QACk=QTCk成立对于任意的整数常数c≥1，定理1中的电路规模可以在不渐近增加深度的情况下减少到O（nlog（c）n），其中log（c）n是c次重对数log ···logn.为了证明这一点，我们将n个输入量子位分成n/logn个logn量子位的块对于每个块，我们应用定理1中的电路来计算ORlogn。我们获得n/logn个输出量子位，并再次将电路应用于输出量子位以计算ORn/logn，这产生了所需的输出。深度和大小的时间复杂度分别为O（1）和O（nlog（2）n）使用得到的电路，我们重复这个尺寸减小过程。在c−1次重复之后，我们得到一个O（nlog（c）n）大小的电路。ORn的电路产生EXt的电路[15]。要构建电路，只需准备Z（−tπ/2k）|Pa kakkakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakaka kakakakakaka kakakaka kakakaka kakakaka kakakaka kakakak|在Hubyerr和S.P. A.lek的O R e d i nt定理1中的电路。这是通过对每一个0≤k≤m− 1增加一个Z（−tπ/ 2k）门和一个NOT门来实现的。 因此，所得电路的深度和大小与图1中的深度和大小渐近相同。定理1.这就产生了一个O（1）-深度O（nlogn）-大小的量子电路，0≤t≤n。4阈值功能首先，我们在EXk的等深电路的基础上，给出了THt的上面描述然后，我们描述了另一种用于THt计数功能的恒深电路。接下来，我们结合这两个电路来证明定理2。基于一个电路，4.1基于正合函数和计数函数的电路我们首先考虑THt的常深度回路，它是基于1 ≤ t ≤n/2 λ时EX k的回路。让|xx = |x0分· · ·|xn−1是一个输入状态。 电路描述如下：1. 请输入以下内容|x和NaplyhecircuitforEXktoachopyforvery0≤k≤t−1innparallel准备状态t-1|EX k（x）2. PAT和NT|t−1 EX k(x) ⊕ 1⟩.如果|X| ≥t，EX k（x）= 0，对于每一个0 ≤k≤t− 1。如果|X|5为安全素数，即，一个素数，其形式为q= 2 p + 1，其中某个素数p>2。在下文中，与密码学文献中一样，我们假设存在无穷多个安全素数。LetGq=（Z/qZ）n，则在l o q上的fggrsm的多个特征向量。我不知道你为什么要这么做0 1q−2q−1G的生成元1

下载后可阅读完整内容，剩余1页未读，立即下载