1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
# -*- coding: utf-8 -*-
from fpylll import Enumeration, GSO, IntegerMatrix, LLL, Pruning
from fpylll.util import gaussian_heuristic
try:
from time import process_time # Python 3
except ImportError:
from time import clock as process_time # Python 2
dim_oh = ((40, 2**22), (41, 2**22), (50, 2**24), (51, 2**24))
def prepare(n):
A = IntegerMatrix.random(n, "qary", bits=n/2, k=n/2)
M = GSO.Mat(A)
L = LLL.Reduction(M)
L()
return M
def test_pruner():
# A dummyPruningParams.run to load tabulated values
Pruning.run(5, 50, 10*[1.], .5)
for (n, overhead) in dim_oh:
print(" \n ~~~~ Dim %d \n" % n)
M = prepare(n)
r = [M.get_r(i, i) for i in range(n)]
print(" \n GREEDY")
radius = gaussian_heuristic(r) * 1.6
print("pre-greedy radius %.4e" % radius)
tt = process_time()
pruning =Pruning.run(radius, overhead, r, 200, flags=Pruning.ZEALOUS, metric="solutions")
print("Time %.4e"%(process_time() - tt))
print("post-greedy radius %.4e" % radius)
print(pruning)
print("cost %.4e" % sum(pruning.detailed_cost))
solutions = Enumeration(M, nr_solutions=10000).enumerate(0, n, radius, 0, pruning=pruning.coefficients)
print(len(solutions))
assert len(solutions)/pruning.expectation < 2
assert len(solutions)/pruning.expectation > .2
print(" \n GRADIENT \n")
print("radius %.4e" % radius)
tt = process_time()
pruning = Pruning.run(radius, overhead, r, 200, flags=Pruning.GRADIENT, metric="solutions")
print("Time %.4e"%(process_time() - tt))
print(pruning)
print("cost %.4e" % sum(pruning.detailed_cost))
solutions = Enumeration(M, nr_solutions=10000).enumerate(0, n, radius, 0, pruning=pruning.coefficients)
print(len(solutions))
assert len(solutions)/pruning.expectation < 2
assert len(solutions)/pruning.expectation > .2
print(" \n HYBRID \n")
print("radius %.4e" % radius)
tt = process_time()
pruning = Pruning.run(radius, overhead, r, 200, flags=Pruning.ZEALOUS, metric="solutions")
print("Time %.4e"%(process_time() - tt))
print(pruning)
print("cost %.4e" % sum(pruning.detailed_cost))
solutions = Enumeration(M, nr_solutions=10000).enumerate(0, n, radius, 0, pruning=pruning.coefficients)
print(len(solutions))
assert len(solutions)/pruning.expectation < 2
assert len(solutions)/pruning.expectation > .2
|
