Coverage for src\pqlattice\linalg\_modint.py: 25%

1import numpy as np 

2 

3from .._utils import as_integer 

4from ..integer._modintring import ModIntRing 

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

6from ._utils import row_add, row_scale, row_swap 

7 

8 

9@validate_aliases 

10def mod_ref(A: Matrix, modulus: int) -> tuple[Matrix, SquareMatrix]: 

11 """_summary_ 

12 

13 Parameters 

14 ---------- 

15 A : Matrix 

16 _description_ 

17 modulus : int 

18 _description_ 

19 

20 Returns 

21 ------- 

22 tuple[Matrix, SquareMatrix] 

23 _description_ 

24 """ 

25 R = ModIntRing(modulus) 

26 m, n = A.shape 

27 

28 M = R.mod(as_integer(A)) 

29 U = as_integer(np.identity(m)) 

30 

31 for j in range(min(m, n)): 

32 col = M[:, j] 

33 nonzero = np.nonzero(col[j:])[0] 

34 if len(nonzero) == 0: 

35 continue 

36 pivot_i = nonzero[0] + j 

37 

38 if pivot_i != j: 

39 row_swap(M, pivot_i, j) 

40 row_swap(U, pivot_i, j) 

41 

42 pivot: int = M[j, j] 

43 pivot_inv = R.inv(pivot) 

44 row_scale(M, j, pivot_inv) 

45 row_scale(U, j, pivot_inv) 

46 

47 M = R.mod(M) 

48 U = R.mod(U) 

49 

50 for i in range(j + 1, m): 

51 if M[i, j] != 0: 

52 row_add(U, i, j, -M[i, j]) 

53 row_add(M, i, j, -M[i, j]) 

54 M = R.mod(M) 

55 U = R.mod(U) 

56 

57 return R.mod(M), R.mod(U) 

58 

59 

60@validate_aliases 

61def mod_rref(A: Matrix, modulus: int) -> tuple[Matrix, SquareMatrix]: 

62 """_summary_ 

63 

64 Parameters 

65 ---------- 

66 A : Matrix 

67 _description_ 

68 modulus : int 

69 _description_ 

70 

71 Returns 

72 ------- 

73 tuple[Matrix, SquareMatrix] 

74 _description_ 

75 """ 

76 R = ModIntRing(modulus) 

77 m, n = A.shape 

78 M, U = mod_ref(A, modulus) 

79 

80 h = m - 1 

81 for j in range(n - 1, -1, -1): 

82 if M[h, j] != 1: 

83 if M[h, j] == 0: 

84 h -= 1 

85 continue 

86 

87 for i in range(h - 1, -1, -1): 

88 coeff = M[i, j] 

89 row_add(M, i, h, -coeff) 

90 row_add(U, i, h, -coeff) 

91 

92 h -= 1 

93 

94 return R.mod(M), R.mod(U) 

95 

96 

97@validate_aliases 

98def mod_left_kernel(A: Matrix, modulus: int) -> Matrix: 

99 """_summary_ 

100 

101 Parameters 

102 ---------- 

103 A : Matrix 

104 _description_ 

105 modulus : int 

106 _description_ 

107 

108 Returns 

109 ------- 

110 Matrix 

111 _description_ 

112 """ 

113 return mod_right_kernel(A.T, modulus) 

114 

115 

116@validate_aliases 

117def mod_right_kernel(A: Matrix, modulus: int) -> Matrix: 

118 """_summary_ 

119 

120 Parameters 

121 ---------- 

122 A : Matrix 

123 _description_ 

124 modulus : int 

125 _description_ 

126 

127 Returns 

128 ------- 

129 Matrix 

130 _description_ 

131 """ 

132 M, U = mod_rref(A.T, modulus) 

133 kernel_basis: list[Vector] = [] 

134 

135 m, _ = M.shape 

136 for i in range(m): 

137 if np.all(M[i] == 0): 

138 kernel_basis.append(U[i]) 

139 

140 return as_integer(kernel_basis) 

141 

142 

143def mod_left_image(A: Matrix, modulus: int) -> Matrix: 

144 raise NotImplementedError() 

145 

146 

147def mod_right_image(A: Matrix, modulus: int) -> Matrix: 

148 raise NotImplementedError() 

149 

150 

151@validate_aliases 

152def mod_left_nullity(A: Matrix, modulus: int) -> int: 

153 """_summary_ 

154 

155 Parameters 

156 ---------- 

157 A : Matrix 

158 _description_ 

159 modulus : int 

160 _description_ 

161 

162 Returns 

163 ------- 

164 int 

165 _description_ 

166 """ 

167 kernel = mod_left_kernel(A, modulus) 

168 return kernel.shape[0] 

169 

170 

171@validate_aliases 

172def mod_right_nullity(A: Matrix, modulus: int) -> int: 

173 """_summary_ 

174 

175 Parameters 

176 ---------- 

177 A : Matrix 

178 _description_ 

179 modulus : int 

180 _description_ 

181 

182 Returns 

183 ------- 

184 int 

185 _description_ 

186 """ 

187 kernel = mod_right_kernel(A, modulus) 

188 return kernel.shape[0] 

189 

190 

191def mod_matinv(A: SquareMatrix, modulus: int) -> SquareMatrix: 

192 """_summary_ 

193 

194 Parameters 

195 ---------- 

196 A : SquareMatrix 

197 _description_ 

198 modulus : int 

199 _description_ 

200 

201 Returns 

202 ------- 

203 SquareMatrix 

204 _description_ 

205 """ 

206 n = A.shape[0] 

207 AId = np.hstack((A, as_integer(np.identity(n)))) 

208 R, _ = mod_rref(AId, modulus) 

209 return as_integer(R[:, n:])