Coverage for src\pqlattice\lattice\_bkz.py: 98%

1from .._utils import as_integer, as_rational 

2from ..typing import Matrix, SquareMatrix, Vector, validate_aliases 

3from ._gso import gso 

4from ._lll import lll 

5from ._svp import schnorr_euchner_svp 

6 

7 

8@validate_aliases 

9def update_block(lattice_basis: SquareMatrix, new_vector: Vector, start_index: int, block_size: int) -> SquareMatrix: 

10 B = as_integer(lattice_basis) 

11 local_basis = as_integer([new_vector] + B[start_index : start_index + block_size].tolist()) 

12 reduced_local = lll(local_basis) 

13 

14 zero_vec = reduced_local[0] 

15 if any(s != 0 for s in zero_vec): 

16 raise ValueError("block update failed") 

17 

18 cleaned_basis = as_integer(reduced_local[1:]) 

19 

20 for i in range(block_size): 

21 B[start_index + i] = cleaned_basis[i] 

22 

23 return B 

24 

25 

26@validate_aliases 

27def bkz(lattice_basis: SquareMatrix, block_size: int = 10) -> SquareMatrix: 

28 """_summary_ 

29 

30 Parameters 

31 ---------- 

32 lattice_basis : SquareMatrix 

33 _description_ 

34 block_size : int, optional 

35 _description_, by default 10 

36 

37 Returns 

38 ------- 

39 SquareMatrix 

40 _description_ 

41 """ 

42 n, m = lattice_basis.shape 

43 

44 B = lll(lattice_basis) 

45 

46 is_changed = True 

47 while is_changed: 

48 is_changed = False 

49 for k in range(n - 1): 

50 h = min(block_size, n - k) 

51 local_basis: Matrix = B[k : k + h] 

52 

53 B_star, U = gso(local_basis) 

54 B_norms2 = as_rational([sum(x * x for x in v) for v in B_star]) 

55 mu = U.T 

56 coeffs = schnorr_euchner_svp(mu, B_norms2) 

57 

58 is_trivial = True 

59 if abs(coeffs[0]) == 1: 

60 is_trivial = all(c == 0 for c in coeffs[1:]) 

61 elif coeffs[0] == 0: 

62 is_trivial = False 

63 else: 

64 is_trivial = False 

65 

66 if is_trivial: 

67 continue 

68 

69 new_vector = as_integer([0] * m) 

70 for i in range(h): 

71 if coeffs[i] == 0: 

72 continue 

73 for d in range(m): 

74 new_vector[d] += coeffs[i] * local_basis[i][d] 

75 

76 B = update_block(B, new_vector, k, h) 

77 is_changed = True 

78 return B