Coverage for src/pqlattice/lattice/_lll.py: 80%

1from fractions import Fraction 

2 

3import numpy as np 

4 

5from .._utils import as_integer 

6from ..typing import Matrix, SquareMatrix, validate_aliases 

7from ._gso import gso, project_coeffs 

8 

9 

10@validate_aliases 

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

12 """_summary_ 

13 

14 Parameters 

15 ---------- 

16 lattice_basis : Matrix 

17 _description_ 

18 delta : float, optional 

19 _description_, by default 0.99 

20 

21 Returns 

22 ------- 

23 Matrix 

24 _description_ 

25 """ 

26 rows, _ = lattice_basis.shape 

27 B: Matrix = as_integer(lattice_basis) 

28 while True: 

29 B_star, _ = gso(B) 

30 # Reduction Step 

31 for i in range(1, rows): 

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

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

34 assert isinstance(c_ij, int) 

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

36 # Swap step 

37 exists = False 

38 for i in range(rows - 1): 

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

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

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

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

43 exists = True 

44 break 

45 if not exists: 

46 break 

47 return B 

48 

49 

50@validate_aliases 

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

52 """_summary_ 

53 

54 Parameters 

55 ---------- 

56 lattice_basis : SquareMatrix 

57 _description_ 

58 

59 Returns 

60 ------- 

61 bool 

62 _description_ 

63 """ 

64 _, U = gso(lattice_basis) 

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

66 

67 

68@validate_aliases 

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

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

71 G, U = gso(lattice_basis) 

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

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

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

75 

76 

77@validate_aliases 

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

79 """_summary_ 

80 

81 Parameters 

82 ---------- 

83 lattice_basis : SquareMatrix 

84 _description_ 

85 delta : float, optional 

86 _description_, by default 0.99 

87 

88 Returns 

89 ------- 

90 bool 

91 _description_ 

92 """ 

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