Coverage for src\pqlattice\lattice\_embeddings.py: 34%
41 statements
« prev ^ index » next coverage.py v7.11.0, created at 2026-01-10 12:32 +0100
1import numpy as np
3from .._utils import as_integer, zeros_mat
4from ..linalg import hnf
5from ..typing import Matrix, SquareMatrix, Vector, validate_aliases
8def lwe_basis(A: Matrix, q: int) -> SquareMatrix:
9 """
10 _summary_
12 Parameters
13 ----------
14 A : Matrix
15 _description_
16 q : int
17 _description_
19 Returns
20 -------
21 SquareMatrix
22 _description_
23 """
24 # lattice: L = { x | Ax = 0 mod q }
25 m, _ = A.shape
26 Im = q * as_integer(np.identity(m))
27 G = np.vstack((A.T, Im))
28 H, _ = hnf(G)
30 return H[:m]
33def sis_basis(A: Matrix, q: int) -> SquareMatrix:
34 """
35 _summary_
37 Parameters
38 ----------
39 A : Matrix
40 _description_
41 q : int
42 _description_
44 Returns
45 -------
46 SquareMatrix
47 _description_
48 """
49 # lattice: L = { y | y = xA mod q }
50 B_p = lwe_basis(A, q)
51 B_inv = np.linalg.inv(B_p.astype(float))
52 B_dual = np.round(q * B_inv.T).astype(int)
53 return B_dual
56@validate_aliases
57def kannan(A: Matrix, b: Vector, q: int) -> SquareMatrix:
58 """
59 _summary_
61 Parameters
62 ----------
63 A : Matrix
64 _description_
65 b : Vector
66 _description_
67 q : int
68 _description_
70 Returns
71 -------
72 SquareMatrix
73 _description_
74 """
75 return bai_galbraith(A, b, q, 1)
78@validate_aliases
79def bai_galbraith(A: Matrix, b: Vector, q: int, M: int) -> SquareMatrix:
80 """
81 _summary_
83 Parameters
84 ----------
85 A : Matrix
86 _description_
87 b : Vector
88 _description_
89 q : int
90 _description_
91 M : int
92 _description_
94 Returns
95 -------
96 SquareMatrix
97 _description_
98 """
99 m, n = A.shape
101 Im = as_integer(np.identity(m))
102 In = as_integer(np.identity(n))
104 Zmxn = zeros_mat(m, n)
105 Zmx1 = zeros_mat(m, 1)
106 Znx1 = zeros_mat(n, 1)
107 Z1xn = zeros_mat(1, n)
109 bT = b.reshape(1, -1)
110 IM = M * (zeros_mat(1, 1) + 1)
112 return np.block(
113 [
114 [q * Im, Zmxn, Zmx1],
115 [A.T, In, Znx1],
116 [-bT, Z1xn, IM],
117 ]
118 )
121@validate_aliases
122def subset_sum(sequence: Vector, S: int) -> SquareMatrix:
123 """
124 _summary_
126 Parameters
127 ----------
128 sequence : Vector
129 _description_
130 S : int
131 _description_
133 Returns
134 -------
135 SquareMatrix
136 _description_
137 """
138 n = len(sequence)
139 A = as_integer(np.identity(n + 1) * 2)
140 A[-1] = 1
141 A[:-1, -1] = sequence
142 A[-1, -1] = S
144 return A
147@validate_aliases
148def ntru() -> SquareMatrix:
149 raise NotImplementedError()