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 ._linalg import cofactor_matrix, det 

7from ._utils import row_add, row_scale, row_swap 

8 

9 

10@validate_aliases 

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

12 """_summary_ 

13 

14 Parameters 

15 ---------- 

16 A : Matrix 

17 _description_ 

18 modulus : int 

19 _description_ 

20 

21 Returns 

22 ------- 

23 tuple[Matrix, SquareMatrix] 

24 _description_ 

25 """ 

26 R = ModIntRing(modulus) 

27 m, n = A.shape 

28 

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

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

31 

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

33 col = M[:, j] 

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

35 if len(nonzero) == 0: 

36 # no pivot, in this column 

37 continue 

38 pivot_i = nonzero[0] + j 

39 

40 if pivot_i != j: 

41 row_swap(M, pivot_i, j) 

42 row_swap(U, pivot_i, j) 

43 

44 pivot: int = M[j, j] 

45 pivot_inv = R.inv(pivot) 

46 row_scale(M, j, pivot_inv) 

47 row_scale(U, j, pivot_inv) 

48 

49 M = R.mod(M) 

50 U = R.mod(U) 

51 

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

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

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

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

56 M = R.mod(M) 

57 U = R.mod(U) 

58 

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

60 

61 

62@validate_aliases 

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

64 """_summary_ 

65 

66 Parameters 

67 ---------- 

68 A : Matrix 

69 _description_ 

70 modulus : int 

71 _description_ 

72 

73 Returns 

74 ------- 

75 tuple[Matrix, SquareMatrix] 

76 _description_ 

77 """ 

78 R = ModIntRing(modulus) 

79 m, n = A.shape 

80 M, U = mod_ref(A, modulus) 

81 

82 h = m - 1 

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

84 # check if current column is a pivot column 

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

86 # skip zero rows at the bottom 

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

88 h -= 1 

89 continue 

90 

91 # reduce column's entries below pivot 

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

93 coeff = M[i, j] 

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

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

96 

97 # move to the next row 

98 h -= 1 

99 

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

101 

102 

103@validate_aliases 

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

105 """_summary_ 

106 

107 Parameters 

108 ---------- 

109 A : Matrix 

110 _description_ 

111 modulus : int 

112 _description_ 

113 

114 Returns 

115 ------- 

116 Matrix 

117 _description_ 

118 """ 

119 return mod_right_kernel(A.T, modulus) 

120 

121 

122@validate_aliases 

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

124 """_summary_ 

125 

126 Parameters 

127 ---------- 

128 A : Matrix 

129 _description_ 

130 modulus : int 

131 _description_ 

132 

133 Returns 

134 ------- 

135 Matrix 

136 _description_ 

137 """ 

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

139 kernel_basis: list[Vector] = [] 

140 

141 m, _ = M.shape 

142 for i in range(m): 

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

144 kernel_basis.append(U[i]) 

145 

146 return as_integer(kernel_basis) 

147 

148 

149@validate_aliases 

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

151 """_summary_ 

152 

153 Parameters 

154 ---------- 

155 A : Matrix 

156 _description_ 

157 modulus : int 

158 _description_ 

159 

160 Returns 

161 ------- 

162 int 

163 _description_ 

164 """ 

165 kernel = mod_left_kernel(A, modulus) 

166 return kernel.shape[0] 

167 

168 

169@validate_aliases 

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

171 """_summary_ 

172 

173 Parameters 

174 ---------- 

175 A : Matrix 

176 _description_ 

177 modulus : int 

178 _description_ 

179 

180 Returns 

181 ------- 

182 int 

183 _description_ 

184 """ 

185 kernel = mod_right_kernel(A, modulus) 

186 return kernel.shape[0] 

187 

188 

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

190 """_summary_ 

191 

192 Parameters 

193 ---------- 

194 A : SquareMatrix 

195 _description_ 

196 modulus : int 

197 _description_ 

198 

199 Returns 

200 ------- 

201 SquareMatrix 

202 _description_ 

203 """ 

204 R = ModIntRing(modulus) 

205 C = R.mod(cofactor_matrix(A)) 

206 det_inv = R.inv(det(A)) 

207 return R.mod(det_inv * C.T)