Coverage for src\pqlattice\lattice\_reductions.py: 80%

1from fractions import Fraction 

2 

3import numpy as np 

4 

5from .._utils import as_integer 

6from ..typing import SquareMatrix, validate_aliases 

7from ._gso import gso, project_coeffs 

8 

9 

10@validate_aliases 

11def lll(lattice_basis: SquareMatrix, delta: float = 0.99) -> SquareMatrix: 

12 rows, _ = lattice_basis.shape 

13 B = as_integer(lattice_basis) 

14 while True: 

15 B_star, _ = gso(B) 

16 # Reduction Step 

17 for i in range(1, rows): 

18 for j in range(i - 1, -1, -1): 

19 c_ij = round(project_coeffs(B_star[j], B[i])) 

20 assert isinstance(c_ij, int) 

21 B[i] = B[i] - c_ij * B[j] 

22 # Swap step 

23 exists = False 

24 for i in range(rows - 1): 

25 u = project_coeffs(B_star[i], B[i + 1]) 

26 r = u * B_star[i] + B_star[i + 1] 

27 if delta * np.dot(B_star[i], B_star[i]) > np.dot(r, r): 

28 B[[i, i + 1]] = B[[i + 1, i]] 

29 exists = True 

30 break 

31 if not exists: 

32 break 

33 return B 

34 

35 

36@validate_aliases 

37def is_size_reduced(lattice_basis: SquareMatrix) -> bool: 

38 _, U = gso(lattice_basis) 

39 return bool(np.all(np.triu(U, 1) <= Fraction(1, 2))) 

40 

41 

42@validate_aliases 

43def lovasz_condition(lattice_basis: SquareMatrix, delta: float) -> bool: 

44 norm2 = lambda a: np.sum(a * a, axis=1) # type: ignore 

45 G, U = gso(lattice_basis) 

46 lhs = delta * norm2(G[:-1]) 

47 rhs = norm2(G[1:] + np.diag(U, 1)[:, np.newaxis] * G[:-1]) 

48 return bool(np.all(lhs <= rhs)) 

49 

50 

51@validate_aliases 

52def is_lll_reduced(lattice_basis: SquareMatrix, delta: float = 0.99) -> bool: 

53 return is_size_reduced(lattice_basis) and lovasz_condition(lattice_basis, delta)