LLL lattice basis reduction algorithm

《LLL lattice basis reduction algorithm》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、LLLlatticebasisreductionalgorithmHelferEtienne21.03.2010Contents1Lattice11.1Introduction............................11.2Denition.............................21.3Determinant............................31.4Shortestvectorproblem.....................52B

2、asisreduction62.1Introduction............................62.2Rank2basisreduction......................72.3LLLbasisreduction.......................103LLLbasisreductionforsolvingRSAproblem173.1RSA................................173.2Coppersmith........

3、...................183.3Application............................214Implementationandexamples214.1LLL................................224.2Coppersmith...........................244.3RSAattack............................265Acknowledgements276Bibliography

4、271Lattice1.1IntroductionSincetheLLLlatticereductionbasisalgorithmoperatesonalatticeitisimportanttounderstandwhatisit.ManyconceptsinLatticetheoryarerelatedwithlinearalgebra:alatticecanberepresentedwiththematrix1ofitsbasis,ithasadeterminant,andsoon.La

5、terwewillneedlinearalgebramethodsandmatrixpropertiesfortheLLLalgorithm.Iwon'tgiveacompleteandpreciseviewofthelatticetheorybutfavorthegeometricalpointofviewandfocusontheelementsthatareneededtounderstandLLLbasisreduction.1.2DenitionAlatticeisadiscrete

6、subgroupofanEuclideanvectorspace.IngeneralthevectorspaceisRnorasubspaceofRn.Itisconvenianttodescribealatticeusingitsbasis.ThebasisofalatticeisasetoflinearlyindependentvectorsinRnwhichcangeneratethelatticebycombiningthem.Noticethatdierentbasescangene

7、ratethesamelattice(cf.gure1).Denition1.Asetofvectorsfb1;b2;:::;bmginRnislinearlyindepen-dentiftheequationc1b1+c2b2+


+cmbm=0whereci2R(1)acceptsonlythetrivialsolutionc1=c2=


=cm=0Theorem1.IfasetofvectorsinRncontainsmorevectorsthann(ifm>n),thenthis

8、setofvectorsisnotlinearlyindependent.Denition2.AsubspaceofRnisaanarbitrarysetHthathasthefollowingproperties:1.thenulvector0isanelementofH2.Hiscloseunderaddition:foreveryuandvinH,theirsumu+visanelementofH3.Hiscloseunderscalarmultiplication:foreveryui