Coverage for src\pqlattice\_backends\_fast.py: 53%

1from typing import Any, override 

2 

3from .._utils import as_integer 

4from ..typing import Array, Matrix, SquareMatrix, Vector 

5from ._protocol import BackendInterface 

6 

7try: 

8 import fpylll 

9 

10 HAS_FPYLLL = True 

11except ImportError: 

12 HAS_FPYLLL = False 

13 

14try: 

15 import flint 

16 

17 HAS_FLINT = True 

18except ImportError: 

19 HAS_FLINT = False 

20 

21 

22class FastBackend(BackendInterface): 

23 def __init__(self) -> None: 

24 if not (HAS_FPYLLL and HAS_FLINT): 

25 raise RuntimeError("Fast backend is unavailable - dependencies missing") 

26 

27 def _to_fpylll(self, a: Array) -> Any: 

28 return fpylll.IntegerMatrix.from_matrix(a.tolist()) 

29 

30 def _from_fpylll(self, mat: Any) -> Array: 

31 data = [list(row) for row in mat] 

32 return as_integer(data) 

33 

34 def _to_flint(self, a: Array) -> Any: 

35 return flint.fmpz_mat(a.tolist()) 

36 

37 def _from_flint(self, mat: Any) -> Array: 

38 return as_integer(mat.table()) 

39 

40 @override 

41 def lll(self, lattice_basis: SquareMatrix, delta: float) -> SquareMatrix: 

42 mat = self._to_fpylll(lattice_basis) 

43 fpylll.LLL.reduction(mat, delta=delta) 

44 return self._from_fpylll(mat) 

45 

46 @override 

47 def bkz(self, lattice_basis: SquareMatrix, block_size: int, delta: float) -> SquareMatrix: 

48 mat = self._to_fpylll(lattice_basis) 

49 # fpylll.BKZ.reduction(mat, delta=delta) 

50 mat_bkz = fpylll.BKZ.reduction(mat, fpylll.BKZ.Param(block_size=block_size)) 

51 return self._from_fpylll(mat_bkz) 

52 

53 @override 

54 def hkz(self, lattice_basis: SquareMatrix, delta: float) -> SquareMatrix: 

55 return self.bkz(lattice_basis, len(lattice_basis), delta) 

56 

57 @override 

58 def shortest_vector(self, lattice_basis: SquareMatrix) -> Vector: 

59 mat = self._to_fpylll(lattice_basis) 

60 fpylll.LLL.reduction(mat) 

61 sv = fpylll.SVP.shortest_vector(mat, pruning=False, preprocess=False) 

62 return as_integer(sv) 

63 

64 @override 

65 def closest_vector(self, lattice_basis: SquareMatrix, target_vector: Vector) -> Vector: 

66 A = self._from_fpylll(lattice_basis) 

67 t = target_vector.tolist() 

68 v0 = fpylll.CVP.closest_vector(A, t) 

69 return as_integer(v0) 

70 

71 @override 

72 def hnf(self, matrix: Matrix) -> tuple[Matrix, SquareMatrix]: 

73 mat = self._to_flint(matrix) 

74 H, U = mat.hnf(transform=True) 

75 return self._from_flint(H), self._from_flint(U)