矩阵积和式逼近困难性的研究进展：结构化矩阵类求模素数p的积和式近似与计算困难.

1关于结构矩阵积和式逼近的困难性布鲁诺·科德诺蒂Istituto di Informati a e Telemati a，CNR and智前奥代诺蒂山nr.it伊戈尔·E. 什帕林斯基澳大利亚新南威尔士州悉尼马奎里大学计算机系，邮编igor i s.mq.edu.au阿恩·温特霍夫新加坡国立大学淡马锡实验室10 Kent Ridge Cres ent，Singapore 119260，Singaporetslwa nus.edu.sgAbstra t我们证明了对于几种自然的结构化矩阵类，如齐次矩阵、幂次矩阵、Hankel矩阵和Toeplitz矩阵，求模素数p的积和式的近似值与计算其Exa t值一样困难.这类结果是众所周知的任意矩阵。然而，所使用的技术似乎并不适用于结构化的”材料“。我们的方法是基于Boneh和Venkatesan在1996年提出的隐数问题的最新进展，并结合了一些由Waring问题启发的指数和的界.2i;j=1XY1介绍给定矩阵X =（xij）n在环上，我们用per X表示它的积式，也就是说，nint X =xi（i）;2Sni=1其中Sn表示在f 1上的群A;：;n g。永久物在计算机和电脑界引起了很大的注意.众所周知，除非一个非常强大的复杂性，真的是假的，永久的是很难计算的。从技术上讲，这是一个完全的过程。在许多文献中，我们考虑了积和式的各种可逼近性和不可逼近性，也考虑了一些随机算法。 特别地，Cai等人[8]已经证明，随机多项式时间算法即使在很小的实例部分上也不能正确地计算永久式，除非PP=BP P。所有这一切都表明，类BPP是计算非确定性多项式时间图灵机（见[32，33，34]）中的epting计算次数的函数类，而类BPP是概率计算（有界误差）的类P的类似物。上述不可逼近性结果适用于任意矩阵，并利用了矩阵的随机自约性（见[8，14，23]及其中的参考文献）.这一结果应与随机多项式时间近似相比较s血红素，这适用于具有非负项的矩阵[17]。另一方面，尽管对结构矩阵的积和式有各种各样的结果，但对结构积和式的计算复杂性知之甚少，除了非常特殊的情形[3，10，11]。在这里，我们提出了一种替代方法，获得 非线性不可逼近性的结果es，证明了近似与外推之间的一个关系， 矩阵，更一般地，对于所有在S次乘法下丢失的矩阵的损失。更多关于这些矩阵和其他有趣的矩阵族的信息，在S/S乘法下迷失，读者鼓起勇气看到[27]。3i;j=1我们都知道一个方阵X =（xij）n是一个汉克尔矩阵，如果循环矩阵是一类Toeplitz矩阵，它的元素xij只依赖于ij（modn）.对于这类矩阵，如果p是p个元素，其中p是素数，我们证明了，如果计算的永久是困难的，那么近似的永久也是困难的。如果PERMn;表示一个环，其中给定一个在S乘下丢失的族中的IF p上的矩阵X，输出对每个X的一个近似，则我们证明了存在一个有效的概率算法，它使PE R M n;多项式地几乎等于P ERMn;并且以高概率正确地估计每个X。这种简化适用于对每X的相当粗略的近似。这种方法当然也适用于一般矩阵，尽管在这种情况下[14]的定理1.7和1.9给出了更强的结果。然而，证明方法不适用于结构矩阵。事实上，在[14]的定理5.2的证明中描述的变换并不保持结构性质为双线性或Toeplitz。我们的方法利用了隐藏数的优点问题，Boneh和Venkatesan介绍的问题[4，5]。[4，5]的方法（基于Latti约简算法）与指数和技术相结合，在密码学和复杂性理论中产生了许多结果[13，15，16，21，25，26，28，29，30，31]。在这里，我们表明，上述两个elebrated技术的组合，Latti约化和指数和的界，并应用于研究积和式。对于整数s和p 1，我们用bsp表示 s除以p的余数.对于整数p和实数> 0，我们用APPROX;p（t）表示满足不等式pJBTPuj2+ 1：（1）因此，粗略地说，如果是一个整数，那么近似;p（t）是一个具有大约最重要的位与BTP相同。 然而，这一定义更灵活，更适合我们的目的。 我们特别注意到，的在不等式（1）中，不需要是整数。4ppp我们还假设，如果p的元素存在，则我们可以将APPROX;p应用于IFp的元素。使用上述符号，我们可以将隐藏数问题公式化如下：设2 IFp.假设我们有一个值APPROX;p（t），对于一些> 0并且对于许多已知的随机值t2IF，You’你超过了这个数字。<在[4]中，给出了一个多项式时间算法，其中对log 1=2 p进行了修改。然而，对于许多应用来说，从IF中随机选择t的性质太有限制，见[13，15，16，21，25，26，28，29，30，31]。 对于这些应用，人们必须研究当t从IFp中的某个元素序列T中随机选取时的情况。上述结果表明，T的分布性质的均匀性起着决定性的作用，从而将指数和引入到问题中。然而，对于某些序列，例如，对于非常小的乘法子群的IF suh均匀性结果是不可用的。 处理这个在文献[31]中，提出了一种改进的基本算法，将序列T替换为该序列的所有元素的k-和的序列。这种变化通常将分布特性的均匀性放大到所需的水平。在[31]中，这种方法已被应用于证明Diabete-Hellman血红素的一个比特安全性结果.这里我们用同样的方法来研究永久物。在整个文件中，log x始终表示x的二进制对数>0中的常数，在明显的情况下，可能依赖于一个小的正参数，否则是绝对的。我们总是假设p是一个素数，p为5，因此表达式log log p和log loglog p被定义（并且是正的）。知识：作者要感谢蔡金义的兴趣和有益的评论。第二位作者部分得到ARC基金DP0211459的资助第三作者部分得到了DSTA赠款R-394-000-011-422的支持5=零“的ppN有限域上的2-隐数问题和Waring我们都是一个序列的disrepan y D（）=（！ ）N个元素中的N个区间[0; 1]的定义为：D（）=supA（J; N）jJj;J[0;1]其中上确界在[0; 1]的所有子区间J上扩展，jJj是J的长度，A（J; N）表示点的数目！以J为单位，对于0 N1. 为了我们的目的，我们还需要以下定义。 我们说如果p的元素的有限序列T是-均匀分布模p if for any a 2 IF the disrepan y of the sequen e bat =p.为至多我们的主要工具是下面的陈述，其中h是[25]的引理4（并且h是[4]的定理1的推广）。引理1. 让！> 0是一个任意的绝对常数。对于质数p，de ne-&-log p log log log p1=2log log p和d =3 log p：设T是2-齐次分布模p整数序列.存在一个概率多项式时间算法A，使得对于任意2 IFp，给定素数p，d个整数t1;：;td，和d个整数i= APPROX;p（i）;i = 1;：; d;对于足够大的p，其输出满足Pr [A（p; t1;：; td; u1;：; ud）=℄1个p1;其中，概率是从IFp的元素中随机地均匀且独立地在所有t1，t2，t3，t4上以及在算法A的所有随机hoi上获得的。t2T6n+：+nt（mod p）;1;：;k 2 IF：对于任意整数n，对于实数z和整数m，我们使用以下符号em（z）= exp（2 iz=m）：因此，我们看到，为了使用引理1，我们需要建立序列T的分布性质的某种均匀性，这自然会导致估计序列元素的指数和的问题。 T.根据[18]的定理1，我们有下面的界，也见[9，19，20]。引理2. 对于任何1 >“> 0，存在一个 永恒的 （“）> 0表示，任意整数n，结合的p（log log p）1“nlog PMax Xepp（an）p 1（“）保持。g d（a;p）=12如果（log p）1+”不幸的是，引理2的界太弱而不能直接应用然而，我们将其应用于IFp的元素的n次幂的k-和。对于整数k; n 1和元素t2，如果p，我们用Nk;n;p（t）表示方程的解的个数1千磅确定k的最小可能值的问题，对于该最小可能值，上格林e（或在更传统的设置中，关于ZZ的orresponding方程）对于任何t都有解，该问题被称为华林问题。然而，对于我们的目的来说，仅仅是可解性是不够的。相反，我们需要解的个数的渐近公式。我们证明引理2可以用来证明，对于合理的小，k，Nk;n;p（t）失去其期望值。引理3. 对于任何1>“> 0，存在常数C（“）> 0，p（log log p）1“nlog P7ppxe（au）=0;如果u60（modp）;p1KXep（at）Xep（ann）A1;：;2IF=零结合的maxNk;n;p（p1）k（t）（p （1）kt2IFpp p2对任意整数k C（“）（log p）2+”和足够大的p成立。众所周知的身份（例如，见[22，第5.1章]）p 1意味着pa=0p;如果u0（mod p）;p 1Nk;n;p（t）= XXep（a（n+：+nt））1千磅p 11p a=02IFp分离项（p1）k=p，对应于a = 0，并将引理2应用于其他项，我们得到最大Nk;n;p（p1）k（t）（p1）k1 +1K 11（“）t2IFppp 1（log p）1+”假设对于2如果一个整数n1我们被给予一个奥拉勒对于每2个IF，它返回APPROX;p（n）。引理4. 设# > 0是一个任意的绝对常数，=#log p log log plog log p1个=2个：存在一个多项式时间的概率算法，对于任何1 >“>0和任意整数n，p（log log p）1“nlog PKK=：然后得到想要的结果。018使得O（1（logp）3+”）所有的orle HNPn; ;p，然后以至少1 + O 2=2的概率进行重排。9pj u j p=2$ppppHJpK证据 从引理3中取C（“），2+”1k = C（“）（log p））;= 2 =3; d = 3log p：然后由引理3，T =（n+：+n）1;：;k 2 IFp）1 KIF的n次幂元素的k-和的模p是2-均匀分布的.现在我们在随机域上一致独立地求出了dk的oral HNPn;p11;：;1k;：;d1;：;dk2 IFp并得到整数uhj，nhjphj对于h = 1; 2;：; d，我们将+1个 ; h = 1;：; d;j= 1;：; k：Kvh =Xn;th =j=1Xn%HJj=1K;uh=Xuhj;j=1（其中我们使用Z上的加法）。注意，对于足够大的p，拉克什uh j kp=2+ 1p=2+ 1：下一个是vH乌赫bvhp + buhp = p， 2f1; 0; 1g：如果= 1，则有bvh布河+ p =0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000uh j p=2+ 1其中h仅在bvhp> p p=2+ 1时才是可能的。 If =1然后我们有buhbvh + p =h uh j p=2+ 1其中h仅在bvhp =2+ 1时才是可能的。 如果= 0，则有p10公司简介 布河pj = jbvhp 布河 pj =100h乌赫日本：2+ 1根据引理3， 的 p=2+ 1的概率BV HPp p=2+ 1，对于所有h = 1;：;d是1 + O（d2）。现在引理1的算法产生奥雷特概率至少为1 + O（d2+ p1 ）= 1 + O2=2个如果p是非常大。ut11i;j=1pi;j=1“的p我们说一个n n矩阵类Mn的元素来自IFp，它是丢失的3主要结果在这一节中，我们利用隐数问题的优点来证明我们的主要结果。粗略地说，我们证明了对属于一类在s乘下丢失的矩阵的积和式的逼近与计算一样困难。然后，利用一般矩阵的性质难以计算的已知事实（除非P∈P=BPP），证明了一般矩阵的一个硬度结果.在下文中，我们给出了一些定义，并陈述和证明了这些结果。在s-乘法下，如果对任意X =（xij）n2Mn且任意2如果我们也有X=（xij）n2Mn.设PERMn是一个给定X2Mn，输出近似p（X）的方程.定理5. 设# > 0和“> 0为任意常量。则对任意一类矩阵，若M n在IFp上的s阶乘法Mnnlog P存在一个在n和log p中以时间多项式运行的probabilisti算法，该算法对任何X2 Mn都使得多项式地多个all到orlePERMn;其中=#log p log log log p1=2log log p并对每个X进行评估 或者至少有1 + O 2的概率 =2。证据给定X 2 Mn，让我们随机均匀地选择2 IF，计算X，并使用具有输入X的OrlePERMn;k来评估APPROX;p（per X）= APPROX;p（nper X）：通过引理4，重复这个过程O（1（log p）3+”）次，我们得到了想要的结果。utp（log logp）1“12“的推论6. 对于任何常量A> 0和A1存在常数C> 0仅取决于A和A，因此以下陈述成立。如果对于某个常数# > 0，存在一个概率多项式时间算法，当失效概率呈指数级小时，a得到 近 似p（每S），其中=#log p log log log p1=2log log p对于区间[Q;2Q]上的n阶n阶矩阵S的积和式，至少有<$QlogAQ素数p，其中某个Q满足QC n logA n and log Q = nO（1）并对其他素数返回一个er r或消息，则PP=BP P。证据我们证明了上述算法可以转化为一个概率算法来计算n个二进制矩阵（即具有0;1-e n次尝试的矩阵）的积和式. 后一个问题是NP完全的，由简单的简化可得，将任意n n个二元矩阵X映射到2n 2n × n矩阵上0个XXT 0;其积式是X的积式的平方，每S =（每X）2。给定任意n × n二进制矩阵S，显然0每秒n！ 让我们设置`=n log nlog Q在定理的条件下，设[Q;2Q]中有素数，且存在算法A。我们可以迭代地建立一个suh素数的集合L，方法是在整数[Q;2]中选择随机的整数，并通过[1]的算法测试它们的素数（也可以使用多项式时间概率素数测试中的任何一种，参见[2，12]），然后确定它们是否已经在列表中，以及它们是否是suh算法A对它们有效。我们注意到，由于Q上的条件为“0：5QlogAQ对于适当的软管常数C > 0。 因此，在每一步，我们S =13Y2Sni=1具有至少为0：5的“合适的”素数。因此每一步只需要（log Q）O（1）= nO（1）的二进制运算。我们还看到eahp2L满足n = O（Qlog1Q）= O（plog1p），因此定理5适用。因此，近似算法A可以转化为概率算法，以计算eahp2的bperSpL. 因此，利用中国剩余定理，在时间多项式中，和log Q，因此在n中，我们 一个 每S模计算p > Q`你好！每秒p2L然后， 得出每S的实际值。本文接着应用Cai等人的一个结果[8]，他们证明了概率算法的收敛性奥雷泰莱 对所有输入即不完全塌陷P_（？）P=BP_P。4备注注意，虽然传统的测度是n2logp，但有些矩阵可以有更短的描述.例如，每行只有s个非零项的s-稀疏迭代矩阵可以仅由O（s lognp）位来描述对于这样的矩阵，指定s对（m; x），=1;：; s就足够了，其中m，1 m n，是第一行中第n个非零项x 2 IFp的位置。在这种情况下，若定理5的算法满足这样的条件，则定理5的算法是slog np中的多项式利用这种设置，我们也可以考虑定理5对于行列式的类似情形.实际上，尽管行列式对于稠密矩阵是一个简单的函数，但对于s-稀疏矩阵是否也能成立就不清楚了在s log np中以时间多项式计算此外，一个类似于Theo-rem 5及其对具有“短描述”的矩阵的修改适用于更广泛的一类矩阵函数，称为内禀函数，其复杂性已被研究，例如，[6，7]。内在性是表达式nimmX=X（）Yxi;（i）;形式14哪里：S n！C是一个不可缺少的 hara ter的群Sn. 的琐碎 哈拉特尔 （）= 1对应于永久，交替哈拉特尔（）=符号或对应于行列式。 因为任何在我们有imm X =n imm X时，定理5的结果对imm X成立，而不是仅对每个X成立，没有任何其他的条件。我们的方法也可用于证明其他几种多项式函数模逼近的困难性，如yle格式多项式和因子多项式（见[7]第3.3节）。最后，我们该技巧适用于矩阵F（X）=mF（X）且具有某个整数m1（仅取决于X的维数n）的任何函数F。雷费伦[1分] Agrawal，N. Kayal和N. Saxena，'PRIMES是在P'，预印本，2002年，1{9。[2] E.李文，李文生，李文生，1996。[3]伯纳斯奥尼湾Codenotti，V. Crespi和G.一个人走得计算变量矩阵的积和？线性代数及其应用292（1999），15{37.[4]D。Boneh和R.Venkatesan，“在Diesie中计算最重要的密钥位的难度{Hellman和相关的s hemes '，Le t。对比中的注释S i.，Springer-Verlag，Berlin，1109（1996），129{142.[5] D。Boneh和R. Venkatesan，“在Latti es和其rypto- graphi appli ations的 舍 入 ” ， Pro 。第 八 届 ACM-SIAM 学 术 年 会 在 迪 斯 河 算 法 ，ACM，NY，1997，675{681.[6 页。 Burgisser ， `immana nts 的 计 算 复 杂 性 ' ， SIAMJ.比 较 ， 30（2000），1023{1040.[7页。Burgisser，代数复杂性中的完备性和保留，Springer-Verlag，Berlin，2000。[8] Y. Cai，A.Pavan和D.Sivakumar，“关于永久的硬度”，Le t。对比中 的 注 释 S i. ， Springer-Verlag ， Berlin ， 1563 （ 1999 ） ，90{99.15[9分] 科赫拉内角Pinner和J.Rosenhouse，“指数和的界限和多项式Waring问题mod p”，Pro。Lond.数学。所以。(to出现）。[10 B. Codenotti和G. Resta，“关于某些干扰物质的永久性”，Algebraiombinatori s and computer s ien e，Springer{Italia，Milan，2001，513{532.[11 B. Codenotti和G. Resta，“通过行列式计算稀疏波动性常数”，线性代数及其应用，355（2002），15{ 34.[12 你 好 Crandall 和 C. Pomeran e ， Prime numbers ： A ComputationalPerspective，Springer-Verlag，Berlin，2001.[13谢谢El Mahassni，P. Q.阮和我。E. Shparlinski，“Nyberg的内在性{Rueppel和其他具有部分已知不存在的DSA样签名S hemes '，Le t.在Comp.S.1.中的注释，Springer-Verlag，柏林，2146（2001），97{109.[14你好。Feige和C. Lund，“关于计算随机矩阵的永久性的困难”，Comp. Compl.，6（1996/1997），101{132。[15你好。I.我和冈萨雷斯。E. Shparlinski，“在安全性的Diesie {赫尔曼比特'，临。密码学与计算数论研讨会，新加坡1999，Birkhauser，2001，257{268.[16你好。I.我和冈萨雷斯。E. Shparlinski，“安全性的最显着位的沙米尔消息传递的血红素”，数学。比较，71（2002），333{342.高斯和[17你好。Jerrum，A. Sin lair和E. Vigoda，“一个多项式时间算法的永久性矩阵与非负entries”，电子troni Colloq。上Comp.Compl.，特里尔大学，TR 2000 -079（2000），1{22.[18你好。诉Konyagin，“关于高斯和的估计和模素数的Waring Inst. A广告。 Nauk苏联，莫斯科，198（1992年），111{124（在俄罗斯）;翻译临。斯捷克洛夫研究所数学、1（1994），105{117.16[19你好。诉Konyagin，“子群和高斯和上的指数和的界”，预印本，2002年，1{25（俄文）。[20你好。科尼亚金和我。张文，张文，等.指数函数的特征和及其应用.北京：清华大学出版社，1999.[21] C. W. Li，M. N阿斯伦德和我E. Shparlinski，“XTR和LUC的传输和位安全性的隐藏问题”，Le t.在Comp.S.1.中的注释，Springer-Verlag，Berlin，2442（2002），433{448.[22你好Lidl和H. Niederreiter，Finields，Cambridge University Press，Cambridge，1997.[23你好Linial，A. Samorodinski和A. Wigderson，“矩阵排序和近似永久式的一个确定性强多项式算法”，Pro. 第30届ACM研讨会在比较理论中，（1998），644{652.[24你好闵，《数学百科全书及其应用》，艾迪生·韦斯利，1982年。[25 P. Q.阮和我。E. Shparlinski，“具有部分已知不确定性的数字签名算法的安全性”，J. Cryptology，15（2002），151{176}。[26 P. Q.阮和我。E. Shparlinski，“部分未知数的椭圆曲线数字签名算法的安全性”，设计，代码和密码学，（即将出版）。[27张文，等，2001.[28我是。E. Shparlinski，“稀疏多项式近似在nite elds”，Pro。第33届ACM 研 讨 会 关 于 计 算 理 论 ， Crete ， Gree ， July 6-8 ， 2001 ，209{215.[29我是。E. Shparlinski，“关于XTR的广义隐藏数问题和位安全性”，Le t 。 对 比 中 的 注 释 S i. ， Springer-Verlag ， Berlin ， 2227（2001），268{277.[30] E. Shparlinski，'Se uri tyofmostsigni a ntbitsofgx2'，Inform. P ro。Letters，83（2002），109{113.17[31我是。E. Shparlinski和A. Winterhof，“小子群中的隐藏数问题”，Cryptology ePrint Ar hive，Report 2003/049，2003，1{12.[32我的天G. Valiant，“代数中的完备性缺失”，Pro 11th ACM Symp。在计算理论上，1979年，第249页。[33我的天G. Valiant，“枚举和可靠性问题的复杂性”，SIAM J.COMPUT。8（1979），410{421.[34我的天G. Valiant，“计算恒量的复杂性”，理论。Comput. S岛8（1979），189{201.