Coverage for src\pqlattice\lattice\_gso.py: 100%

1from fractions import Fraction 

2 

3import numpy as np 

4 

5from .._utils import as_rational 

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

7 

8 

9@validate_aliases 

10def project_coeffs(q: Vector, b: Vector) -> Fraction: 

11 if np.dot(q, q) == 0: 

12 return Fraction(0, 1) 

13 

14 return np.dot(b, q) / np.dot(q, q) 

15 

16 

17@validate_aliases 

18def gso(B: Matrix) -> tuple[Matrix, SquareMatrix]: 

19 """_summary_ 

20 

21 Parameters 

22 ---------- 

23 B : Matrix 

24 _description_ 

25 

26 Returns 

27 ------- 

28 tuple[Matrix, SquareMatrix] 

29 _description_ 

30 """ 

31 rows, _ = B.shape 

32 

33 B_star: Matrix = as_rational(B) 

34 U: SquareMatrix = as_rational(np.identity(rows)) 

35 

36 for j in range(1, rows): 

37 b: Vector = B_star[j].copy() 

38 for i in range(j): 

39 U[i, j] = project_coeffs(B_star[i], b) 

40 B_star[j] -= U[i][j] * B_star[i] 

41 

42 # B = U.T @ B_star 

43 return B_star, U