pairwiseubuntu12.10
ubuntu12.10 时间:2021-04-01 阅读:()
ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithm:SolvingtheIdealLatticeChallengeof128dimensionsTsukasaIshiguro1ShinsakuKiyomoto1YutakaMiyake1TsuyoshiTakagi2KDDIR&DLaboratoriesInc.
1InstituteofMathematicsforIndustry,KyushuUniversity22014/3/281/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentBackgroundSomecontestsfromTUDarmstadt-SVPChallenge,IdealLatticeChallenge,LatticeChallenge2/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentBackgroundSomecontestsfromTUDarmstadt-SVPChallenge,IdealLatticeChallenge,LatticeChallengeOurcontributions·AparallelversionofanalgorithmforsolvingSVP·Improvementsusingidealstructures·Solvingthe128dimensionalSVPoverideallattice2/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentndimensionallatticeandSVPb1b2ShortestvectorsLatticebasisB=(b1,bn)∈Zn*n,bi∈ZnLatticeL(B)=1≤i≤nαibi,αi∈Z(Euclidean)normofv=(v1,.
.
,vn)||v||=1≤i≤nv2iDenition(ShortestVectorProblem(SVP))GivenalatticeL(B),ndashortestnon-zerovectorinL(B).
3/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentndimensionalideallatticevrot(v)rot2(v)Polynomialrepresentationv=(v1,vn)∈L(B)v(x)=1≤i≤nvixi1∈Z[x]Vectorrotationrot(v)=xv(x)modg(x)g(x):monic,deg(g(x))=nIfrot(v)∈L(B)forallv∈L(B),thentheL(B)iscalledideallattice4/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGauss-reducedDenition(Gauss-reduced)Iftwodifferentvectorsa,b∈L(B)satisfy||a±b||≥max(||a||,||b||),thena,barecalledGauss-reduced.
abb′=ababa+bbaab′a+b′Reducea,barenotGauss-reduced.
a,b′areGauss-reduced.
Wesaythatb(orb′)wasreducedbya.
5/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentPairwise-reducedDenition(Pairwise-reduced)LetAbeasetofdvectorsinL(B).
Ifeverypairoftwovectors(ai,aj)inAfori,j=1,d,ijisGauss-reduced,thentheAiscalledpairwise-reduced.
AnypairofvectorsareGauss-reducedSetofvectors6/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reduced(1)chosenatrandomorpoppedfromstackS7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reduced(2)checkandreducev(3)ifvwasreduced,movevintostackS7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reduced(4)checkandreducei(5)ifiwasreduced,moveiintostackS7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reduced(6)appendvtoL7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reducedGaussSievealgorithmconstructsabiglistLoflatticevectors,whichisalwayspairwise-reduced.
Finally,ashortestvectorappearedinthelistL.
7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelizationTheGaussSievealgorithmisnoteasytobeparallelizedMildeandSchneiderproposedaparallelimplementationoftheGaussSieve[MildeandSchneider,'10]ThemalgorithmdoesnotkeepthelistLpairwise-reducedWhentheyused10threads,thelistLdoubledsizeoforiginalalgorithm8/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelizationTheGaussSievealgorithmisnoteasytobeparallelizedMildeandSchneiderproposedaparallelimplementationoftheGaussSieve[MildeandSchneider,'10]ThemalgorithmdoesnotkeepthelistLpairwise-reducedWhentheyused10threads,thelistLdoubledsizeoforiginalalgorithmOurgoalWeproposeafullyparallelizedGaussSievealgorithm.
8/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelizationTheGaussSievealgorithmisnoteasytobeparallelizedMildeandSchneiderproposedaparallelimplementationoftheGaussSieve[MildeandSchneider,'10]ThemalgorithmdoesnotkeepthelistLpairwise-reducedWhentheyused10threads,thelistLdoubledsizeoforiginalalgorithmOurgoalWeproposeafullyparallelizedGaussSievealgorithm.
OurstrategyOuralgorithmalwayskeepsthelistLpairwise-reducedwithoutreferencetothenumberofthreads.
8/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(1)chooseatrandomorpoppedfromstackS9/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(2)checkandreducevi(3)ifviwasreduced,moveviintostackS9/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(4)checkandreducevi(5)ifviwasreduced,moveviintostackS9/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(6)checkandreducei(7)ifiwasreduced,moveiintostackS9/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(8)appendvitoLv4v3v2v19/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentIsanewLpairwise-reducedListL12345ListVv4v3v2v1·LandVarepairwise-reduced,respectivery·Allpairs(i,vj)areGauss-reduced→V∪Lispairwise-reducedanewL=ListV∪L12345v4v3v2v1+10/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentSolvingthe72dimensionalSVP02004006008001000120048121620242832Time(minutes)ThenumberofthreadsTotaltime·Thisinstancehas16cores·Therunningtimedereasesuntil16threads·ThesizesofthelistLaremostofthesame11/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentListoftheimprovementsofGaussSieveGenericimprovements-Samplingshortvectors·Reductionoflengthsofsamplingvectors→about5timesfaster-Improvementofimplementation·UsingSIMDoperations→n=80,96,128→about4timesfastersSpecicimprovements-IdealGaussSieveforn=2α(Anti-cycliclattice)[Schneider,'11]→n=128-Trinomiallatticeforn=2s3t·Inverserotationrot1(v)=x1v(x)modg(x)·Updatingtoshortvectors→n=96→morethan25timesfaster12/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentExperimentenvironmentAmazonEC2cc1.
8xlargeinstanceOS:Ubuntu12.
10IntelXeonE5-2670(2.
6Ghz),total16coresgsievelibrary[Voulgaris]compiler:g++4.
1.
2,OpenMP,OpenMPIImprovementofimplementationOurassumptions-Allabsolutevaluesofnormsofvectorsarelessthan216-CalculatingtimeofinnerproductismostexpensiveWeoptimizedinnerproductbyusingSIMDoperations-8-parallelizationof16-bitadditionandmultiplication(SSE4.
2)→about4timesfaster13/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentSolvingtheChallengesSVPChallengedimnCPUhours#instances#threadstype800.
9132Randomlattice962004128RandomlatticeIdealLatticeChallengedimnCPUhours#instances#threadstype800.
9132Ideallattice968132Trinomiallattice12829,994842,688Anti-cycliclatticeOriginalgsievelibraryrequiresabout1weekforsolvinga80dimensionalSVPTrinomiallattice:25timesfaster14/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentConclusionWeproposedaparallelversionoftheGaussSievealgorithmWefoundthenewconditionstospeeduptheGaussSievealgorithmWesolveda128dimensionalSVPoverideallattice,whichhadnotbeensolvedbeforeThefull-versionispublishedin[ePrint2013/388]Openproblems-HowisthetheoreticalcomplexityoftheGaussSieve,theParallelGaussSieve,andtheIdealGaussSieve-DoesthereexistotherconditionsortechniquestospeeduptheGaussSievealgorithm15/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperiment16/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentSolvingthe80dimensionalSVP01000200030004000500001000020000300004000050000Runningtime(seconds)Thenumberofsamples$r$17/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentSamplingshortvectorOptimizationofsamplingalgorithm,namelySampleDalgorithminKlein'srandomizedroundingalgorithm.
Wetrytoadjusttheparameterwhichdeterminesthetradeoffbetweenthelengthofthenormofsamplevectorsandtherunningtimeofouralgorithm.
Average:6.
24GHMaximum:10.
58GH→Average:1.
66GHMaximum:2.
07GHGHistheGaussianheuristicbound:GH=(1/√π)Γ(n2+1)1n·det(L(B))1n18/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentApplyingIdealGaussSieve[Schneider,ePrint2011/458]Anti-cycliclattice-n=2α,α∈N-Cyclotomicpolynomial:g(x)=xn+1Vectorrotationrot(v)=(vn,v1,vn1)||roti(v)||=||v||,(1≤i≤n)Itiseasytogenerate(n1)independentvectorsroti(v)ofsamelengthfromonevectorvListL1234ListL1234rot(1)rot(2)rot(3)rot(4)rotn1(1)rotn1(2)rotn1(3)rotn1(4)19/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentTrinomialLattice(1/2)Cyclotomicpolynomial:g(x)=xn±xn/2+1-(case1)n=2·3m,m>0-(case2)n=2s3t,s>1,t>0Vectorrotationrot(v)=(vn,v1,vn22,vn21vn1,vn2vn1)Differentialofnorm||rot(v)||||v||=(vn1)22vn21vn1→If(vn1)22vn21vn1<0,normofalatticevectordecreases.
20/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentTrinomialLattice(2/2)Improvement3-1:Inverserotation-rot1(v)=x1v(x)modg(x)x1:inverseofxmodulog(x)Improvement3-2:Vectorupdate-choosingtheshortestvectorinfollowingvectorsrot(v),rot2(v)rotk(v)rot1(v),rot2(v)rotk(v)Solvingthe72dimensionalSVP4080120160200240048121620Runningtime(seconds)Onlyrotation[22]InverserotationInverserotation+Updatingvector21/15
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithm:SolvingtheIdealLatticeChallengeof128dimensionsTsukasaIshiguro1ShinsakuKiyomoto1YutakaMiyake1TsuyoshiTakagi2KDDIR&DLaboratoriesInc.
1InstituteofMathematicsforIndustry,KyushuUniversity22014/3/281/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentBackgroundSomecontestsfromTUDarmstadt-SVPChallenge,IdealLatticeChallenge,LatticeChallenge2/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentBackgroundSomecontestsfromTUDarmstadt-SVPChallenge,IdealLatticeChallenge,LatticeChallengeOurcontributions·AparallelversionofanalgorithmforsolvingSVP·Improvementsusingidealstructures·Solvingthe128dimensionalSVPoverideallattice2/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentndimensionallatticeandSVPb1b2ShortestvectorsLatticebasisB=(b1,bn)∈Zn*n,bi∈ZnLatticeL(B)=1≤i≤nαibi,αi∈Z(Euclidean)normofv=(v1,.
.
,vn)||v||=1≤i≤nv2iDenition(ShortestVectorProblem(SVP))GivenalatticeL(B),ndashortestnon-zerovectorinL(B).
3/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentndimensionalideallatticevrot(v)rot2(v)Polynomialrepresentationv=(v1,vn)∈L(B)v(x)=1≤i≤nvixi1∈Z[x]Vectorrotationrot(v)=xv(x)modg(x)g(x):monic,deg(g(x))=nIfrot(v)∈L(B)forallv∈L(B),thentheL(B)iscalledideallattice4/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGauss-reducedDenition(Gauss-reduced)Iftwodifferentvectorsa,b∈L(B)satisfy||a±b||≥max(||a||,||b||),thena,barecalledGauss-reduced.
abb′=ababa+bbaab′a+b′Reducea,barenotGauss-reduced.
a,b′areGauss-reduced.
Wesaythatb(orb′)wasreducedbya.
5/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentPairwise-reducedDenition(Pairwise-reduced)LetAbeasetofdvectorsinL(B).
Ifeverypairoftwovectors(ai,aj)inAfori,j=1,d,ijisGauss-reduced,thentheAiscalledpairwise-reduced.
AnypairofvectorsareGauss-reducedSetofvectors6/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reduced(1)chosenatrandomorpoppedfromstackS7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reduced(2)checkandreducev(3)ifvwasreduced,movevintostackS7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reduced(4)checkandreducei(5)ifiwasreduced,moveiintostackS7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reduced(6)appendvtoL7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentGaussSieveAlgorithm[Micciancio,2009]ListLVectorvStackS12345Lisalwayspairwise-reducedGaussSievealgorithmconstructsabiglistLoflatticevectors,whichisalwayspairwise-reduced.
Finally,ashortestvectorappearedinthelistL.
7/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelizationTheGaussSievealgorithmisnoteasytobeparallelizedMildeandSchneiderproposedaparallelimplementationoftheGaussSieve[MildeandSchneider,'10]ThemalgorithmdoesnotkeepthelistLpairwise-reducedWhentheyused10threads,thelistLdoubledsizeoforiginalalgorithm8/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelizationTheGaussSievealgorithmisnoteasytobeparallelizedMildeandSchneiderproposedaparallelimplementationoftheGaussSieve[MildeandSchneider,'10]ThemalgorithmdoesnotkeepthelistLpairwise-reducedWhentheyused10threads,thelistLdoubledsizeoforiginalalgorithmOurgoalWeproposeafullyparallelizedGaussSievealgorithm.
8/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelizationTheGaussSievealgorithmisnoteasytobeparallelizedMildeandSchneiderproposedaparallelimplementationoftheGaussSieve[MildeandSchneider,'10]ThemalgorithmdoesnotkeepthelistLpairwise-reducedWhentheyused10threads,thelistLdoubledsizeoforiginalalgorithmOurgoalWeproposeafullyparallelizedGaussSievealgorithm.
OurstrategyOuralgorithmalwayskeepsthelistLpairwise-reducedwithoutreferencetothenumberofthreads.
8/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(1)chooseatrandomorpoppedfromstackS9/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(2)checkandreducevi(3)ifviwasreduced,moveviintostackS9/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(4)checkandreducevi(5)ifviwasreduced,moveviintostackS9/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(6)checkandreducei(7)ifiwasreduced,moveiintostackS9/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentParallelGaussSieveAlgorithmListLStackS12345Lisalwayspairwise-reducedListVv4v3v2v1(8)appendvitoLv4v3v2v19/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentIsanewLpairwise-reducedListL12345ListVv4v3v2v1·LandVarepairwise-reduced,respectivery·Allpairs(i,vj)areGauss-reduced→V∪Lispairwise-reducedanewL=ListV∪L12345v4v3v2v1+10/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentSolvingthe72dimensionalSVP02004006008001000120048121620242832Time(minutes)ThenumberofthreadsTotaltime·Thisinstancehas16cores·Therunningtimedereasesuntil16threads·ThesizesofthelistLaremostofthesame11/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentListoftheimprovementsofGaussSieveGenericimprovements-Samplingshortvectors·Reductionoflengthsofsamplingvectors→about5timesfaster-Improvementofimplementation·UsingSIMDoperations→n=80,96,128→about4timesfastersSpecicimprovements-IdealGaussSieveforn=2α(Anti-cycliclattice)[Schneider,'11]→n=128-Trinomiallatticeforn=2s3t·Inverserotationrot1(v)=x1v(x)modg(x)·Updatingtoshortvectors→n=96→morethan25timesfaster12/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentExperimentenvironmentAmazonEC2cc1.
8xlargeinstanceOS:Ubuntu12.
10IntelXeonE5-2670(2.
6Ghz),total16coresgsievelibrary[Voulgaris]compiler:g++4.
1.
2,OpenMP,OpenMPIImprovementofimplementationOurassumptions-Allabsolutevaluesofnormsofvectorsarelessthan216-CalculatingtimeofinnerproductismostexpensiveWeoptimizedinnerproductbyusingSIMDoperations-8-parallelizationof16-bitadditionandmultiplication(SSE4.
2)→about4timesfaster13/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentSolvingtheChallengesSVPChallengedimnCPUhours#instances#threadstype800.
9132Randomlattice962004128RandomlatticeIdealLatticeChallengedimnCPUhours#instances#threadstype800.
9132Ideallattice968132Trinomiallattice12829,994842,688Anti-cycliclatticeOriginalgsievelibraryrequiresabout1weekforsolvinga80dimensionalSVPTrinomiallattice:25timesfaster14/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentConclusionWeproposedaparallelversionoftheGaussSievealgorithmWefoundthenewconditionstospeeduptheGaussSievealgorithmWesolveda128dimensionalSVPoverideallattice,whichhadnotbeensolvedbeforeThefull-versionispublishedin[ePrint2013/388]Openproblems-HowisthetheoreticalcomplexityoftheGaussSieve,theParallelGaussSieve,andtheIdealGaussSieve-DoesthereexistotherconditionsortechniquestospeeduptheGaussSievealgorithm15/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperiment16/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentSolvingthe80dimensionalSVP01000200030004000500001000020000300004000050000Runningtime(seconds)Thenumberofsamples$r$17/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentSamplingshortvectorOptimizationofsamplingalgorithm,namelySampleDalgorithminKlein'srandomizedroundingalgorithm.
Wetrytoadjusttheparameterwhichdeterminesthetradeoffbetweenthelengthofthenormofsamplevectorsandtherunningtimeofouralgorithm.
Average:6.
24GHMaximum:10.
58GH→Average:1.
66GHMaximum:2.
07GHGHistheGaussianheuristicbound:GH=(1/√π)Γ(n2+1)1n·det(L(B))1n18/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentApplyingIdealGaussSieve[Schneider,ePrint2011/458]Anti-cycliclattice-n=2α,α∈N-Cyclotomicpolynomial:g(x)=xn+1Vectorrotationrot(v)=(vn,v1,vn1)||roti(v)||=||v||,(1≤i≤n)Itiseasytogenerate(n1)independentvectorsroti(v)ofsamelengthfromonevectorvListL1234ListL1234rot(1)rot(2)rot(3)rot(4)rotn1(1)rotn1(2)rotn1(3)rotn1(4)19/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentTrinomialLattice(1/2)Cyclotomicpolynomial:g(x)=xn±xn/2+1-(case1)n=2·3m,m>0-(case2)n=2s3t,s>1,t>0Vectorrotationrot(v)=(vn,v1,vn22,vn21vn1,vn2vn1)Differentialofnorm||rot(v)||||v||=(vn1)22vn21vn1→If(vn1)22vn21vn1<0,normofalatticevectordecreases.
20/15ParallelGaussSieveAlgorithmT.
Ishiguro,S.
Kiyomoto,Y.
Miyake,T.
TakagiOutlineBackgroundProposedAlgorithmImprovementsExperimentTrinomialLattice(2/2)Improvement3-1:Inverserotation-rot1(v)=x1v(x)modg(x)x1:inverseofxmodulog(x)Improvement3-2:Vectorupdate-choosingtheshortestvectorinfollowingvectorsrot(v),rot2(v)rotk(v)rot1(v),rot2(v)rotk(v)Solvingthe72dimensionalSVP4080120160200240048121620Runningtime(seconds)Onlyrotation[22]InverserotationInverserotation+Updatingvector21/15
- pairwiseubuntu12.10相关文档
- 矩阵ubuntu12.10
- 2019年铜陵学院机器人工程基础实验室
- 文件linux下安装hadoop完全分布式（ubuntu12.10）
- 分区Win7和ubuntu12.10双系统安装教程[方案]
- 文件Linux下安装Hadoop完全分布式（Ubuntu12.10）
- 安装u盘装置ubuntu12.10全过程图解[总论]
亚洲云Asiayu,成都云服务器 4核4G 30M 120元一月
点击进入亚云官方网站（www.asiayun.com）公司名：上海玥悠悠云计算有限公司成都铂金宿主机IO测试图亚洲云Asiayun怎么样？亚洲云Asiayun好不好？亚云由亚云团队运营，拥有ICP/ISP/IDC/CDN等资质，亚云团队成立于2018年，经过多次品牌升级。主要销售主VPS服务器，提供云服务器和物理服务器，机房有成都、美国CERA、中国香港安畅和电信，香港提供CN2 GIA线路，CE...
digital-vm$80/月，最高10GDigital-VM1Gbps带宽带宽
digital-vm在日本东京机房当前提供1Gbps带宽、2Gbps带宽、10Gbps带宽接入的独立服务器，每个月自带10T免费流量，一个独立IPv4。支持额外购买流量：20T-$30/月、50T-$150/月、100T-$270美元/月；也支持额外购买IPv4，/29-$5/月、/28-$13/月。独立从下单开始一般24小时内可以上架。官方网站：https://digital-vm.com/de...
华纳云，3折低至优惠云服务器，独立服务器/高防御服务器低至6折，免备案香港云服务器CN2 GIA三网直连线路月付18元起，10Mbps带宽不限流量
近日华纳云发布了最新的618返场优惠活动，主要针对旗下的免备案香港云服务器、香港独立服务器、香港高防御服务器等产品，月付6折优惠起，高防御服务器可提供20G DDOS防御，采用E5处理器V4CPU性能，10Mbps独享CN2 GIA高速优质带宽，有需要免备案香港服务器、香港云服务器、香港独立服务器、香港高防御服务器、香港物理服务器的朋友可以尝试一下。华纳云好不好？华纳云怎么样？华纳云服务器怎么样？...
ubuntu12.10为你推荐
-
乐划锁屏乐视屏幕手机解锁忘记但是指纹可以解开怎么办？8080端口路由器如何开8080端口www.20ren.com有什么好看的电影吗？来几个…陈嘉垣陈浩民狼吻陈嘉恒是什么时候的事8090lu.com8090向前冲电影 8090向前冲清晰版 8090向前冲在线观看 8090向前冲播放 8090向前冲视频下载地址？？se95se.comwww.sea8.com这个网站是用什么做的 需要多少钱www.hyyan.comDOTA6.51新手选什么英雄为好，请详细讲述出装备顺序，加点顺序，以及注意事项。谢谢www.ijinshan.com在电脑看港台电视台那个网站最好而又不用钱速度又快baqizi.cc和空姐一起的日子电视剧在线观看 和空姐一起的日子全集在线观看baqizi.cc孔融弑母是真的吗？