Coverage for src/pqlattice/lattice/_svp.py: 100%

1from fractions import Fraction 

2 

3from .._utils import as_integer, as_rational 

4from ..typing import SquareMatrix, Vector, validate_aliases 

5from ._gso import gso 

6from ._lll import lll 

7 

8 

9@validate_aliases 

10def schnorr_euchner_svp(mu: SquareMatrix, B: Vector) -> Vector: 

11 n = len(B) 

12 best_norm: Fraction = B[0] 

13 best_coeffs: Vector = as_integer([1] + [0] * (n - 1)) 

14 

15 r: Vector = as_rational([0] * (n + 1)) 

16 c: Vector = as_rational([0] * n) 

17 x: Vector = as_integer([0] * n) 

18 v: Vector = as_rational([0] * n) 

19 

20 last_move = [0] * n 

21 k = n - 1 

22 

23 r[n] = Fraction(0) 

24 v[n - 1] = Fraction(0) 

25 c[n - 1] = Fraction(0) 

26 x[n - 1] = 0 

27 last_move[n - 1] = 0 

28 

29 while True: 

30 y: Fraction = x[k] - c[k] 

31 current_norm: Fraction = r[k + 1] + (y * y * B[k]) 

32 # print(f"{k=}: {current_norm=:.5f}, {best_norm=:.5f}") 

33 if current_norm < best_norm: 

34 if k == 0: 

35 if current_norm > 0: 

36 best_norm = current_norm 

37 best_coeffs = x.copy() 

38 

39 k += 1 

40 last_move[k] += 1 

41 

42 step_sign = -1 if (last_move[k] % 2 == 0) else 1 

43 step_mag = (last_move[k] + 1) // 2 

44 x[k] = round(c[k]) + (step_sign * step_mag) 

45 

46 else: 

47 k -= 1 

48 center_val = Fraction(0) 

49 for j in range(k + 1, n): 

50 center_val += mu[j][k] * x[j] 

51 

52 c[k] = -center_val 

53 x[k] = round(c[k]) 

54 last_move[k] = 0 

55 r[k + 1] = current_norm 

56 else: 

57 k += 1 

58 if k == n: 

59 break 

60 

61 last_move[k] += 1 

62 step_sign = -1 if (last_move[k] % 2 == 0) else 1 

63 step_mag = (last_move[k] + 1) // 2 

64 

65 x[k] = round(c[k]) + (step_sign * step_mag) 

66 

67 return best_coeffs 

68 

69 

70@validate_aliases 

71def shortest_vector(lattice_basis: SquareMatrix) -> Vector: 

72 """_summary_ 

73 

74 Parameters 

75 ---------- 

76 lattice_basis : SquareMatrix 

77 _description_ 

78 

79 Returns 

80 ------- 

81 Vector 

82 _description_ 

83 """ 

84 B = lll(lattice_basis) 

85 B_star, U = gso(B) 

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

87 mu = U.T 

88 coeffs = schnorr_euchner_svp(mu, B_norms2) 

89 return coeffs @ B