[数学建模类精品]一类特殊多项式系统的结式矩阵

毕业论文专业数学与应用数学班级学号学生姓名指导教师讲师二八年六月一类特殊多项式系统的结式矩阵THERESULTANTMATRIXFORASPECIALPOLYNOMIALSYSTEM专业班级学生姓名指导教师讲师系别数理与信息科学系2008年6月A1A2A0A3A4A5A6A7A8A9A10A11A12A13A14A15A16A18A17A19A20A21A23A24A22A25A26A27A4A28A29A18A30A31A23A13A14A32A33A34摘要本文是研究一类特殊多项式系统的结式矩阵。主要证明了从双次数矩形支集,MNA的4个角上分别切去4个矩形子支集时，A结式DIXON矩阵公式仍然成立。首先给出了一些基本的概念和3个双次数多项式的DIXON矩阵；然后把论文的主要结论以定理的形式正式给出，定理的证明分为3部分第一部分证明了当,MNA角上切去的矩形子支集中的单项式系数为0时，,MND相应的行与列为0；第二部分证明了去掉,MND的零行与零列之后，剩下的矩阵为方阵且它的元素仍是DIXON系数矩阵中的元素，这样就得到的,MND子矩阵就是AD；第三部分证明了0AD，且它与A结式有相同的阶数，因此AD就是多项式支集为A的,FGH的A结式；最后通过例子验证这些结论。关键词DIXON矩阵；多项式支集；A结式ABSTRACTTHISPAPERSTUDIESTHERESULTANTFORASPECIALPOLYNOMIALSYSTEMITPROVETHATTHEDIXONMATRIXFORMULATIONFORARESULTANTSSURVIVESWHENFOURCORNERRECTANGULARSUBSUPPORTSARECUTOFFFROMTHEBIDEGREERECTANGULARSUPPORT,MNAFIRST,ITHASDEFINEDSOMENOTATIONSANDTERMINOLOGIESANDPRESENTEDTHEDIXONRESULTANTFORMULATIONFORTHREEBIDEGREEPOLYNOMIALSINTWOVARIABLESTHENITSTATESTHEMAINRESULTOFTHEPAPERFORMALLYASATHEOREMTHEPROOFOFTHETHEOREMISDIVIDEDINTOTHREEPARTSPART1IDENTIFIESTHEZEROROWSANDCOLUMNSOFTHEDIXONCOEFFICIENTMATRIXPART2ENSURESTHATTHEREQUIREDNUMBEROFNONZEROROWSANDCOLUMNSREMAININTHEDIXONCOEFFICIENTMATRIXPART3ASSERTSTHATTHEDETERMINANTOFADISNONZEROANDHASTHERIGHTDEGREE,THUSITISTHEARESULTANTFOR,FGHWHOSEMONOMIALSUPPORTISALAST,ITILLUSTRATESTHEVARIOUSRESULTSWITHEXAMPLESKEYWORDSDIXONMATRIXMONOMIALSUPPORTARESULTANT目录绪论11预备知识311312矩阵与行列式313多项式32经典双次数DIXON结式53DIXONA结式74矩形切角引起的零行和零列941因式分解定理942矩形的右上切角问题943矩形的左上切角问题1144矩形的左下切角问题1145矩形的右下切角问题125经矩形切角后,MND的非零子矩阵1351括号的行支集和列支集1352AD的非零行与非零列146DIXON矩阵的行列式就是A结式177举例说明188结论219参考文献22致谢24翻译原文25中文翻译31A35A36A37A38A39A40A41A42A43A44A44A45A46A47A48A49A50A51A52A53A54绪论结式方法是消去法中的一种重要工具，在G1207数G1972G1321G451G14270G2172G1972G1321定理证明G451G38G36DG18G38G36G48G451G38G36G42DG451G16757G12651G7438G1207数G451G16757G12651G7438G16282G16285G451G7438G3132G1166和G15406G6323G10628G4466中有G11540G5203G8879G13792G9157G17840的应G11004。G6164G16871的结式，就是一个多项式，它G11013G2419多项式系统的系数G6164G7512成，它G12573G1122零的G1817分G5529要G7477G1226是G2419多项式系统G4396在公G1861G7693。正因G3926此，结式方法的G1260G5334，G19512了它的G5567G17907消元G14033G2159之G3818，G17836在G1122它G14033G2040定一个多项式系统是G2554有解。有了这个工具，G6117G1216就G2499以在G8726解之G2081先G2040定这个多项式系统是G2554有解，G13792G993G1262G11908到G13475过数G3837的G16757G12651之后，结G7536G7092解的G5785G1929出G10628G15G6164以结式G4557G1122解多项式方G12255G13464G1075是一个G5468有G6940的工具。G11013G1122多项式的支集与结式有G11540G4506切的G1863系，因此研究支集的G13582G3845G5785G1929G2029G4557结式矩阵最后的G16280G8181有G11540重要的G5859G1053，G1866中切角问题G11G70OG85NG72G85G70G88G87G87ING74G12G15999G16760为是最G1863G19202的问题。在多项式的支集G7512成的G10287G20051多G19766G1319中，G1881部G9869的G13582G3845G11G4557应G11540G7588些单项式在多项式中的G13582G3845G12G993G1262G5445G2721G6984个DIXON结式矩阵的G3835G4579和G3867G5334G5627，G1306是G1262G5445G2721G6164G4557应的G7366G19766的次数，G13792G1313G1122G3247个角的G9869的G13582G3845，G2029G1262G5445G2721结式矩阵的G3835G4579G451G17876G2282G5627G12573问题。在这方G19766，G38G75IONG75证明了G4557G1122非G9163G2524双G2476元多项式系统，G3926G7536G1313G1122G3247个角的G13582G3845部分为矩形，G1075就是G6164G16871的G85G72G70G87G68NG74G88G79G68G85G70OG85NG72G85G70G88G87G87ING74的G5785G1929下，DIXON结式矩阵G993G1262G1147G10995多G1325因子。以G5460，1N个N元多项式方G12255G13464的结式是一个多项式方G12255，此方G12255G13464的系数满足多项式方G12255当且仅当此方G12255G13464在N维射G5445空间中有解。这样一个结式G2499以表示为一个G48G68G70G68G88G79G68Y商式，G1306是G4557G1122特殊G5785G1929有更好的方法。G4557G11221N个N元线G5627方G12255，1N阶系数矩阵的行列式是结式。G4557G11222个一元方G12255，它的结式G2499以通过SYG79VG72SG87G72G85G11西尔维斯特G12法或BG72ZOG88G87G11贝祖G12法G8726得。G13475典结式考虑总次数G993超过一个特定值的G6164有单项式；G13792A结式考虑的是G7512成多项式的单项式。DIXONG7512造了3个二元方G12255的一个结式他是通过把G38G68YG79G72Y多项式1FSGSSFG扩展为DIXON多项式,1,FSTGSTHSTFTGTHTSTFGH，G1866中G38G68YG79G72Y多项式考虑的是两个一元多项式FS，GS，G13792DIXON多项式考虑的是3个G1863G1122S，T的双次数多项式,FST，,GST，,HST。然G13792G38G68YG79G72Y多项式的系数矩阵给出一个G1863G1122总次数G7512形的G13475典结式，DIXON多项式的系数矩阵给出G1863G1122双次数G7512形的A结式。事G4466上，G2499以通过从一个总次数为MN的多项式中去掉G7588些适当的单项式，G13792得到一个双次数为,MN的多项式。EWG38G75IONG75讨论了DIXON结式矩阵中项的表达式，有了这个公式，G993G11004G16757G12651G6984个DIXON矩阵，就G2499以知道G7588个G1313置A55A56A57A58A59A60A61A62A63A64A64A65A66A67A68A69A70A71A72A73A63的项是什么。在文献5中另G3818一种公式G1075G2499以G8726出DIXON结式矩阵中的项，该公式G16757G12651简单，并且G2499以证明DIXON结式矩阵中的一些G5627质。1908年G36LDIXON综G2524G2081G1166的结G7536，G4557G11013三个双G2476元多项式G7512成的多项式系统给出了三种结式的G7512造方法，分别是基G1122SYG79VG72SG87G72G85与G38G68YG79G72Y的方法，以及两者的G9163G2524方法。G11013G1122双G2476元多项式系统有更G4466际的背景，因此G4557相应的DIXON结式矩阵的研究G1075G5468多。本文主要基G1122G38G68YG79G72YQG88OG87IG72NG87方法，G8726多项式的支集为A的3个双次数多项式的DIXON结式矩阵，以及在G85G72G70G87G68NG74G88G79G68G85G70OG85NG72G85G70G88G87G87ING74的G5785G1929下，G8726解并讨论A结式。论文首先G7693据论文需要给出了一些基本的概念G451术语；第2节给出了和双次数多项式,FGH的DIXON结式矩阵AD的定G1053，并且给出DIXON结式矩阵中项的表达式；第3节把论文的主要结论以定理的形式正式给出G15这就是论文的核心部分G11定理31G12，这个定理G1861有三个结论，因此接下来G6117G1216将定理的证明分为三个部分第4节证明了DIXON系数矩阵的零行和零列，即当从,FGH的多项式支集,MNAG3247个角上分别切去G3247个矩形子支集1234,SSSS时，AD的行支集AR和列支集ACG1075是G4557应的从G1866支集,MNRG451,MNC的G3247个角上切去形状相同的G3247个矩形子支集G11在这里，从,MNRG451,MNC切去的子支集与IS的形状完全相同，只是在G1313置上有一个平移G12，G11013G1122G45571234,IJSSSSUUU，有,0IJIJIJABC，因此,MND中G4557应的行与列均为0；第5节证明了去掉,MND的N个零行与N个零列之后G11G1866中1234NSSSSG12，剩下的矩阵AD是个方阵且它的每个向量均非零；第6节证明0AD，且AD的次数与A结式的次数相G12573，因此AD就是G6117G1216G6164要的A结式。第7节通过一个例子将定理31的G1881容进行了验证。A74A75A76A77A78A79A80A81A82A83A83A84A85A86A87A88A89A90A91A92A931预备知识这节给出的一些术语和概念与第2节定G1053的DIXON公式G4506切相G1863。11集合定义11G6984数的集G2524记为。集G2524S的基数记为S。定义12令2个集G2524的差为|ABXAXB。G3926G7536BA，从A中去掉B就得到AB；并且记11NNIIABBABU定义13G3926G7536,AB，S，G2029,|,ABSXAYBXYS。G4557,AB，A到B的连续的G6984数集记为|ABXAXB，且若AB，G2029AB定义14G3926G7536,ABCD，两个连续的G6984数集的笛卡尔积记为,|,ABCDXYAXBCYD，且若AB或CD，G2029ABCD12矩阵与行列式一个方阵M的行列式为M矩阵的零行（或列）是指这个行（或列）的元素的值全为013多项式,FST称为G1863G1122G2476量,ST双次数为,MN的多项式，G3926G7536FG1863G1122,ST的次数分别为,MN即,00,MNIJIJIJFSTAST,FST的多项式支集是指F的单项式指数向量,IJ的集G2524G11G1866中IJST是F的一个单项式G12，G1075就是说,IJIJAST是F的一项（若,0IJA）G3926G7536一个一般的多项式FG1863G1122,ST的双次数为,MN，那么它的多项式支集记为,00MNAMNG1111G12G5468显然，,MNA是,IJ平G19766上的一个矩形G9869列。,FST的多项式支集的凸包称为F的G10287G20051多G19766G1319。例G392643,00,IJIJIJFSTAST，它的多项式支集和G10287G20051多G19766G1319G3926图11G6164示。A94A95A96A97A98A99A100A101A102A103A103A104A105A106A107A108A109A110A111A112A113图11双次数为4,3的多项式F的多项式支集与G10287G20051多G19766G1319G4557G11223个一般的双次数多项式，,000000,MNMNMNIJIJIJIJIJIJIJIJIJFSTASTGSTBSTHSTCST，G1112G12定G1053,IJIJIJKLKLKLPQPQPQABCIJKLPQABCABC，称此3阶行列式为括号在G993致引起G9163淆的G5785G1929下，为了节省空间，简记,IJKLPQIJKLPQ例G39260,00,00,01,01,01,00,10,10,10010010,01,00,1ABCABCABCA94A95A96A97A98A99A100A101A102A103A103A104A105A106A107A108A109A110A111A112A1142经典双次数DIXON结式在这节中，主要介绍3个二元多项式方G12255的G13475典DIXON结式的G7512造过G12255。设3个多项式,000000,MNMNMNIJIJIJIJIJIJIJIJIJFSTASTGSTBSTHSTCST，G1121G12G1866中,|0IJIJIJAIJABC为,FGH的多项式支集，显然,MNAA下G19766G6117G1216就给出,FGH的DIXON多项式的定G1053定义21,1,AFSTGSTHSTFSTGTHFTGTHTSTFGHG1122G12当S或T时A的分子为0，G6164以分子G2499以G15999分母G6984G19512，这G1075就G5859味G11540A是G1863G1122,ST的一个多项式。接下来G6117G1216就主要研究A的矩阵形式TABAASTDMMMMG1123G12G1866中系数矩阵0,0,0,00,0,21,1,1,21,0,01,21,21,1MNAABMNMNMNCCDCCCLMML称为多项式,FGH的DIXON矩阵；单项式ST和AB分别称为AD的行G7643和列G7643。G13792,ABC的G16757G12651公式G11013下式给出MIN,1MIN,21MIN,MIN,1,00MAX0,MAX1,1MIN,2MIN,MIN,0MAX0,MAX1,11,1,1,1,AMBNMAUNVABUVKAULBVBBNAUNVBVKAUMLBVNCUVLKLAUKBVUVLKLAUKBVMIN,110AMU定义22行G7643ST的指数向量集记为A115A116A117A118A119A120A121A122A123A124A124A125A126A127A128A129A130A131A132A133A134,|0ABAABAABRCSTC为中的项，称之为AD的行支集。列G7643AB的指数向量集记为,|0ABAABAABCABCSTC为中的项，称之为AD的列支集。G11013G1122A的分子,IJLKPQIJKLPQAFSTGSTHSTFTGTHTIJKLPQSTFGHG1124G12G6164以AD中的值G1863G1122,FGH的每个系数G18129是线G5627的。在此G6117G1216将,MNA，,MNAD，,MNAR，,MNAC相应G3332简记为,MN，,MND，,MNR，,MNCG5468显然，,MNG1863G1122,ST的次数分别为1,21,21,1MNMNG1075就是说,01021MNRMN，,02101MNCMNG1125G12并且G6117G1216G2499以得到,2MNMNRCMN，因此,MND是一个2MN阶的方阵。当,MNAA时，行列式,MND就是,FGH的G13475典DIXON结式。例G39261,1100100101100110100110110DA135A136A137A138A139A140A141A142A143A144A144A145A146A147A148A149A150A151A152A153A1543DIXONA结式这节的主要G1881容就是介绍下G19766的这个定理定理31设,MNA的左下角G451右下角G451左上角G451右上角的矩形子支集G1393次为1112213224120000SBLSBMRSCMRNSCLN，G1131G12若,FGH的多项式支集为,1234MNAASSSS，G2029有以下3个结论成立G111G12AD的行支集为,1234AMNRRSSSS，G1132G12列支集为,1234AMNCCSSSSG1133G12G112G1212342AARCMNSSSSG1134G12G113G12AD是方阵且G1866行列式AD是,FGH的A结式。G1866中112112112112111,111,111,111BBBMRRRNCCCMLLLNWESTRESSTHATFUNCTIONSMAYBENEITHERNEGLIGIBLENORNOTICEABLEA235A236A237A238A239A240A241A242A243A244A244A245A246A247A248A249A250A251A252A253A243A245222WEAKONEWAYFUNCTIONONEWAYFUNCTIONS,ASDEFINEDEARLIER,AREONEWAYINAVERYSTRONGSENSENAMELY,ANYEFFICIENTINVERTINGALGORITHMHASNEGLIGIBLESUCCESSININVERTINGTHEMAMUCHWEAKERDEFINITION,PRESENTEDNEXT,REQUIRESONLYTHATALLEFFICIENTINVERTINGALGORITHMSFAILWITHSOMENOTICEABLEPROBABILITYDEFINITION222WEAKONEWAYFUNCTIONSAFUNCTION0,10,1FISCALLEDWEAKLYONEWAYIFTHEFOLLOWINGTWOCONDITIONSHOLD1EASYTOCOMPUTEASINTHEDEFINITIONOFASTRONGONEWAYFUNCTION2SLIGHTLYHARDTOINVERTTHEREEXISTSAPOLYNOMIALPSUCHTHATFOREVERYPROBABILISTICPOLYNOMIALTIMEALGORITHMAANDALLSUFFICIENTLYLARGENS,11PR,1NNNAFUFFUPNWECALLTHEREADERSATTENTIONTOTHEORDEROFQUANTIFIERSTHEREEXISTSASINGLEPOLYNOMIALPSUCHTHATNP1LOWERBOUNDSTHEFAILUREPROBABILITYOFALLPROBABILISTICPOLYNOMIALTIMEALGORITHMSTRYINGTOINVERTFONNFUWEAKONEWAYFUNCTIONSFAILTOPROVIDETHEKINDOFHARDNESSALLUDEDTOINTHEEARLIERMOTIVATIONALDISCUSSIONSSTILL,ASWESHALLSEELATER,THEYCANBECONVERTEDINTOSTRONGONEWAYFUNCTIONS,WHICHINTURNDOPROVIDESUCHHARDNESS223TWOUSEFULLENGTHCONVENTIONSINTHESEQUELITWILLBECONVENIENTTOUSETHEFOLLOWINGTWOCONVENTIONSREGARDINGTHELENGTHSOFTHEPREIMAGESOFONEWAYFUNCTIONSINTHECURRENTSECTIONWEJUSTIFYTHEUSEOFTHESECONVENTIONS2231FUNCTIONSDEFINEDONLYFORSOMELENGTHSINMANYCASESITISMORECONVENIENTTOCONSIDERONEWAYFUNCTIONSWITHDOMAINSPARTIALTOTHESETOFALLSTRINGSINPARTICULAR,THISFACILITATESTHEINTRODUCTIONOFSOMESTRUCTUREINTHEDOMAINOFTHEFUNCTIONAPARTICULARLYIMPORTANTCASE,USEDTHROUGHOUTTHERESTOFTHISSECTION,ISTHATOFFUNCTIONSWITHDOMAIN0,1LNNNU,WHERELISSOMEPOLYNOMIALWEPROVIDEAMOREGENERALTREATMENTOFTHISCASELETNI,ANDDENOTEBYISNTHESUCCESSOROFNWITHRESPECTTOINAMELY,ISNISTHESMALLESTINTEGERTHATISBOTHGREATERTHANNANDINTHESETIIE,MINISNDEFIIINASETNIISCALLEDPOLYNOMIALTIMEENUMERABLEIFTHEREEXISTSANALGORITHMTHATONINPUTNHALTSWITHINNPOLYSTEPSANDOUTPUTS1ISNTHEUNARYOUTPUTFORCESISTOBEPOLYNOMIALBOUNDEDIE,ISNPOLYNLETIBEAPOLYNOMIALTIMEENUMERABLESETENDFBEAFUNCTIONWITHDOMAIN0,1NNNUWECALLFSTRONGLYRESP,WEAKLYONEWAYONLENGTHINIIFFISPOLYNOMIALTIMECOMPUTABLEANDISHARDTOINVERTOVERNSINIFOREXAMPLE,THEHARDNESSCONDITIONFORFUNCTIONSTHATARESTRONGLYONEWAYONLENGTHSINIISSTARTEDASFOLLOWSFOREVERYPROBABILISTICPOLYNOMIALTIMEALGORITHMA,EVERYPOSITIVEPOLYNOMIALP,ANDALLSUFFICIENTLYLARGENSINI,A254A255A1A0A2A3A4A5A9A6A6A7A12A8A10A11A13A14A15A16A9A1711PR,1NNNAFUFFUPN，我们就称函数RNV是显著的。这里要指出，存在一些函数既G993是可忽略的，G1075G993是显著的。222弱单向函数A99A100A101A102A103A104A105A106A107A108A108A109A110A111A112A113A114A115A116A117A118A119前面定义的单向函数是很严格意义下的单向，G2375在求逆的时候G1231意G20652G6940的求逆G17828算，求成功概率G18129是可忽略的。下面提供一种比较弱一些的定义，G4439G2494要求G6164有的G20652G6940求逆算法一显著的概率失败就可以了。定义222弱单向函数如G7536函数0,10,1FG9397G17287下面G1016个条件G20G714容易计算G2656强单向函数定义中的要求一样。稍微有点难求逆存在一个多项式P，使得对于G8611一个概率多项式时间算法AG2656G1231意G17287够G3835的N，G18129有11PR,1NNNAFUFFUPNG2029称函数F是弱单向函数。请读者G8892意下面G18339词的顺G5219存在一个多项式P，使得在F作用下求UNFG2419G1699的G6164有概率多项式时间算法的失败概率下G11040G18129为NP1。弱单向函数G5194G8821有提供前面讨论中暗G12046的难G5242类型。G993过后面我们会G11487G2052弱单向函数能够转化成强单向函数，而后者能够提供难G5242类型。223两个有用的长度协议在后面，我们会经G5132G5224用下面的G1016个关于单向函数G2419G1699河乡的G19283G5242协议。本节G16789明使用这些协议的G2524理G5627。2231为一些长度定义的函数很多G5785G1929下，G13783G15397定义预属于全体字符G1030集G2524的单向函数G7368为方便。G10317别地，这为介绍一些函数的G13479构提供了方便。本节后面一直使用的一个G10317别重要的G1375子是定义在0,1LNNNUG990的函数，这里L时某一多项式。对这种G4466G1375我们将作G7368一G14336的处理。令NIG15关于I，我们用ISNG15932G12046N的一个后继，G2375ISN是在集G2524I中比NG3835的最小的整数G2375MINISNDEFIIIN。如G7536存在一种算法，当输入为N时，在NPOLYG8505G1881终止G5194输出1ISN，G2029称集G2524NI为多项式时间可数的一元输出使得IS以多项式为G11040，G2375ISNPOLYN。设I是一个多项式时间可G2027集，F为定义在0,1NNIUG990的一个函数。我们说F时定义在G19283G5242IG990的强弱单向函数，如G7536F时多项式时间可计算的G5194且在IG1881对N是难求逆的。G1375如，定义在G19283G5242IG990的强单向函数的难计算条件如下对于G8611一个概率多项式时间算法A、G8611一个G8503多项式P以及IG1881全体G17287够G3835的N，G18129有11PR,1NNNAFUFFUPN在前面章节中定义的一G14336单向函数可以G11487作是定义在G19283G5242NG990的单向函数。A120A121A122A123A124A125A126A127A128A129A129A130A131A132A133A134A135A136A137A138A139A140在G1166以多项式时间可G2027集G1881的G19283G5242G990的单向函数可以很容易地转化为一G14336单向函数G2375定义在G6164有0,1G990的函数。G10317别地，对G8611一个定义在0,1NNIUG990的函数F，令GXDEFFX这里X是G19283G5242在I中的X最G19283的前缀，可以构造函数0,10,1G。如G7536函数F是G12573G19283G5242的G2375对G6164有的XG18129有XXF，那么我们就可以修改构造函数过程以保持这种G5627质，G1186而获得G12573G19283G5242的函数0,10,1G，使得GXDEFFXX这里XXX，且X是G19283G5242在I中的X最G19283前缀。命题223设I为多项式时间可G2027集，且F是定义在G19283G5242在IG1881的强弱单向函数，那么GG2656G在G21G17G20式G2656G21G17G21式中G2010别定义在通G5132意义下是强弱单向函数。尽管G990G17860命G20076的G8503G11842G5627是非G5132吸引G1166的，G1306我们还是希望读者G993要忽略下面的G16789明。G16789明过程G4466G19481G990很简单，第一次用G2052了后面广泛使用的G16789明方法。这个G13479论用反G16789法来G16789明，通过假设GG能够以G993可能的概率成功地求逆，得出矛盾，G1186而G16789明GG具有难求逆的G5627质。得出矛盾的G2419G3252在于假设能一G18108允许的概率成功地对F求逆。G6454句话说，对F的求逆G15999转化为对GG的求逆。这里的“G2476形”G4466G19481G990是比标准G2476形G7368严格意义下的一种G2476形，必须保持算法的成功概率G993G2476。这种论点G15999称为可G13434G5627理论。证明G20330G1820G16789明GG2656G能以多项式时间算法计算。为了G16789明这一点，我们利用I是一多项式时间可G2027集的事G4466，这就意味着我们可以在多项式时间G1881G1927定I的成G2604G1375如，通过G16278G45311IMISMM。G1186而当输入X时，在多项式时间G1881可以G6226G2052IG1881小于X的最G3835的M。计算XGG15G6226G2052这个M，G5194G5224用函数F作用于X的前缀的第MG1313。对G可G1582同样的处理。下一G8505我们G16789明G保持了F的难求逆的G5627质，同样的G16789明可以说明G的难求逆G5627。为了简单G17227G16277，这里G2494提供F是强单向函数的G16789明，对于F是弱单向函数的G5785形可类似的给出G16789明。用反G16789法来G17839行G16789明。假设命G20076的G13479论G993G8503G11842，G2375存在一个G20652G6940的能以G993可忽略的成功概率对G求逆的算法。我们用这个算法来构造一个以G993可忽略概率对F求逆的算法，这样得出一个与命G20076前提矛盾的G13479论。G6454句话说，我们指出以G993允许的成功概率对G求逆，G3252此可推G4560出后一算法的G993可能G5627。化简的G1393G6466是如G7536可以对G求G1231意G19283G5242的G2419G1699，就可以对G求G19283G5242在I为G1881的G2419G1699，而求这样G19283G5242的G2419G1699G与F就发生了冲突。直G16278地，G1231意一个对G求逆的算法G18129可以如下转G6454为对F求逆的算法。当输入A141A142A143A144A145A146A147A148A149A150A150A151A152A153A154A155A156A157A158A159A160A161,1NY时，我们可以G16855用输入为,1MY时的G逆G2476G3132G76G81G89G72G85G87G72G85G15G5194输出G逆G2476G3132G17832G3250G1030的G19283G5242在IG1881的最G19283前缀G1375如如G7536G逆G2