Coverage for src\pqlattice\random\_lattice.py: 100%

1import random 

2 

3import numpy as np 

4 

5from .._utils import as_integer, zeros_mat 

6from ..typing import SquareMatrix 

7 

8 

9def _gen_unimodular(n: int, rounds: int, rng: random.Random) -> SquareMatrix: 

10 U = as_integer(np.eye(n)) 

11 for _ in range(rounds): 

12 i, j = rng.sample(range(n), 2) 

13 coeff = rng.sample([-1, 1], 1) 

14 

15 U[i] += coeff * U[j] 

16 

17 return U 

18 

19 

20def randlattice(n: int, det_upper_bound: int | None = None, seed: int | None = None) -> SquareMatrix: 

21 """ 

22 Generates lattice basis by, first generating random square matrix in Hermite normal form and then by transforming it using random unimodular matrix. 

23 

24 Parameters 

25 ---------- 

26 n : int 

27 lattice's rank 

28 det_upper_bound : int | None, optional 

29 upper bound of lattice volume, by default 2 ** n 

30 seed : int | None, optional 

31 seed for random number generator 

32 

33 Returns 

34 ------- 

35 SquareMatrix 

36 n x n matrix representing lattice basis 

37 """ 

38 det_ub: int = 2**n if det_upper_bound is None else det_upper_bound 

39 

40 rng = random.Random(seed) 

41 diagonals = [rng.randint(1, det_ub) for _ in range(n)] 

42 

43 H = zeros_mat(n) 

44 for i in range(n): 

45 H[i, i] = diagonals[i] 

46 modulus = H[i, i] 

47 for j in range(i + 1, n): 

48 H[i, j] = rng.randint(0, modulus - 1) 

49 

50 U = _gen_unimodular(n, n * 5, rng) 

51 

52 basis = U @ H 

53 return basis