资源描述：
《外文书籍how-to-construct-random-algorithm》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、HotitoConstructRandomFunctionsODEDGOLDREICH,SHAFIGOLDWASSER,ANDSILVIOMICALIMassachusettsInstituteofTechnology,Cambridge,MassachusettsAbstract.Aconstructivetheoryofrandomnessforfunctions,basedoncomputationalcomplexity,isdeveloped,andapseudorandomfunctiongeneratorispresented.Thisgeneratorisadet
2、erministicpolynomial-timealgorithmthattransformspairs(g,r),wheregisanyone-wayfunctionandrisarandomk-bitstring,topolynomial-timecomputablefunctionsf,:{1,...,2’)+{1,...,2kl.Thesef,‘scannotbedistinguishedfromrandomfunctionsbyanyprobabilisticpolynomial-timealgorithmthatasksandreceivesthevalueofaf
3、unctionatargumentsofitschoice.Theresulthasapplicationsincryptography,randomconstructions,andcomplexitytheory.CategoriesandSubjectDescriptors:F.0[TheoryofComputation]:General;F.1.1[ComputationbyAbstractDevices]:ModelsofComputation-computabilitytheory;G.0[MathematicsofComputing]:General;G.3[Mat
4、hematicsofComputing]:ProbabilityandStatistics-probabilisticalgorithms;randomnumbergenerationGeneralTerms:Algorithms,Security,TheoryAdditionalKeyWordsandPhrases:Cryptography,one-wayfunctions,predictionproblems,randomnessIhavesetuponaManchestercomputerasmallprogrammeusingonly1000unitsofstorage,
5、wherebythemachinesuppliedwithonesixteenfigurenumberreplieswithanotherwithintwoseconds.Iwoulddefyanyonetolearnfromtheserepliess&i-cientabouttheprogrammetobeabletopredictanyrepliestountriedvalues.A.TURING1.IntroductionWhatismeantbysayingthatcertainfunctions“‘behaverandomly”?Inthispaperweprovide
6、apreciseanswertotheabovequestion.Wethenpresentanefficientwaytoconstructfunctionsthatbehaverandomly,ifone-wayfunctionsexist.Weconcludebydemonstratingapplicationsofourconstruction.Randomnesshasattractedmuchattentioninthesecondhalfofthiscentury.However,mostofthepreviousworkfocusedonmeasuringther
7、andomnessofstrings.0.GoldreichwassupportedinpartbyaWeizmannpostdoctoralfellowship;S.GoldwasserwassupportedinpartbyanIBMfacultydevelopmentaward(1983)andNationalScienceFoundationgrantDCR8509905;andS.MicaliwassupportedbyaNationalScienceFoundatio
