The complexity of bit retrieval位检索地复杂性.pdf

《The complexity of bit retrieval位检索地复杂性.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ThecomplexityofbitretrievalVeitElserDepartmentofPhysicsCornellUniversityAbstractBitretrievalistheproblemofreconstructingabinarysequencefromitsperiodicautocorrelation,withapplicationsincryptographyandx-raycrys-tallography.Afterdefiningtheproblem,withandwithoutnoise,wedescr

2、ibeandcomparevariousalgorithmsforsolvingit.Ageometricalconstraintsatis-factionalgorithm,relaxed-reflect-reflect,iscurrentlythebestalgorithmfornoisybitretrieval.1BitretrievalThebitretrievalproblemisliketheproblemoffactoringintegers,butwithsomemodificationstotherulesofarithme

3、tic.Thesemodificationsareillustratedbelow,wherethecalculationof13×19inbase-2iscontrastedwiththerulesofbitre-trieval.Therearetwochanges:(i)exponentsinthebinaryexpansionareperiodic(columns“wraparound”),and(ii)thecolumnsaresummedwithoutcarrying.InarXiv:1601.03428v1[cs.DS]13J

4、an2016bothfactoringandbitretrievaltheproblemistoreversetheprocess:findthebinarysequencesatthetop,giventheirproductatthebottom.Periodicorring-likearrangementsofintegersthatarecombinedwiththerulesjustdescribedareelementsofthepolynomialringZN=Z[x]/(xN−1),whereNistheperiodoft

5、heexponents(N=5intheexample).FactoringelementsinZNishard,evenwhenwearetoldthecoefficientsofthefactorsarelimitedto0and1.Wewillseeshortlythatinbitretrievalitmakesmoresensetoinsteadlimitthecoefficientsto±1;wethereforedefinethesetS={s+sx+···+sxN−1∈Z:s=±1,0≤k≤N−1}.(1)N01N−1Nk111

6、0101101×10011×100111101011011101110101101101101111011122221Therulesofordinarybase-2multiplication(left)aremodified(right)sothatexponentshaveperiod5andcolumnsaresummedwithoutcar-ries.“Retrieval”isareferencetophaseretrieval,animportantspecialcasewherethetwocoefficientsequenc

7、esarereflectionsofeachother(one“ring”isthemirroroftheother).Thisbringsustoourfirstformulationofbitretrieval:Definition1.1.Bitretrievalistheproblemwhere,givena(x)∈ZNknowntohavetheforma(x)=s(x)s(1/x)forsomes(x)∈SN,wemustfinds′(x)∈SNsuchthats′(x)s′(1/x)=a(x).Theproblemdefinition

8、sidestepsthequestionofuniqueness.Clearly,ifs′(x)isasolution,thensoare±s′(x)xrand±s′(1/x)xr,forarbitrary