---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------Progressive BKZ library test (version 202205)---------------------------------------- Notes: 1. It takes about 30-60 minutes. 2. It creates cache files in directory described in bkz.conf 3. It requires challenge-600 and LWE_40_005.txt from Lattice Challenge and LWE Challenge for complete test The latest version is published at https://www2.nict.go.jp/security/pbkzcode/ Contact mailing list: pbkz-info@nict.go.jp ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------PBKZlib test 1: basic subroutines---------------------------------------------- ----------------------------------------------------Read setting file: ----------------------------------------------------- dir. of constantscache=~/bkzwork/bkzcache/const dir. of pfcache=~/bkzwork/bkzcache/pf dir. of simcache=~/bkzwork/bkzcache/sim dir. of svpccache=~/bkzwork/bkzcache/svpc full-path of cache file directory: /home/a/bkzwork/bkzcache/const size of double=8 size of long double=16 maximum number of threads: 8 ---------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------test for memory allocation------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------Generating SVP challenge basis: ---------------------------------------------- dim=50 seed=0 B[1,1]=2572249791343926599834597246504438270825677441016286978314646816037633073718800960382407276679352978883369712522291598115976394261337503625492577298679 dim=100 seed=0 B[1,1]=7680916219385146434061257274071352244401082700778834458936215902141558756254495429588828478536242957389199439799970697304797645180068034274544188047780152124266949649679984435295146406255381905171231742991233806687321342343281344554026185558600501290524448762480231428108542987719421828022108239063007 dim=150 seed=0 B[1,1]=32994585006546975548950349183793411210357035761623219240080266420054151519279275786823796661048496392807557996368143464673604399247331144488555048724282838494622194174318080193336747494216729406611305588908394732021186450987320253425223980702827869697657719917231116454737397731482758287306600515911771556402818499930899026346656205707214339244346794247559648697546248062909194913002598663399252815318124803879451800607762193852727285906580029546669371 dim=200 seed=0 B[1,1]=91119767893568659551240749825799577242258882262465800646108680634668547198294348055247526725887469012531333058364542117822436592927643702668013621320878297869715339018913203671392843023165022944480026614198611927115397095672174017904073643518475170975481232009827953940080272551683371634402590453300794621597291182385349022382128000341504430142288989940542819607251497906168813967537646512190915593790863212339126057624290397059718431650450054850271975582216882279021027813630170196248733802236854676666589497191541357994902172142587713267157197722239395686564421879544889569370467707308163616724536027 ---------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------Save and Load: ------------------------------------------------------- save lattice basis to svpc_200 load lattice basis to svpc_200 matrix element check ---------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------test for constant table--------------------------------------------------- volume and surface of n-unit balls dim=10: volume=2.55016 surface=25.5016 dim=20: volume=0.0258069 surface=0.516138 dim=30: volume=2.19154e-05 surface=0.000657462 dim=40: volume=3.60473e-09 surface=1.441892e-07 dim=50: volume=1.73022e-13 surface=8.6511e-12 dim=60: volume=3.09625e-18 surface=1.85775e-16 dim=70: volume=2.43228e-23 surface=1.702596e-21 dim=80: volume=9.42649e-29 surface=7.541192e-27 dim=90: volume=1.96758e-34 surface=1.770822e-32 dim=100: volume=2.3682e-40 surface=2.3682e-38 gaussian heuristic constants: V_n(1)^(-1/n) dim=2 GH=0.56419 dim=4 GH=0.670938 dim=8 GH=0.839366 dim=16 GH=1.09464 dim=32 GH=1.47128 dim=64 GH=2.01774 dim=128 GH=2.8025 dim=256 GH=3.92246 dim=512 GH=5.51479 factorial(10)=3628800 factorial(20)=2432902008176640000 factorial(30)=265252859812191058636308480000000 factorial(40)=815915283247897734345611269596115894272000000000 factorial(50)=30414093201713378043612608166064768844377641568960512000000000000 factorial(60)=8320987112741390144276341183223364380754172606361245952449277696409600000000000000 factorial(70)=11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000 factorial(80)=71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000 factorial(90)=1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000 factorial(100)=93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 Binary coefficients: (10 choose 5)=252 (20 choose 5)=15504 (20 choose 10)=184756 (30 choose 5)=142506 (30 choose 10)=30045015 (30 choose 15)=155117520 (40 choose 5)=658008 (40 choose 10)=847660528 (40 choose 15)=40225345056 (40 choose 20)=137846528820 (50 choose 5)=2118760 (50 choose 10)=10272278170 (50 choose 15)=2250829575120 (50 choose 20)=47129212243960 (50 choose 25)=126410606437752 (60 choose 5)=5461512 (60 choose 10)=75394027566 (60 choose 15)=53194089192720 (60 choose 20)=4191844505805495 (60 choose 25)=51915437974328292 (60 choose 30)=118264581564861424 (70 choose 5)=12103014 (70 choose 10)=396704524216 (70 choose 15)=721480692460864 (70 choose 20)=161884603662657876 (70 choose 25)=6455761770304780752 (70 choose 30)=55347740058143507128 (70 choose 35)=112186277816662845432 (80 choose 5)=24040016 (80 choose 10)=1646492110120 (80 choose 15)=6635869816740560 (80 choose 20)=3535316142212174320 (80 choose 25)=363413731121503794368 (80 choose 30)=8871412534840453463008 (80 choose 35)=57900619847453606481440 (80 choose 40)=107507208733336176461620 (90 choose 5)=43949268 (90 choose 10)=5720645481903 (90 choose 15)=45795673964460816 (90 choose 20)=50980740277700939310 (90 choose 25)=11613412635260273974818 (90 choose 30)=673132974506580171230064 (90 choose 35)=11324588512110271581775824 (90 choose 40)=59870908646972742699313758 (90 choose 45)=103827421287553411369671120 (100 choose 5)=75287520 (100 choose 10)=17310309456440 (100 choose 15)=253338471349988640 (100 choose 20)=535983370403809682970 (100 choose 25)=242519269720337121015504 (100 choose 30)=29372339821610944823963760 (100 choose 35)=1095067153187962886461165020 (100 choose 40)=13746234145802811501267369720 (100 choose 45)=61448471214136179596720592960 (100 choose 50)=100891344545564193334812497256 ---------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------test for sampling tools--------------------------------------------------- random: 0.5488135 0.59284462 0.71518936 0.84426574 0.60276337 0.85794562 0.54488318 0.84725174 0.4236548 0.6235637 normal: 0.19596304 -0.88892573 -0.89384335 -0.33004838 -1.7103648 -0.37511648 1.5424636 -0.25908218 0.88871136 1.3411866 Pr[random < 0.1] =0.10128 Pr[normal > 0.5] =0.30945 ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- ------------------------------------------PBKZlib test 2: Gram-Schmidt subroutines------------------------------------------ ---------------------------------------------------------------------------------------------------------------------------- -----------------------------------------Generate random unimodular matrix dim=100------------------------------------------ U[0]=[0 0 1 1 2 6 -12 7 5 -16 -4 -1 2 10 13 -1 -1 8 -4 40 -6 -34 20 -10 -5 -18 -4 30 23 10 4 -21 29 -62 19 -61 -59 -3 17 9 -24 45 42 -34 -3 48 -24 50 107 -20 -10 49 0 -5 -160 -14 -51 112 12 -13 -23 -77 -77 237 -2 26 63 7 -223 334 -55 -34 -211 -77 288 213 -155 -266 243 -38 -103 -44 -85 532 160 128 -277 475 -577 4 58 156 -520 211 -809 120 -389 854 219 340] list of |b*i|: [1922.04 2296.94 1417.45 938.565 1541.76 847.686 792.32 1096.51 524.271 330.341 595.719 228.234 147.58 99.442 379.172 96.019 Last line of mu-matrix:0.732064 0.414673 -0.392095 -0.141898 -0.72133 -0.177143 0.448519 -0.0458158 -0.726699 -1.02877 -0.236568 1.78926 -0.74719 0 ---------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------Check size reduction---------------------------------------------------- Last line of mu-matrix after size reduce:-0.095559 0.0420327 -0.466413 0.0504812 -0.285627 0.395313 -0.0389941 -0.313788 0.313907 0.421228 0.0855531 0.448262 0.05233 ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- ----------------------------------BKZlib test3: precomputed table of pruning coefficients----------------------------------- ---------------------------------------------------------------------------------------------------------------------------- test: dim=60 ptarget=0.1 delta=1.01 Rigid_Lower_Prob=0.073213754 Rigid_Upper_Prob=0.11657392 Approx_Prob=0.10061344 ---------------------------------------------------------------------------------------------------------------------------- test: dim=60 ptarget=0.0001 delta=1.01 Rigid_Lower_Prob=1.9361249e-05 Rigid_Upper_Prob=0.00024565056 Approx_Prob=0.00010511833 ---------------------------------------------------------------------------------------------------------------------------- test: dim=60 ptarget=1e-12 delta=1.01 Rigid_Lower_Prob=7.701296e-17 Rigid_Upper_Prob=1.4386657e-10 Approx_Prob=9.4818305e-13 ---------------------------------------------------------------------------------------------------------------------------- test: dim=100 ptarget=0.1 delta=1.01 Rigid_Lower_Prob=0.0796164 Rigid_Upper_Prob=0.11081 Approx_Prob=0.10097573 ---------------------------------------------------------------------------------------------------------------------------- test: dim=100 ptarget=0.0001 delta=1.01 Rigid_Lower_Prob=6.24454e-05 Rigid_Upper_Prob=0.000120973 Approx_Prob=9.9842934e-05 ---------------------------------------------------------------------------------------------------------------------------- test: dim=100 ptarget=1e-12 delta=1.01 Rigid_Lower_Prob=4.54086e-14 Rigid_Upper_Prob=1.53764e-12 Approx_Prob=9.9426789e-13 ---------------------------------------------------------------------------------------------------------------------------- test: dim=140 ptarget=0.1 delta=1.01 Rigid_Lower_Prob=0.0715131 Rigid_Upper_Prob=0.119617 Approx_Prob=0.10193542 ---------------------------------------------------------------------------------------------------------------------------- test: dim=140 ptarget=0.0001 delta=1.01 Rigid_Lower_Prob=6.48408e-05 Rigid_Upper_Prob=0.000126555 Approx_Prob=0.00010143994 ---------------------------------------------------------------------------------------------------------------------------- test: dim=140 ptarget=1e-12 delta=1.01 Rigid_Lower_Prob=4.01869e-13 Rigid_Upper_Prob=1.52753e-12 Approx_Prob=9.9106852e-13 ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- -----------------------------------------BKZlib test4: LLL and pruning coefficients----------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- -----------------------------------Generate LLL basis for svp challenge dim=110 seed=10------------------------------------ first vector = [221 710 1746 1077 155 -1950 1308 683 -1512 -351 -494 2615 -952 1114 1449 685 2 -203 1071 155 -78 189 208 707 253 785 -627 456 145 -829 -1118 1114 90 -1884 -1601 -77 2798 -222 -744 -347 -2263 -75 -923 1651 2483 -788 1059 372 -93 -147 1141 -141 -424 701 526 306 -1119 1154 2357 -147 -484 244 -2363 65 -20 -1169 910 -964 1434 1322 -184 1229 -1868 -848 -891 792 241 -1704 -1032 1984 -72 905 200 831 -825 332 -86 -173 233 12 -809 483 508 197 1462 -1066 -75 -200 158 -416 -246 64 -54 27 -24 8 0 0 0 0] |b*i|: [10411 10087.8 9944.02 9851.51 9774.82 9232.56 8839.83 8843.21 8606.45 8044.24 7402.8 7548.38 6863.14 6586.43 6201.95 6073.3 GaussianHeuristic(L)=2655.4985 FullENUMCost(L)=6.6277255e+37 ---------------------------------------------------------------------------------------------------------------------------- Pruning coefficient for L (radius=1.1GH,p=0.0003, even dimension, from table interpolation) [0.0167848 0.0291283 0.0349817 0.0453806 0.0526889 0.0534117 0.0542968 0.0569308 0.0668452 0.0724398 0.0796321 0.089901 0.09 Rigid_Lower_Prob=0.000174199 Rigid_Upper_Prob=0.000379641 Approx_Prob=0.00030049478 Rigid_Upper_Cost=1.5869226e+26 ---------------------------------------------------------------------------------------------------------------------------- Pruning coefficient for L (radius=1.1GH,p=0.0003, even dimension, from systematic upper bound) [0.00237143 0.00585586 0.00993655 0.0144601 0.0193443 0.0245367 0.0300001 0.0357069 0.0416352 0.0477677 0.0540898 0.0605894 Rigid_Lower_Prob=0.0003 Rigid_Upper_Prob=0.00147041 Approx_Prob=0.00089794974 Rigid_Upper_Cost=2.5339924e+28 ---------------------------------------------------------------------------------------------------------------------------- Pruning coefficient for L (radius=1.1GH,p=0.0003, even dimension, from systematic upper bound + optimization) [0.0190761 0.0296406 0.0327212 0.0327749 0.0511446 0.0540644 0.0597192 0.0652515 0.0724308 0.0872073 0.10556 0.106703 0.1108 Rigid_Lower_Prob=0.00021536 Rigid_Upper_Prob=0.000385597 Approx_Prob=0.00033462692 Rigid_Upper_Cost=1.5558971e+26 ---------------------------------------------------------------------------------------------------------------------------- Pruning coefficient for L (radius=1.1GH,p=0.0003, even dimension, from systematic upper bound + optimization + post process) [0.020692 0.0218949 0.0369505 0.0734475 0.0758695 0.0766629 0.0786447 0.0935761 0.0942195 0.0963679 0.116311 0.117579 0.1242 Rigid_Lower_Prob=0.000208192 Rigid_Upper_Prob=0.00032717 Approx_Prob=0.00029364999 Rigid_Upper_Cost=1.0598619e+26 Change dimension to 111 ---------------------------------------------------------------------------------------------------------------------------- Pruning coefficient for L (radius=1.1GH,p=0.0003, odd dimension, from table interpolation) [0.0167848 0.0291283 0.0349817 0.0453806 0.0526889 0.0534117 0.0542968 0.0569308 0.0668452 0.0724398 0.0796321 0.089901 0.09 Rigid_Lower_Prob=0.000174199 Rigid_Upper_Prob=0.000379641 Approx_Prob=0.00029354393 Rigid_Upper_Cost=1.5869226e+26 ---------------------------------------------------------------------------------------------------------------------------- Pruning coefficient for L (radius=1.1GH,p=0.0003, odd dimension, from systematic upper bound) [0.00237143 0.00585586 0.00993655 0.0144601 0.0193443 0.0245367 0.0300001 0.0357069 0.0416352 0.0477677 0.0540898 0.0605894 Rigid_Lower_Prob=0.0003 Rigid_Upper_Prob=0.00147041 Approx_Prob=0.00091402749 Rigid_Upper_Cost=2.5339924e+28 ---------------------------------------------------------------------------------------------------------------------------- Pruning coefficient for L (radius=1.1GH,p=0.0003, odd dimension, from systematic upper bound + optimization) [0.0221289 0.0399358 0.0399618 0.0413357 0.0591978 0.0613741 0.0712893 0.078994 0.0829514 0.0834733 0.0899342 0.0903947 0.09 Rigid_Lower_Prob=0.000231037 Rigid_Upper_Prob=0.000370914 Approx_Prob=0.00033245275 Rigid_Upper_Cost=1.3964683e+26 ---------------------------------------------------------------------------------------------------------------------------- Pruning coefficient for L (radius=1.1GH,p=0.0003, odd dimension, from systematic upper bound + optimization + post process) [0.0509533 0.0574726 0.0602906 0.0829593 0.0831188 0.107955 0.111249 0.114155 0.119291 0.120719 0.125923 0.128881 0.140219 0 Rigid_Lower_Prob=0.000227084 Rigid_Upper_Prob=0.00035085 Approx_Prob=0.00030469315 Rigid_Upper_Cost=1.2071559e+26 ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- ----------------------BKZlib test5: Precision test for pruning functions (double, long double, float*)---------------------- Check subroutine for computing success probability Input coefficient R_i=1 for all i, expected output is prob=1 dim=10 result(double)=1 dim=11 result(double)=1 dim=12 result(double)=1 dim=13 result(double)=1 dim=14 result(double)=1 dim=15 result(double)=1 dim=16 result(double)=1 dim=17 result(double)=1 dim=18 result(double)=1 dim=19 result(double)=1 dim=20 result(double)=1 dim=21 result(double)=1 dim=22 result(double)=1 dim=23 result(double)=1 dim=24 result(double)=1 dim=25 result(double)=1 dim=26 result(double)=1 dim=27 result(double)=1 dim=28 result(double)=1 dim=29 result(double)=1 dim=30 result(double)=1 dim=31 result(double)=1 dim=32 result(double)=1 dim=33 result(double)=1 dim=34 result(double)=1 dim=35 result(double)=1 dim=36 result(double)=1 dim=37 result(double)=1 dim=38 result(double)=1 dim=39 result(double)=1 dim=40 result(double)=-14 ---------------------------------------------------------------------------------------------------------------------------- dim=40 result(long double)=1 dim=41 result(long double)=1 dim=42 result(long double)=1 dim=43 result(long double)=1 dim=44 result(long double)=1 dim=45 result(long double)=0 ---------------------------------------------------------------------------------------------------------------------------- dim=45 result(float10)=1 dim=46 result(float10)=1 dim=47 result(float10)=1 dim=48 result(float10)=1 dim=49 result(float10)=1 dim=50 result(float10)=1 dim=51 result(float10)=1 dim=52 result(float10)=1 dim=53 result(float10)=1 dim=54 result(float10)=1 dim=55 result(float10)=1 dim=56 result(float10)=1 dim=57 result(float10)=1 dim=58 result(float10)=1 dim=59 result(float10)=1 dim=60 result(float10)=1 dim=61 result(float10)=1 dim=62 result(float10)=1 dim=63 result(float10)=1 dim=64 result(float10)=1 dim=65 result(float10)=1 dim=66 result(float10)=1 dim=67 result(float10)=1 dim=68 result(float10)=1 dim=69 result(float10)=1 dim=70 result(float10)=1 dim=71 result(float10)=1 dim=72 result(float10)=1 dim=73 result(float10)=1 dim=74 result(float10)=1 dim=75 result(float10)=1 dim=76 result(float10)=1 dim=77 result(float10)=1 dim=78 result(float10)=1 dim=79 result(float10)=1 dim=80 result(float10)=1 dim=81 result(float10)=1 dim=82 result(float10)=1 dim=83 result(float10)=1 dim=84 result(float10)=1 dim=85 result(float10)=1 dim=86 result(float10)=1 dim=87 result(float10)=1 dim=88 result(float10)=1 dim=89 result(float10)=917865000 --------------------------------------------A bounding function of p approx 0.1--------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- dim=5 exact=1 result(double)=1 error=0 dim=6 exact=0.0029006 result(double)=0.00290058436397 error=5.39064952481e-06 dim=7 exact=0.00670528 result(double)=0.00670723186472 error=0.000291008982891 dim=8 exact=0.0188217 result(double)=0.0188232107877 error=8.02619544282e-05 dim=9 exact=0.0443211 result(double)=0.0443219727337 error=1.96907682845e-05 dim=10 exact=0.0809212 result(double)=0.080943786037 error=0.000279033611784 dim=11 exact=0.0966921 result(double)=0.0966888562054 error=3.35487951288e-05 dim=12 exact=0.101997 result(double)=0.101992556055 error=4.3571269389e-05 dim=13 exact=0.100466 result(double)=0.10046577635 error=2.22613510955e-06 dim=14 exact=0.104499 result(double)=0.104498669665 error=3.16114041221e-06 dim=15 exact=0.102963 result(double)=0.102963343729 error=3.33836193563e-06 dim=16 exact=0.0954291 result(double)=0.0954291441528 error=4.62676536356e-07 dim=17 exact=0.105803 result(double)=0.10580326658 error=2.51957872538e-06 dim=18 exact=0.105594 result(double)=0.105593830123 error=1.60877501272e-06 dim=19 exact=0.100469 result(double)=0.100468734653 error=2.6410887299e-06 dim=20 exact=0.103528 result(double)=0.103527856966 error=1.38159675484e-06 dim=21 exact=0.105904 result(double)=0.105904166228 error=1.5696123874e-06 dim=22 exact=0.104358 result(double)=0.104358289705 error=2.7760622053e-06 dim=23 exact=0.10717 result(double)=0.107169536714 error=4.322929564e-06 dim=24 exact=0.103532 result(double)=0.103531503396 error=4.79664388219e-06 dim=25 exact=0.104964 result(double)=0.104963648416 error=3.34957662853e-06 dim=26 exact=0.108914 result(double)=0.108914138117 error=1.26812712168e-06 dim=27 exact=0.102408 result(double)=0.102407740256 error=2.53636677305e-06 dim=28 exact=0.105538 result(double)=0.105537516011 error=4.58594715676e-06 dim=29 exact=0.110035 result(double)=0.110034618743 error=3.4648786525e-06 dim=30 exact=0.0966331 result(double)=0.0966331275887 error=2.85499577675e-07 dim=31 exact=0.105115 result(double)=0.105114525225 error=4.51673702499e-06 dim=32 exact=0.108166 result(double)=0.108166331318 error=3.06304253859e-06 dim=33 exact=0.098869 result(double)=0.098869047532 error=4.80757334429e-07 dim=34 exact=0.105992 result(double)=0.105991669 error=3.12289025424e-06 dim=35 exact=0.103691 result(double)=0.103691345102 error=3.32816693698e-06 dim=36 exact=0.101357 result(double)=0.10135695651 error=4.29072949477e-07 dim=37 exact=0.101157 result(double)=0.101157228665 error=2.26048633665e-06 dim=38 exact=0.100751 result(double)=0.100751465566 error=4.62093264238e-06 dim=39 exact=0.0997214 result(double)=0.0997214463359 error=4.64653651381e-07 dim=40 exact=0.1021 result(double)=0.102099731368 error=2.63107380862e-06 dim=41 exact=0.0986617 result(double)=0.0986616984728 error=1.54789109517e-08 dim=42 exact=0.0993932 result(double)=0.0993931436769 error=5.66669525698e-07 dim=43 exact=0.0992892 result(double)=0.0992891931146 error=6.9346917726e-08 dim=44 exact=0.100205 result(double)=0.100205286685 error=2.86097874617e-06 dim=45 exact=0.0988445 result(double)=0.0988446292049 error=1.30715149438e-06 dim=46 exact=0.100144 result(double)=0.100144332852 error=3.32372600855e-06 dim=47 exact=0.0979663 result(double)=0.0979657494709 error=5.61960832193e-06 dim=48 exact=0.0992764 result(double)=0.0992759730671 error=4.3004660184e-06 dim=49 exact=0.0992346 result(double)=0.0992346363191 error=3.65992418516e-07 dim=50 exact=0.0996792 result(double)=0.0996818682179 error=2.67673342524e-05 dim=51 exact=0.0992959 result(double)=0.0992945736816 error=1.33574105071e-05 dim=52 exact=0.101983 result(double)=0.101984962137 error=1.92394743857e-05 dim=53 exact=0.0987528 result(double)=0.09875124686 error=1.5727800937e-05 dim=54 exact=0.102421 result(double)=0.102412464606 error=8.33433076096e-05 dim=55 exact=0.0997391 result(double)=0.0997295171455 error=9.60884474408e-05 dim=56 exact=0.100542 result(double)=0.100561528627 error=0.000194195802109 dim=57 exact=0.104916 result(double)=0.104915089731 error=8.67624822442e-06 dim=58 exact=0.100432 result(double)=0.100440000053 error=7.96500687861e-05 dim=59 exact=0.102792 result(double)=0.102805606366 error=0.00013235042815 dim=60 exact=0.108186 result(double)=0.108261118046 error=0.000693859879824 dim=61 exact=0.10205 result(double)=0.101975204452 error=0.000733467985948 dim=62 exact=0.100064 result(double)=0.0999686675495 error=0.000953623298079 dim=63 exact=0.102508 result(double)=0.102983658289 error=0.00461877444641 ---------------------------------------------------------------------------------------------------------------------------- dim=63 exact=0.102508 result(long double)=0.102507748857 error=2.44999059662e-06 dim=64 exact=0.098656 result(long double)=0.0986557108584 error=2.93081438334e-06 dim=65 exact=0.0988624 result(long double)=0.098861108198 error=1.30668369103e-05 dim=66 exact=0.0959748 result(long double)=0.0959736727577 error=1.17453282711e-05 dim=67 exact=0.0935946 result(long double)=0.0935987815644 error=4.46754143908e-05 dim=68 exact=0.0886655 result(long double)=0.0886681907706 error=3.03465151058e-05 dim=69 exact=0.0815898 result(long double)=0.0816068233386 error=0.000208601902127 dim=70 exact=0.0679735 result(long double)=0.0679799101117 error=9.42942070143e-05 dim=71 exact=0.0761923 result(long double)=0.0761924393937 error=1.82949527551e-06 dim=72 exact=0.0841499 result(long double)=0.0844140258432 error=0.00312893314325 ---------------------------------------------------------------------------------------------------------------------------- dim=72 exact=0.0841499 result(float10)=0.0841499 error=0 dim=73 exact=0.0879304 result(float10)=0.0879304 error=0 dim=74 exact=0.0913197 result(float10)=0.0913197 error=0 dim=75 exact=0.0935467 result(float10)=0.0935467 error=0 dim=76 exact=0.0977854 result(float10)=0.0977854 error=0 dim=77 exact=0.0971803 result(float10)=0.0971803 error=0 dim=78 exact=0.0976912 result(float10)=0.0976912 error=0 dim=79 exact=0.100238 result(float10)=0.100238 error=0 dim=80 exact=0.101415 result(float10)=0.101415 error=0 dim=81 exact=0.100601 result(float10)=0.100601 error=0 dim=82 exact=0.0980079 result(float10)=0.0980079 error=0 dim=83 exact=0.0968379 result(float10)=0.0968379 error=0 dim=84 exact=0.0966031 result(float10)=0.0966031 error=0 dim=85 exact=0.096947 result(float10)=0.096947 error=0 dim=86 exact=0.0955595 result(float10)=0.0955595 error=0 dim=87 exact=0.0961282 result(float10)=0.0961282 error=0 dim=88 exact=0.0957824 result(float10)=0.0957824 error=0 dim=89 exact=0.0952623 result(float10)=0.0952623 error=0 dim=90 exact=0.10072 result(float10)=0.10072 error=0 dim=91 exact=0.0943254 result(float10)=0.0943254 error=0 dim=92 exact=0.0978163 result(float10)=0.0978163 error=0 dim=93 exact=0.0981217 result(float10)=0.0981217 error=0 dim=94 exact=0.0976116 result(float10)=0.0976116 error=0 dim=95 exact=0.098684 result(float10)=0.098684 error=0 dim=96 exact=0.096843 result(float10)=0.096843 error=0 dim=97 exact=0.0974301 result(float10)=0.0974301 error=0 dim=98 exact=0.0980764 result(float10)=0.0980764 error=0 dim=99 exact=0.0976679 result(float10)=0.0976679 error=0 dim=100 exact=0.100519 result(float10)=0.100519 error=0 dim=101 exact=0.0963382 result(float10)=0.0963381 error=1.03801092195e-06 dim=102 exact=0.0992547 result(float10)=0.0992547 error=0 dim=103 exact=0.097491 result(float10)=0.0974909 error=1.02573676107e-06 dim=104 exact=0.0988387 result(float10)=0.0988387 error=0 dim=105 exact=0.095798 result(float10)=0.095798 error=0 dim=106 exact=0.0983143 result(float10)=0.0983144 error=1.01714499605e-06 dim=107 exact=0.0966192 result(float10)=0.0966201 error=9.314832007e-06 dim=108 exact=0.0948332 result(float10)=0.113698 error=0.165920244859 ---------------------------------------------------------------------------------------------------------------------------- dim=108 exact=0.0948332 result(float10)=0.113698 error=0.165920244859 ---------------------------------------------------------------------------------------------------------------------------- ----------------------------Precision test for pruning functions (double, long double, bkzfloat)---------------------------- Check subroutine for computing success probability Input coefficient is generated for probability = 10^(-24) prec=4 dim=30 result=2.89888 exact=0.0966331 error=0.966665367314 prec=5 dim=32 result=1.22243 exact=0.108166 error=0.911515587805 prec=6 dim=34 result=0.30332 exact=0.105992 error=0.650560464196 prec=7 dim=36 result=0.149357 exact=0.101357 error=0.321377638812 prec=8 dim=38 result=0.109445 exact=0.100751 error=0.0794371602175 prec=9 dim=40 result=0.095263 exact=0.1021 error=0.071769732215 prec=10 dim=42 result=0.0972916 exact=0.0993932 error=0.0216010426388 prec=11 dim=44 result=0.0988813 exact=0.100205 error=0.0133867576579 prec=12 dim=46 result=0.100339 exact=0.100144 error=0.00194341183388 prec=13 dim=48 result=0.0992775 exact=0.0992764 error=1.10800533857e-05 prec=13 dim=53 result=0.0990111 exact=0.0987528 error=0.00260879840745 prec=14 dim=55 result=0.0997412 exact=0.0997391 error=2.10544890176e-05 prec=14 dim=60 result=0.107434 exact=0.108186 error=0.00699964629447 prec=15 dim=62 result=0.0998836 exact=0.100064 error=0.00180610230308 prec=16 dim=64 result=0.0983889 exact=0.098656 error=0.0027147371299 prec=17 dim=66 result=0.095993 exact=0.0959748 error=0.000189597158126 prec=17 dim=71 result=0.0783003 exact=0.0761923 error=0.0269219913589 prec=18 dim=73 result=0.0878102 exact=0.0879304 error=0.00136886147623 prec=19 dim=75 result=0.0935022 exact=0.0935467 error=0.00047592463065 prec=19 dim=80 result=0.102738 exact=0.101415 error=0.0128774163406 prec=20 dim=82 result=0.0976767 exact=0.0980079 error=0.00339077794397 prec=21 dim=84 result=0.0962259 exact=0.0966031 error=0.00391994255185 prec=22 dim=86 result=0.0955947 exact=0.0955595 error=0.00036822125076 prec=22 dim=91 result=0.0605673 exact=0.0943254 error=0.557365112858 prec=23 dim=93 result=0.0973233 exact=0.0981217 error=0.00820358536959 prec=24 dim=95 result=0.0978161 exact=0.098684 error=0.00887277247815 prec=25 dim=97 result=0.0974945 exact=0.0974301 error=0.000660550082312 ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- --------------------------------BKZlib test6A: enumeration subroutine (SVP, without pruning)-------------------------------- dim=44 radius=1883.316 full enumeration (prec=double, mode=enum_mode_all_vectors) #found=30 shortest length=1652.0372 full enumeration (prec=double, mode=enum_mode_find_shortest) #found=2 found shortest length=1652.0372 full enumeration (prec=double, mode=enum_mode_find_short_projection) #found=10000 full enumeration (prec=double, mode=num_mode_find_abort) found_length=1804.7532 (shortest=1652.0372) max_parallel=8 full enumeration (prec=double, mode=enum_mode_all_vectors, parallell) #found=30 ---------------------------------------------------------------------------------------------------------------------------- full enumeration for projected sublattice dim=30 norm=sqrt(2) expected number of vectors (whole basis)=900 expected number of vectors (sub 20-dim basis)=400 full enumeration (single core, whole lattice basis) # found vectors=900 full enumeration (single core, whole lattice basis, parallel) # found vectors=900 full enumeration (single core, sub lattice basis) # found vectors=400 # found vectors=400 full enumeration (parallel, sub lattice basis) # found vectors=400 # found vectors=400 ---------------------------------------------------------------------------------------------------------------------------- full enumeration (single core, whole lattice basis, after randomization) # found vectors=900 ---------------------------------------------------------------------------------------------------------------------------- full enumeration (parallel, whole lattice basis, after randomization) # found vectors=900 ---------------------------------------------------------------------------------------------------------------------------- full enumeration (single core, sub lattice basis, after randomization) # found vectors=400 # found vectors=400 ---------------------------------------------------------------------------------------------------------------------------- full enumeration (parallel, sub lattice basis, after randomization) # found vectors=400 # found vectors=400 ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- --------------------------------BKZlib test6B: enumeration subroutine (CVP, without pruning)-------------------------------- test for enumeration subroutine (CVP, without pruning) dim=30 subdim=20 target vector=[6 14 26 34 46 54 66 74 86 94 106 114 126 134 146 154 166 174 186 194 206 214 226 234 246 254 266 274 286 294] norm=22.360682 subnorm=18.439092 expected number of close vectors (whole basis)=31 expected number of close vectors (sub 20-dim basis)=21 ---------------------------------------------------------------------------------------------------------------------------- full enumeration BDD (single core, whole lattice basis) # found vectors=31 ---------------------------------------------------------------------------------------------------------------------------- full enumeration BDD (parallel, whole lattice basis) # found vectors=31 ---------------------------------------------------------------------------------------------------------------------------- full enumeration BDD(single core, sub lattice basis) # found vectors=21 # found vectors=21 ---------------------------------------------------------------------------------------------------------------------------- full enumeration BDD(parallel, sub lattice basis) # found vectors=21 # found vectors=21 ---------------------------------------------------------------------------------------------------------------------------- full enumeration BDD (single core, whole lattice basis, after randomization) # found vectors=31 ---------------------------------------------------------------------------------------------------------------------------- full enumeration BDD (parallel, whole lattice basis, after randomization) # found vectors=31 ---------------------------------------------------------------------------------------------------------------------------- full enumeration BDD (single core, sub lattice basis, after randomization) # found vectors=21 # found vectors=21 ---------------------------------------------------------------------------------------------------------------------------- full enumeration BDD (parallel, sub lattice basis, after randomization) # found vectors=21 # found vectors=21 ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------BKZlib test6C: enumeration subroutine (SVP, with pruning)---------------------------------- ---------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------Checking mild probability-------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- find a vector shorter than 1.05GH: dim=48 GH=1783.5809 radius=1872.7599 p_succ=0.096142109 #found=0 ---------------------------------------------------------------------------------------------------------------------------- find a vector shorter than 1.05GH: dim=52 GH=1874.5842 radius=1968.3135 p_succ=0.079096351 #found=0 ---------------------------------------------------------------------------------------------------------------------------- find a vector shorter than 1.05GH: dim=56 GH=1934.1303 radius=2030.8368 p_succ=0.065072764 #found=1 vector=[153 -242 -58 -24 181 498 -433 -6 -258 -100 -534 -11 135 -224 -244 -36 -188 -408 -69 -328 -229 178 -38 238 272 90 376 -6 -262 201 196 -233 233 -183 -186 367 -213 199 -60 -204 102 -177 -198 -338 -278 -415 281 476 101 -422 193 229 245 513 87 131] length=1921.006=0.99321435GH ---------------------------------------------------------------------------------------------------------------------------- find a vector shorter than 1.05GH: dim=60 GH=1983.9351 radius=2083.1318 p_succ=0.053535524 #found=1 vector=[-70 -179 92 34 418 240 -229 -55 -75 -179 44 46 -552 -125 -426 199 664 221 100 45 -313 279 425 320 503 289 152 -54 463 -403 336 -172 -70 315 82 -100 -260 -18 -152 -470 177 -66 53 66 160 338 -21 179 -213 210 -315 -229 -36 -179 -83 -404 255 -404 68 15] length=2021.262=1.0188146GH ---------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------Checking low probability-------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- find a vector shorter than 3.5GH: dim=60 GH=1983.9351 radius=6943.7727 p_succ=2.2694329e-33 parallel subtree depth=8 parallel subtree nodes=84 #found=1537 vector=[-673 -164 312 746 -81 -472 -223 -489 -494 234 -253 -332 -483 86 154 668 -195 -488 335 918 -86 51 121 -242 -243 508 -145 -577 -96 425 -595 982 -373 -369 364 -673 -420 62 -409 98 27 -391 626 62 48 95 -269 590 483 455 -428 -101 -152 -464 452 1630 -127 -47 92 -31] length=3505.5865=1.7669865GH vector=[-76 256 833 -187 59 -1027 -598 -972 565 -458 -353 9 -16 -365 -5 60 459 18 165 484 -147 -332 -172 339 -789 434 -849 -484 16 -546 -386 10 -472 -516 352 -832 -11 -805 125 -479 -467 -320 163 485 432 668 -144 -912 -677 -300 -500 -90 235 257 206 326 -132 644 524 -305] length=3613.3013=1.82128GH vector=[-76 256 833 -187 59 -1027 -598 -972 565 -458 -353 9 -16 -365 -5 60 459 18 165 484 -147 -332 -172 339 -789 434 -849 -484 16 -546 -386 10 -472 -516 352 -832 -11 -805 125 -479 -467 -320 163 485 432 668 -144 -912 -677 -300 -500 -90 235 257 206 326 -132 644 524 -305] length=3613.3013=1.82128GH ---------------------------------------------------------------------------------------------------------------------------- find a vector shorter than 3.5GH: dim=80 GH=2287.3834 radius=8005.842 p_succ=2.9823352e-44 parallel subtree depth=10 parallel subtree nodes=81 #found=357 vector=[-1027 -994 -888 -44 -275 1603 -514 400 -161 -637 -1025 -572 413 723 659 -183 213 -297 1198 261 130 504 93 -575 665 -211 596 114 -184 46 -442 -174 68 -904 -796 -65 -351 586 -134 -470 12 359 -926 -464 349 215 915 -1175 -306 -551 1110 -1243 469 -162 475 73 154 -347 -310 116 345 -562 -167 397 -109 -175 -194 524 687 -1070 18 309 -888 109 302 36 -101 0 0 0] length=5048.3485=2.2070408GH vector=[-57 399 -850 -1707 -268 -482 -287 506 113 614 109 -845 -115 -240 641 272 -1629 755 -386 -115 -189 215 -512 -108 -300 781 428 -648 -104 72 -57 868 -176 -200 -665 238 -19 742 -1224 63 1394 -63 -217 -1265 -1284 -491 -650 -999 84 -372 119 -569 -362 846 113 -214 -624 -925 10 990 809 -525 -162 -878 145 -229 1166 -967 -377 130 -240 -1240 92 474 -796 -71 -50 -36 28 -1] length=5638.935=2.4652338GH vector=[-57 399 -850 -1707 -268 -482 -287 506 113 614 109 -845 -115 -240 641 272 -1629 755 -386 -115 -189 215 -512 -108 -300 781 428 -648 -104 72 -57 868 -176 -200 -665 238 -19 742 -1224 63 1394 -63 -217 -1265 -1284 -491 -650 -999 84 -372 119 -569 -362 846 113 -214 -624 -925 10 990 809 -525 -162 -878 145 -229 1166 -967 -377 130 -240 -1240 92 474 -796 -71 -50 -36 28 -1] length=5638.935=2.4652338GH ---------------------------------------------------------------------------------------------------------------------------- find a vector shorter than 3.5GH: dim=100 GH=2541.6122 radius=8895.6427 p_succ=3.9191832e-55 parallel subtree depth=13 parallel subtree nodes=211 #found=597 vector=[953 -559 1650 -32 315 646 -411 298 -1055 -1098 674 -1107 269 289 775 -820 142 207 -298 785 24 544 464 -424 -394 -272 -1029 -193 756 979 539 -1033 -775 981 880 308 1399 -59 593 -784 -1142 -564 139 665 -1504 43 99 1666 1263 1197 -13 1419 528 1074 -814 97 -44 -550 -193 91 -817 414 1331 -1477 -1449 662 461 1005 595 700 212 -532 653 -939 298 1056 98 -800 -607 282 53 -1540 436 286 257 -631 -1195 1280 1495 -1001 198 -62 73 60 54 229 -48 -67 22 0] length=7659.5722=3.0136668GH vector=[1334 84 1247 -221 333 -905 2233 765 316 -1605 721 -962 150 -16 1342 -940 -551 61 -14 966 -388 329 -1313 -1307 1541 -1425 -777 -809 -277 1109 128 751 190 766 460 -907 -308 -1406 -1096 90 -1186 968 -429 -972 -929 -20 -1125 -921 948 1168 740 1070 1307 -674 -314 38 2110 240 265 101 11 -1825 -366 -202 93 1072 -241 1458 92 -1060 -241 515 -203 830 891 2191 -168 1488 -957 636 -653 690 -746 1142 -999 -490 1434 299 -995 486 -997 6 601 -70 181 -392 -2 18 -160 78] length=8862.2878=3.4868765GH vector=[-547 15 323 1181 1136 488 -289 -834 331 182 1439 -3 -960 -282 38 -296 1411 555 7 -337 -205 879 -149 1263 190 -701 329 -932 30 623 536 -248 -194 -2084 263 -740 -287 724 -857 -726 -648 851 28 305 -2598 -1585 767 -270 -1558 -973 749 -367 -716 218 -296 419 485 66 1052 48 867 -226 735 744 -106 -8 -366 1484 -338 182 -462 -9 -190 470 -1619 -111 246 1059 -1028 82 -628 1207 -918 -26 67 9 449 1107 -731 1018 -29 721 -351 177 305 -274 200 29 147 68] length=7423.8178=2.9209089GH ---------------------------------------------------------------------------------------------------------------------------- find a vector shorter than 3.5GH: dim=120 GH=2771.6373 radius=9700.7305 p_succ=5.1503255e-66 parallel subtree depth=22 parallel subtree nodes=132 #found=7 vector=[495 1498 -826 47 2055 -1051 594 596 211 1704 -1829 -482 -984 -319 -1160 -1898 1076 -156 -452 1195 -5 -597 -216 -1069 848 873 -352 -649 1681 600 -1662 -813 467 -196 3050 212 53 1137 -202 1143 -753 327 840 -52 -359 -349 -807 184 -946 -530 554 -717 -260 -793 -1525 137 439 434 177 1620 848 -164 10 477 358 1231 818 -1090 -1042 573 -586 737 -20 167 430 1 551 -11 -631 1083 2623 -493 802 -1270 857 721 438 330 904 652 989 649 -336 936 775 856 245 -244 562 95 -50 1244 1078 -119 1779 169 1439 -1073 533 -776 -496 -158 -352 -341 104 -420 486 73 -63 -57] length=9673.0894=3.4900272GH vector=[495 1498 -826 47 2055 -1051 594 596 211 1704 -1829 -482 -984 -319 -1160 -1898 1076 -156 -452 1195 -5 -597 -216 -1069 848 873 -352 -649 1681 600 -1662 -813 467 -196 3050 212 53 1137 -202 1143 -753 327 840 -52 -359 -349 -807 184 -946 -530 554 -717 -260 -793 -1525 137 439 434 177 1620 848 -164 10 477 358 1231 818 -1090 -1042 573 -586 737 -20 167 430 1 551 -11 -631 1083 2623 -493 802 -1270 857 721 438 330 904 652 989 649 -336 936 775 856 245 -244 562 95 -50 1244 1078 -119 1779 169 1439 -1073 533 -776 -496 -158 -352 -341 104 -420 486 73 -63 -57] length=9673.0894=3.4900272GH vector=[-835 -504 -344 2549 -207 667 2937 928 261 216 -1355 563 378 750 215 -757 -547 793 -80 1353 -990 506 -260 130 -249 851 457 -489 -219 1891 -321 -405 -570 123 1639 278 1636 938 20 827 1031 7 1003 -293 1384 1141 -330 -596 349 -1324 -287 -549 -1748 -1273 557 -799 -356 -661 -140 1382 772 -80 -1010 772 1231 452 1362 -223 -856 410 -282 210 -1292 -1755 -770 268 467 -767 2428 134 298 -1122 -110 -967 519 -605 293 -638 -1553 343 -559 -457 599 639 854 453 -441 1554 332 -177 475 -714 -1226 -104 577 715 -155 -526 41 721 222 211 -152 -462 -85 10 -330 138 5 0] length=9392.0653=3.3886344GH ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- -----------------------------BKZlib test7: Preprocessing subroutine for progressive BKZ dim=100----------------------------- costlimit_lb=1.5847696e+08 |b*i| before: [7659.57 7659.3 7308.23 7237.38 7145.86 7465.73 7306.86 6764.16 6206.42 5959.06 6263.61 6599.55 6413.06 5849.01 5403.88 5157 |b*i| after: [7659.57 7659.3 7308.23 7237.38 7145.86 7465.73 7306.86 6764.16 6206.42 3289.72 3223.46 3194.22 3026.9 2899.47 2910.37 2932. ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- -----------------------------------------------BKZlib test8: progressive BKZ------------------------------------------------ ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------generate ideal lattice challenge instance index=172 seed=0--------------------------------- dimension=84 phi=[1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1 0 -1 0 1] |b*i|: [5123.53 5075.2 5009.89 4672.56 4365.23 4175.18 4131.66 4211.98 3865.75 3704.06 3707.41 3658.31 3210.82 3038.11 3087.89 2930 ---------------------------------------------------------------------------------------------------------------------------- Enum-then-update subroutine, blocksize=40 |b*i|: [3457.31 3723.06 3551.3 3627.3 3589.77 3693.91 3614.84 3433.88 3243.17 3075.29 2916.5 2930.79 2804.95 2731.17 2505.05 2520.6 ---------------------------------------------------------------------------------------------------------------------------- Enum-then-update subroutine, blocksize=60 |b*i|: [3064.41 3010.96 3091.77 2905.78 2935.55 2894.66 2808.69 2507.05 2402.51 2288.69 2285.35 2253.75 2287.19 2122.63 2166.83 212 |b1|=1.3074744 ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- ------------------------Progressive BKZ for ideal lattice challenge instance index=119 dim=96 seed=0------------------------ (It may take a few minutes|.) After LLL: |b1|=2.2930508 ---------------------------------------------------------------------------------------------------------------------------- loop=1 time=0.00167918 tour=1 applybeta=15 basisbeta=9 |b1|=5701.97=2.29305GH logfec=66.4818/53.1384 time=0.543964 tour=2 applybeta=15 basisbeta=9 |b1|=5701.97=2.29305GH logfec=63.4395/53.1384 time=0.962463 tour=3 applybeta=15 basisbeta=9 |b1|=5701.97=2.29305GH logfec=61.4483/53.1384 time=1.31904 tour=4 applybeta=15 basisbeta=9 |b1|=4952.81=1.99177GH logfec=59.9361/53.1384 time=1.68588 tour=5 applybeta=15 basisbeta=9 |b1|=4952.81=1.99177GH logfec=58.5358/53.1384 time=2.00883 tour=6 applybeta=15 basisbeta=9 |b1|=4952.81=1.99177GH logfec=57.4901/53.1384 time=2.30404 tour=7 applybeta=15 basisbeta=9 |b1|=4902.96=1.97173GH logfec=56.6733/53.1384 time=2.59566 tour=8 applybeta=15 basisbeta=9 |b1|=4902.96=1.97173GH logfec=56.0667/53.1384 time=2.87036 tour=9 applybeta=15 basisbeta=9 |b1|=4673.53=1.87946GH logfec=55.5736/53.1384 time=3.15281 tour=10 applybeta=15 basisbeta=9 |b1|=4306.94=1.73204GH logfec=55.0943/53.1384 time=3.44227 tour=11 applybeta=15 basisbeta=9 |b1|=4306.94=1.73204GH logfec=54.5788/53.1384 time=3.73807 tour=12 applybeta=15 basisbeta=9 |b1|=4306.94=1.73204GH logfec=54.1274/53.1384 time=4.01525 tour=13 applybeta=15 basisbeta=9 |b1|=4306.94=1.73204GH logfec=53.8802/53.1384 time=4.25426 tour=14 applybeta=15 basisbeta=9 |b1|=4306.94=1.73204GH logfec=53.5146/53.1384 time=4.49516 tour=15 applybeta=15 basisbeta=9 |b1|=4306.94=1.73204GH logfec=53.3602/53.1384 time=4.72447 tour=16 applybeta=17 basisbeta=11 |b1|=3989.64=1.60444GH logfec=52.8825/52.5651 time=4.99185 tour=17 applybeta=17 basisbeta=11 |b1|=3989.64=1.60444GH logfec=52.5863/52.5651 time=5.24914 tour=18 applybeta=27 basisbeta=21 |b1|=3989.64=1.60444GH logfec=52.2807/52.0342 time=5.93081 tour=19 applybeta=28 basisbeta=22 |b1|=3989.64=1.60444GH logfec=51.9779/51.6049 time=6.48255 tour=20 applybeta=33 basisbeta=27 |b1|=3940.87=1.58482GH logfec=51.279/51.2534 time=7.23447 tour=21 applybeta=37 basisbeta=31 |b1|=3940.87=1.58482GH logfec=50.3042/50.2104 time=8.40347 tour=22 applybeta=42 basisbeta=36 |b1|=3735.85=1.50238GH logfec=49.3489/49.2352 time=9.95416 tour=23 applybeta=46 basisbeta=40 |b1|=3408.46=1.37071GH logfec=48.4961/48.3631 time=11.8892 tour=24 applybeta=50 basisbeta=44 |b1|=3263.41=1.31238GH logfec=47.7279/47.6077 time=16.4724 tour=25 applybeta=53 basisbeta=47 |b1|=3263.41=1.31238GH logfec=47.064/46.971 progressive bkz finish. time=21.3615 prob=0.00059234344 CostLB=99141486 ---------------------------------------------------------------------------------------------------------------------------- loop=2 time=1.49397 tour=1 applybeta=15 basisbeta=9 |b1|=2654.23=1.0674GH logfec=56.2217/53.1384 time=1.80216 tour=2 applybeta=15 basisbeta=9 |b1|=2654.23=1.0674GH logfec=55.1575/53.1384 time=2.10166 tour=3 applybeta=15 basisbeta=9 |b1|=2654.23=1.0674GH logfec=53.9463/53.1384 time=2.37203 tour=4 applybeta=17 basisbeta=11 |b1|=2654.23=1.0674GH logfec=52.9344/52.5651 time=2.72532 tour=5 applybeta=27 basisbeta=21 |b1|=2654.23=1.0674GH logfec=52.3628/52.0342 time=3.25429 tour=6 applybeta=35 basisbeta=29 |b1|=2654.23=1.0674GH logfec=50.575/50.4969 time=4.20739 tour=7 applybeta=43 basisbeta=37 |b1|=2654.23=1.0674GH logfec=49.1528/48.9449 time=5.48151 tour=8 applybeta=50 basisbeta=44 |b1|=2654.23=1.0674GH logfec=47.6119/47.6077 progressive bkz finish. time=9.0892 prob=0.00069624963 CostLB=97670818 ---------------------------------------------------------------------------------------------------------------------------- loop=3 time=0.00125289 tour=1 applybeta=15 basisbeta=9 |b1|=2654.23=1.0674GH logfec=54.3501/53.1384 time=0.366274 tour=2 applybeta=17 basisbeta=11 |b1|=2654.23=1.0674GH logfec=53.0416/52.5651 time=0.711063 tour=3 applybeta=28 basisbeta=22 |b1|=2654.23=1.0674GH logfec=51.8592/51.6049 time=1.31008 tour=4 applybeta=36 basisbeta=30 |b1|=2654.23=1.0674GH logfec=50.4883/50.3569 time=2.2223 tour=5 applybeta=46 basisbeta=40 |b1|=2654.23=1.0674GH logfec=48.4968/48.3631 progressive bkz finish. time=3.52634 prob=0.00068232464 CostLB=97240641 ---------------------------------------------------------------------------------------------------------------------------- loop=4 time=0.00125408 tour=1 applybeta=43 basisbeta=37 |b1|=2654.23=1.0674GH logfec=49.1253/48.9449 time=1.31156 tour=2 applybeta=51 basisbeta=45 |b1|=2654.23=1.0674GH logfec=47.4311/47.3393 progressive bkz finish. time=5.57647 prob=0.00088726238 CostLB=98664111 ---------------------------------------------------------------------------------------------------------------------------- loop=5 time=0.00118804 tour=1 applybeta=45 basisbeta=39 |b1|=2654.23=1.0674GH logfec=48.6687/48.6356 time=1.29562 tour=2 applybeta=58 basisbeta=52 |b1|=2654.23=1.0674GH logfec=46.5837/46.5088 progressive bkz finish. time=6.87175 prob=0.0017634595 CostLB=98788319 ---------------------------------------------------------------------------------------------------------------------------- loop=6 time=1.43128 tour=1 applybeta=53 basisbeta=47 |b1|=2654.23=1.0674GH logfec=47.1089/46.971 progressive bkz finish. time=6.0867 prob=0.001276388 CostLB=99633558 ---------------------------------------------------------------------------------------------------------------------------- loop=7 progressive bkz finish. time=0.0037291 prob=0.0010641856 CostLB=98251801 ---------------------------------------------------------------------------------------------------------------------------- loop=8 time=0.00122499 tour=1 applybeta=54 basisbeta=48 |b1|=2633.23=1.05895GH logfec=46.9592/46.8747 progressive bkz finish. time=5.90776 prob=0.0014702804 CostLB=99996572 ---------------------------------------------------------------------------------------------------------------------------- loop=9 progressive bkz finish. time=0.00607991 prob=0.001225843 CostLB=98301576 8 ---------------------------------------------------------------------------------------------------------------------------- loop=10 time=0.00152302 tour=1 applybeta=54 basisbeta=48 |b1|=2633.23=1.05895GH logfec=46.9127/46.8747 progressive bkz finish. time=4.20505 prob=0.0014408748 CostLB=97005004 found vector=[106 -802 212 262 421 181 -64 58 -7 340 -361 175 -112 314 -282 218 -420 65 -67 -57 -70 223 -57 194 -333 -170 275 109 316 -477 97 250 -395 -486 58 -48 342 70 -195 116 -65 195 -154 249 -166 -275 305 232 -202 -524 -29 -141 388 12 536 298 424 345 -146 31 231 -184 563 249 230 97 5 433 -103 -115 76 -96 -139 288 79 -160 -231 -92 301 594 -142 175 235 -175 -32 -318 -177 292 319 399 45 -354 -76 281 97 180] |b1|=1.0493259*GH ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------BKZlib test9: PBKZ simulator------------------------------------------------ ---------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------Find BKZ strategy: BKZ-20 -> 45----------------------------------------------- (It may take a few minutes.) Optimized strategy: 20->(59)->25->(60)->35->(61)->45 cost=97.3392 ---------------------------------------------------------------------------------------------------------------------------- progressive BKZ: LLL -> (25) -> 20 time=0.271775 tour=1 applybeta=25 basisbeta=9 |b1|=61602.3=17.3462GH logfec=260.697/189.907 time=6.09335 tour=2 applybeta=25 basisbeta=9 |b1|=57812.7=16.2791GH logfec=247.03/189.907 time=12.7183 tour=3 applybeta=25 basisbeta=9 |b1|=48957=13.7855GH logfec=236.188/189.907 time=18.2455 tour=4 applybeta=25 basisbeta=9 |b1|=45788.2=12.8932GH logfec=227.947/189.907 time=22.9734 tour=5 applybeta=25 basisbeta=9 |b1|=39610.2=11.1536GH logfec=223.763/189.907 time=27.5746 tour=6 applybeta=25 basisbeta=9 |b1|=38168.7=10.7477GH logfec=218.711/189.907 time=31.8973 tour=7 applybeta=25 basisbeta=9 |b1|=31492.1=8.86767GH logfec=215.066/189.907 time=36.5034 tour=8 applybeta=25 basisbeta=9 |b1|=31492.1=8.86767GH logfec=211.737/189.907 time=40.6936 tour=9 applybeta=25 basisbeta=9 |b1|=27891.9=7.85392GH logfec=209.047/189.907 time=45.0122 tour=10 applybeta=25 basisbeta=9 |b1|=27146.4=7.64401GH logfec=206.402/189.907 time=49.2595 tour=11 applybeta=25 basisbeta=9 |b1|=27146.4=7.64401GH logfec=203.795/189.907 time=53.4784 tour=12 applybeta=25 basisbeta=9 |b1|=27146.4=7.64401GH logfec=201.438/189.907 time=57.4923 tour=13 applybeta=25 basisbeta=9 |b1|=27146.4=7.64401GH logfec=199.629/189.907 time=61.717 tour=14 applybeta=25 basisbeta=9 |b1|=25306.3=7.12584GH logfec=198.218/189.907 time=66.6997 tour=15 applybeta=25 basisbeta=9 |b1|=24711.4=6.95834GH logfec=196.382/189.907 time=71.1598 tour=16 applybeta=25 basisbeta=9 |b1|=23871.7=6.72189GH logfec=194.784/189.907 time=75.1627 tour=17 applybeta=25 basisbeta=9 |b1|=23871.7=6.72189GH logfec=193.426/189.907 time=79.1091 tour=18 applybeta=25 basisbeta=9 |b1|=23263.5=6.55063GH logfec=191.711/189.907 time=83.1091 tour=19 applybeta=25 basisbeta=9 |b1|=23263.5=6.55063GH logfec=190.966/189.907 time=86.9881 tour=20 applybeta=25 basisbeta=9 |b1|=20132.9=5.66909GH logfec=190.255/189.907 time=90.9641 tour=21 applybeta=25 basisbeta=11 |b1|=20132.9=5.66909GH logfec=188.993/187.359 time=94.7084 tour=22 applybeta=25 basisbeta=11 |b1|=20132.9=5.66909GH logfec=188.242/187.359 time=98.682 tour=23 applybeta=25 basisbeta=11 |b1|=19021.5=5.35615GH logfec=187.641/187.359 progressive bkz finish. time=103.197 Strategied BKZ time=0.272848 tour=1 applybeta=59 basisbeta=21 |b1|=19021.5=5.35615GH logfec=186.278/184.942 time=42.7028 tour=2 applybeta=60 basisbeta=31 |b1|=17608.7=4.95834GH logfec=176.819/176.589 time=90.0197 tour=3 applybeta=61 basisbeta=40 |b1|=14705.6=4.14087GH logfec=169.09/167.947 progressive bkz finish. time=146.941 ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- ------------------------------------------BKZlib test10: Speed test (multithreads)------------------------------------------ max threads=8 used threads=4 ---------------------------------------------------------------------------------------------------------------------------- Benchmark for ENUM(single core,double precision, dim=100) processed_nodes=450000000 elapsed_time=6.466614 speed=69588196nodes/sec ---------------------------------------------------------------------------------------------------------------------------- Benchmark for ENUM(multicore(4),double precision, dim=100) processed_nodes=1050000000 elapsed_time=5.7212429 speed=1.8352655e+08nodes/sec ---------------------------------------------------------------------------------------------------------------------------- Benchmark for ENUM(single core,long double precision, dim=100) processed_nodes=220000000 elapsed_time=7.123019 speed=30885780/sec ---------------------------------------------------------------------------------------------------------------------------- Benchmark for ENUM(multicore(4),long double precision, dim=100) processed_nodes=480000000 elapsed_time=6.3526099 speed=75559496/sec ---------------------------------------------------------------------------------------------------------------------------- Benchmark for ENUM(single core,float15, dim=100) processed_nodes=6000000 elapsed_ime=3.7419319 speed=1603449.8/sec ---------------------------------------------------------------------------------------------------------------------------- Benchmark for ENUM(multicore(4),float15, dim=100) processed_nodes=16000000 elapsed_time=5.762531 speed=2776557.7/sec ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- -------------------------------BKZlib test11: Time simulation and solve SVP challenge dim=90-------------------------------- Time to find BKZ-45 basis in sec: 4.8173839 beta=45 M=1 cost=1777.0747 M=2 cost=1428.3118 M=4 cost=755.30133 M=8 cost=590.01277 M=16 cost=539.33896 M=32 cost=464.05957 M=64 cost=589.36077 M=24 tcost=412.6233 enumcost=4.3313387e+08 M=28 tcost=506.26696 enumcost=4.6422527e+08 M=20 tcost=453.16982 enumcost=6.2443875e+08 M=26 tcost=461.04928 enumcost=4.5203482e+08 M=22 tcost=572.55124 enumcost=7.4226853e+08 M=25 tcost=440.16144 enumcost=4.4761759e+08 M=23 tcost=519.94894 enumcost=6.2261821e+08 M=25 tcost=430.75484 enumcost=4.3444834e+08 Time to find BKZ-81 basis in sec: 647.60477 Time to find BKZ-63 basis in sec: 15.37591 beta=63 M=1 cost=309.5747 M=2 cost=193.09583 M=4 cost=179.50385 M=8 cost=220.6546 M=3 tcost=239.68306 enumcost=2.2581455e+09 M=6 tcost=222.45737 enumcost=7.5951116e+08 M=4 tcost=177.16357 enumcost=1.0120244e+09 Time to find BKZ-54 basis in sec: 8.0860524 beta=54 M=1 cost=692.31667 M=2 cost=455.5672 M=4 cost=344.66091 M=8 cost=270.24423 M=16 cost=288.62712 M=6 tcost=450.83109 enumcost=2.3468362e+09 M=12 tcost=254.74119 enumcost=4.599833e+08 M=10 tcost=250.26468 enumcost=5.9291456e+08 M=11 tcost=381.9997 enumcost=9.3244176e+08 M=9 tcost=242.87692 enumcost=6.6150952e+08 M=10 tcost=311.26713 enumcost=8.0642312e+08 Time to find BKZ-72 basis in sec: 81.002079 beta=72 M=1 cost=201.08356 M=2 cost=252.49696 Time to find BKZ-58 basis in sec: 10.375644 beta=58 M=1 cost=429.74633 M=2 cost=419.77424 M=4 cost=220.49414 M=8 cost=233.335 M=3 tcost=543.60976 enumcost=5.9789664e+09 M=6 tcost=639.00306 enumcost=3.3643703e+09 M=4 tcost=246.94983 enumcost=1.7976634e+09 Time to find BKZ-67 basis in sec: 26.669944 beta=67 M=1 cost=283.50685 M=2 cost=176.92338 M=4 cost=221.62705 M=2 tcost=198.24769 enumcost=2.5358865e+09 Time to find BKZ-65 basis in sec: 19.400303 beta=65 M=1 cost=211.67513 M=2 cost=471.47226 Time to find BKZ-69 basis in sec: 39.387885 beta=69 M=1 cost=234.49525 M=2 cost=174.72476 M=4 cost=222.69435 M=2 tcost=201.70487 enumcost=2.1512592e+09 Time to find BKZ-68 basis in sec: 32.228997 beta=68 M=1 cost=185.3183 M=2 cost=158.25218 M=4 cost=197.10543 M=2 tcost=170.99214 enumcost=1.8643477e+09 global_min=158.25218 Preprocess blocksize beta=68 Strategy: 20->(50)->28->(53)->38->(57)->48->(61)->58->(69)->68 cost=32.229 #bases=2 time=0.00228095 tour=1 applybeta=20 basisbeta=9 |b1|=8045.98=3.32685GH logfec=59.8589/47.7927 time=0.695449 tour=2 applybeta=20 basisbeta=9 |b1|=5310.3=2.1957GH logfec=53.6329/47.7927 time=1.10757 tour=3 applybeta=20 basisbeta=9 |b1|=4510.93=1.86518GH logfec=51.4048/47.7927 time=1.56015 tour=4 applybeta=20 basisbeta=9 |b1|=4472.07=1.84911GH logfec=50.288/47.7927 time=1.89111 tour=5 applybeta=20 basisbeta=9 |b1|=4372.51=1.80794GH logfec=49.0305/47.7927 time=2.23868 tour=6 applybeta=20 basisbeta=9 |b1|=4372.51=1.80794GH logfec=48.2989/47.7927 time=2.54727 tour=7 applybeta=20 basisbeta=11 |b1|=4186.98=1.73123GH logfec=47.7723/47.2908 time=2.85098 tour=8 applybeta=20 basisbeta=11 |b1|=3846.87=1.5906GH logfec=47.431/47.2908 progressive bkz finish. time=3.15231 time=0.00161004 tour=1 applybeta=50 basisbeta=21 |b1|=3846.87=1.5906GH logfec=47.1858/46.828 time=4.00271 tour=2 applybeta=57 basisbeta=41 |b1|=2956.97=1.22265GH logfec=43.5802/43.5537 time=10.245 tour=3 applybeta=61 basisbeta=50 |b1|=2956.97=1.22265GH logfec=42.2414/42.2053 time=18.8797 tour=4 applybeta=61 basisbeta=57 |b1|=2933.43=1.21291GH logfec=41.6138/41.6054 time=26.9281 tour=5 applybeta=69 basisbeta=62 |b1|=2869.88=1.18664GH logfec=41.1338/41.123 time=46.2886 tour=6 applybeta=69 basisbeta=67 |b1|=2665.29=1.10204GH logfec=40.7217/40.714 time=64.1966 tour=7 applybeta=69 basisbeta=67 |b1|=2665.29=1.10204GH logfec=40.7694/40.714 time=77.7315 tour=8 applybeta=69 basisbeta=65 |b1|=2665.29=1.10204GH logfec=40.8861/40.714 progressive bkz finish. time=95.9643 Start ENUM-SVP (initial radius=2539.42) Rigid_upper_bound=1.94165e+09 LatticeGH=2418.5 #nodes=1.68798Gnodes Time=25.2115 enum_speed=66.9529Mnodes/sec final_radius=2539.42 final_slide=6 Found Length=2569.3028=1.0623555*GH(L) time=0.00183916 tour=1 applybeta=50 basisbeta=9 |b1|=6550.7=2.70858GH logfec=59.8692/47.7927 time=6.34852 tour=2 applybeta=50 basisbeta=25 |b1|=4161.21=1.72058GH logfec=46.3609/46.2613 time=10.6221 tour=3 applybeta=57 basisbeta=44 |b1|=3386.92=1.40042GH logfec=42.9908/42.9754 time=17.7449 tour=4 applybeta=61 basisbeta=53 |b1|=2943.65=1.21714GH logfec=42.0196/41.9881 time=26.9992 tour=5 applybeta=69 basisbeta=58 |b1|=2688.14=1.11149GH logfec=41.5531/41.5027 progressive bkz finish. time=47.1082 Start ENUM-SVP (initial radius=2539.42) Rigid_upper_bound=1.90302e+09 LatticeGH=2418.5 #nodes=1.78595Gnodes Time=27.2608 enum_speed=65.5133Mnodes/sec final_radius=2539.42 final_slide=6 Found Length=2556.8535=1.057208*GH(L) time=1.44309 tour=1 applybeta=50 basisbeta=9 |b1|=5588.36=2.31068GH logfec=56.7071/47.7927 time=7.72554 tour=2 applybeta=53 basisbeta=28 |b1|=3850.63=1.59216GH logfec=45.825/45.7824 time=12.7401 tour=3 applybeta=57 basisbeta=45 |b1|=3116.2=1.28849GH logfec=42.8017/42.7503 time=18.9028 tour=4 applybeta=61 basisbeta=52 |b1|=2994.76=1.23828GH logfec=42.0591/42.0565 time=28.0275 tour=5 applybeta=69 basisbeta=59 |b1|=2994.76=1.23828GH logfec=41.4359/41.4031 progressive bkz finish. time=49.6572 Start ENUM-SVP (initial radius=2539.42) Rigid_upper_bound=2.8037e+09 LatticeGH=2418.5 #nodes=2.21508Gnodes Time=32.1408 enum_speed=68.9179Mnodes/sec final_radius=2539.42 final_slide=6 Found Length=2550.1751=1.0544466*GH(L) time=0.00118017 tour=1 applybeta=50 basisbeta=9 |b1|=5612.06=2.32047GH logfec=57.8571/47.7927 time=5.2163 tour=2 applybeta=53 basisbeta=28 |b1|=4240.41=1.75333GH logfec=46.0179/45.7824 time=11.372 tour=3 applybeta=61 basisbeta=48 |b1|=2857.33=1.18145GH logfec=42.3651/42.3631 time=23.33 tour=4 applybeta=69 basisbeta=58 |b1|=2857.33=1.18145GH logfec=41.5408/41.5027 time=43.8345 tour=5 applybeta=69 basisbeta=66 |b1|=2857.33=1.18145GH logfec=40.8025/40.7899 progressive bkz finish. time=57.8388 Start ENUM-SVP (initial radius=2539.42) Rigid_upper_bound=1.79502e+09 LatticeGH=2418.5 #nodes=1.09888Gnodes Time=16.9822 enum_speed=64.7075Mnodes/sec final_radius=2539.42 final_slide=6 Found Length=2587.2559=1.0697788*GH(L) time=0.00254297 tour=1 applybeta=50 basisbeta=9 |b1|=6146.83=2.54159GH logfec=60.4/47.7927 time=6.56758 tour=2 applybeta=50 basisbeta=22 |b1|=4399.29=1.81902GH logfec=46.6179/46.4535 time=11.5949 tour=3 applybeta=57 basisbeta=44 |b1|=3276.12=1.35461GH logfec=43.0792/42.9754 time=18.0594 tour=4 applybeta=61 basisbeta=53 |b1|=3079.06=1.27313GH logfec=42.0445/41.9881 time=27.8561 tour=5 applybeta=69 basisbeta=59 |b1|=3036.87=1.25569GH logfec=41.4293/41.4031 progressive bkz finish. time=52.5859 Start ENUM-SVP (initial radius=2539.42) Rigid_upper_bound=1.71699e+09 LatticeGH=2418.5 #nodes=1.45699Gnodes Time=22.365 enum_speed=65.146Mnodes/sec final_radius=2539.42 final_slide=6 Found Length=2523.706=1.0435022*GH(L) find vector: [551 3 55 -73 -126 -290 298 33 -216 75 -545 -149 -169 281 295 -95 492 -100 -71 -171 -468 246 -106 -194 321 49 -349 129 483 -121 182 -71 -162 175 205 364 -212 -437 -420 66 116 -338 -178 162 -233 -250 -547 233 -279 53 -47 271 -13 191 281 58 -339 -44 -341 133 -253 312 -315 -247 -104 -366 166 -18 -185 384 509 -99 -18 -189 -342 83 -61 70 -338 -221 -168 191 549 37 -217 27 172 -762 104 68] Length=2523.706=1.0435022*GH(L) ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- -------------------------------------------BKZlib test12: Solve LatticeChallenge-------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------Read file: challenge-600-------------------------------------------------- n=600 q=84 r=84 Extract last 200 vectors Table of |b*i|: [84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------Apply LLL---------------------------------------------------------- [84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 82.2314 78.603 78.6591 81.6287 83.07 ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------Apply PBKZ--------------------------------------------------------- reset processing range[1,200] -> [24,145] time=0.366424 tour=1 applybeta=40 basisbeta=9 |b1|=84=3.34659GH logfec=100.125/79.5092 reset processing range[1,200] -> [18,151] time=4.79656 tour=2 applybeta=40 basisbeta=9 |b1|=84=3.19911GH logfec=104.32/93.4381 reset processing range[1,200] -> [12,157] time=9.39071 tour=3 applybeta=40 basisbeta=9 |b1|=84=3.0696GH logfec=111.888/108.478 reset processing range[1,200] -> [9,163] time=14.327 tour=4 applybeta=40 basisbeta=21 |b1|=84=3.11287GH logfec=118.63/117.526 reset processing range[1,200] -> [5,169] time=19.7434 tour=5 applybeta=40 basisbeta=28 |b1|=84=3.0943GH logfec=127.852/127.498 reset processing range[1,200] -> [1,173] time=25.6908 tour=6 applybeta=40 basisbeta=32 |b1|=84=3.01476GH logfec=135.92/135.881 reset processing range[1,200] -> [1,175] time=33.2378 tour=7 applybeta=41 basisbeta=35 |b1|=84=3.07264GH logfec=136.567/136.216 reset processing range[1,200] -> [1,176] time=40.3614 tour=8 applybeta=43 basisbeta=37 |b1|=84=3.10142GH logfec=136.651/136.107 reset processing range[1,200] -> [1,178] time=48.1125 tour=9 applybeta=45 basisbeta=39 |b1|=84=3.15864GH logfec=137.971/137.715 reset processing range[1,200] -> [1,180] time=55.9024 tour=10 applybeta=48 basisbeta=42 |b1|=84=3.2154GH logfec=138.873/138.201 progressive bkz finish. time=64.5952 b1=[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 -2 -2 2 0 -13 0 4 2 4 5 4 10 2 1 2 -4 -1 0 0 -6 -15 3 -2 -3 6 0 1 8 1 -3 -2 -10 2 8 -1 -7 -5 4 2 3 -2 -2 12 -7 1 0 -3 6 1 -5 13 -12 4 -3 -8 -6 9 5 9 10 -11 12 5 9 2 5 1 15 -4 14 6 6 -3 4 7 10 4 -5 3 -5 -6 -13 4 0 3 -6 -1 -4 -2 7 -8 3 -1 2 4 9 8 -5 -8 -7 1 0 2 -6 0 1 7 4 1 2 -4 -5 0 10 7 6 2 -3 -3 1 7 8 -4 -2 1 3 2 5 -11 0 3 -9 0 7 -3 1 3 0 -6 3 -8 -7 4 -4 6 -7 -4 -11 -10 2 -6 1 0 -3 -4 -3 -8 12 4 18 -5 8 15 -12 -7 0] |b1|=79.868642 ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------BKZlib test13: Solve LWE Challenge--------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------Read file: LWE_40_005.txt-------------------------------------------------- n=40 m=1600 q=1601 alpha=0.005 dim(b)=1600 size(A)=1600,40 subdim=100 sigma=8.005 maxnorm of e=120.075 ---------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------Find basis vectors for A-------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------Apply PBKZ--------------------------------------------------------- time=0.00167394 tour=1 applybeta=15 basisbeta=9 |b1|=587.286=2.81812GH logfec=69.8009/56.8562 time=0.447755 tour=2 applybeta=15 basisbeta=9 |b1|=522.628=2.50786GH logfec=67.7615/56.8562 time=0.828855 tour=3 applybeta=15 basisbeta=9 |b1|=503.291=2.41507GH logfec=66.1906/56.8562 time=1.26099 tour=4 applybeta=15 basisbeta=9 |b1|=492.418=2.36289GH logfec=64.9362/56.8562 time=1.70471 tour=5 applybeta=15 basisbeta=9 |b1|=451.89=2.16842GH logfec=62.6282/56.8562 time=2.15255 tour=6 applybeta=15 basisbeta=9 |b1|=441.509=2.1186GH logfec=61.4815/56.8562 time=2.51867 tour=7 applybeta=15 basisbeta=9 |b1|=441.509=2.1186GH logfec=60.7815/56.8562 time=2.95999 tour=8 applybeta=15 basisbeta=9 |b1|=425.517=2.04187GH logfec=59.2832/56.8562 time=3.32199 tour=9 applybeta=15 basisbeta=9 |b1|=373.47=1.79212GH logfec=58.7843/56.8562 time=3.68406 tour=10 applybeta=15 basisbeta=9 |b1|=347.989=1.66984GH logfec=58.2748/56.8562 time=4.02753 tour=11 applybeta=15 basisbeta=9 |b1|=347.989=1.66984GH logfec=57.7683/56.8562 time=4.4017 tour=12 applybeta=15 basisbeta=9 |b1|=347.989=1.66984GH logfec=57.5359/56.8562 time=4.81363 tour=13 applybeta=15 basisbeta=9 |b1|=347.989=1.66984GH logfec=56.8662/56.8562 time=5.15829 tour=14 applybeta=17 basisbeta=11 |b1|=347.989=1.66984GH logfec=56.6795/56.2327 time=5.56748 tour=15 applybeta=17 basisbeta=11 |b1|=347.989=1.66984GH logfec=56.6387/56.2327 time=5.9627 tour=16 applybeta=25 basisbeta=19 |b1|=347.989=1.66984GH logfec=56.2256/56.1304 time=6.59206 tour=17 applybeta=28 basisbeta=22 |b1|=335.136=1.60817GH logfec=55.3783/55.1862 time=7.4527 tour=18 applybeta=31 basisbeta=25 |b1|=328.052=1.57417GH logfec=55.0891/54.9453 time=8.39008 tour=19 applybeta=34 basisbeta=28 |b1|=328.052=1.57417GH logfec=54.5399/54.3426 time=9.60039 tour=20 applybeta=38 basisbeta=32 |b1|=328.052=1.57417GH logfec=53.6019/53.4799 time=11.2305 tour=21 applybeta=41 basisbeta=35 |b1|=328.052=1.57417GH logfec=52.8763/52.7315 time=12.8955 tour=22 applybeta=45 basisbeta=39 |b1|=268.121=1.28659GH logfec=52.1392/51.9495 time=15.1199 tour=23 applybeta=48 basisbeta=42 |b1|=268.121=1.28659GH logfec=51.3153/51.2975 progressive bkz finish. time=17.7174 ---------------------------------------------------------------------------------------------------------------------------- -----------------------------------------------------Find close vector------------------------------------------------------ Start ENUM-CVP (initial radius=120.075) Rigid_upper_bound=4.23989e+06 LatticeGH=208.396 #nodes=0.00780924Gnodes Time=0.177604 enum_speed=43.97Mnodes/sec final_radius=120.075 final_slide=0 slot=0 proj=1 norm=8491(92.1466): -5726 344 -681 -273 8578 -3237 4773 -2633 -4760 -5009 5005 6015 -2532 2510 2028 37 -6043 - error candidate[1]: [17 -10 6 0 11 14 -5 -4 -9 3 -2 -2 -15 -1 -8 1 3 -3 2 -16 3 -5 -1 4 2 -1 -4 6 -5 -5 -15 13 -1 -2 -6 -11 13 12 -4 8 9 3 -4 10 -4 -12 10 -25 7 -8 -4 0 -6 9 -3 4 -3 4 10 -4 -3 -7 -2 5 0 2 -15 -18 -11 -2 7 -5 11 -1 -1 -9 4 1 21 -3 6 14 7 1 13 -19 3 -12 8 7 28 -7 -6 10 0 -17 14 -14 7 -12] norm[1]=92.146622 ---------------------------------------------------------------------------------------------------------------------------- -----------------------------Extract secret vector from error candidate by gaussian elimitation----------------------------- final solution s=[451 410 1055 253 1038 456 1300 406 1586 134 1260 5 454 1247 1069 800 444 199 1093 135 1175 676 1374 69 596 871 770 261 658 1575 657 1370 601 1492 913 516 138 623 35 1550 ] All tests have been finished. Total test time=1729.5558