from fpylll import * from g6k import * from g6k.utils.stats import SieveTreeTracer from g6k.algorithms.bkz import pump_n_jump_bkz_tour from fpylll.util import gaussian_heuristic from math import sqrt #FPLLL.set_random_seed(1337) #------------------------------------------------------- # SVP #------------------------------------------------------- """ n = 60 A = IntegerMatrix.random(n, "qary", k=30, bits=30) g6k = Siever(A, seed=0x1337) # g6k has its own seed g6k.initialize_local(0, 0, n) # sieve the entire basis g6k(alg="bgj1") #alg \in {"nv", "gauss", "hk3"} v = g6k.best_lifts()[0][2] print('best lifts', g6k.best_lifts()) w = A.multiply_left(v) # w = v*A print('norms:', sum(w_**2 for w_ in w), A[0].norm()**2) """ #------------------------------------------------------- # Simulate BKZ #------------------------------------------------------- """ n = 60 A = IntegerMatrix.random(n, "qary", k=30, bits=30) g6k = Siever(A, seed=0x1337) # g6k has its own seed g6k.initialize_local(0, 0, n) sp = g6k.params.new() sp.threads = 1 #g6k(alg="bgj1") tracer = SieveTreeTracer(g6k, root_label=("bgj1"), start_clocks=True) for b in (20, 30, 40, 50, 60): # progressive BKZ pump_n_jump_bkz_tour(g6k, tracer, b, pump_params={"down_sieve": True}) print(b, A[0].norm()**2) """ #------------------------------------------------------- # many short vectors #------------------------------------------------------- n = 44 A = IntegerMatrix.random(n, "qary", k=n/2, bits=10) g6k = Siever(A) g6k.lll(0, n) # Run a progressive sieve (preprocessing) g6k.initialize_local(0, n/2, n) while g6k.l > 0: # Extend the lift context to the left g6k.extend_left(1) # Sieve g6k() with g6k.temp_params(saturation_ratio=.95, saturation_radius=1.4, db_size_base=sqrt(1.7), db_size_factor=3): g6k() gh = gaussian_heuristic([g6k.M.get_r(i, i) for i in range(n)]) db = list(g6k.itervalues()) found = 0 for x in db: v = A.multiply_left(x) l = sum(v_**2 for v_ in v) if l < 1.2 * gh: print(l/gh, v) found += 1