Coverage for src/pqlattice/polynomial/_modpolyring.py: 61%

1from ..integer._modring import mod, modinv 

2from ..typing import Vector, validate_aliases 

3from . import _poly as poly 

4 

5 

6class ModIntPolyRing: 

7 def __init__(self, modulus: int): 

8 """_summary_ 

9 

10 Parameters 

11 ---------- 

12 modulus : int 

13 _description_ 

14 

15 Raises 

16 ------ 

17 ValueError 

18 _description_ 

19 """ 

20 if modulus <= 1: 

21 raise ValueError("Modulus has to be greater than 1") 

22 

23 self.modulus = modulus 

24 

25 @validate_aliases 

26 def reduce(self, polynomial: Vector) -> Vector: 

27 """_summary_ 

28 

29 Parameters 

30 ---------- 

31 polynomial : Vector 

32 _description_ 

33 

34 Returns 

35 ------- 

36 Vector 

37 _description_ 

38 """ 

39 return poly.trim(mod(polynomial, self.modulus)) 

40 

41 @validate_aliases 

42 def is_zero(self, polynomial: Vector) -> bool: 

43 """_summary_ 

44 

45 Parameters 

46 ---------- 

47 polynomial : Vector 

48 _description_ 

49 

50 Returns 

51 ------- 

52 bool 

53 _description_ 

54 """ 

55 return poly.is_zero_poly(self.reduce(polynomial)) 

56 

57 @validate_aliases 

58 def deg(self, polynomial: Vector) -> int: 

59 """_summary_ 

60 

61 Parameters 

62 ---------- 

63 polynomial : Vector 

64 _description_ 

65 

66 Returns 

67 ------- 

68 int 

69 _description_ 

70 """ 

71 return poly.deg(self.reduce(polynomial)) 

72 

73 @validate_aliases 

74 def add(self, polynomial_a: Vector, polynomial_b: Vector) -> Vector: 

75 """_summary_ 

76 

77 Parameters 

78 ---------- 

79 polynomial_a : Vector 

80 _description_ 

81 polynomial_b : Vector 

82 _description_ 

83 

84 Returns 

85 ------- 

86 Vector 

87 _description_ 

88 """ 

89 return self.reduce(poly.add(polynomial_a, polynomial_b)) 

90 

91 @validate_aliases 

92 def sub(self, polynomial_a: Vector, polynomial_b: Vector) -> Vector: 

93 """_summary_ 

94 

95 Parameters 

96 ---------- 

97 polynomial_a : Vector 

98 _description_ 

99 polynomial_b : Vector 

100 _description_ 

101 

102 Returns 

103 ------- 

104 Vector 

105 _description_ 

106 """ 

107 return self.reduce(poly.sub(polynomial_a, polynomial_b)) 

108 

109 @validate_aliases 

110 def mul(self, polynomial_a: Vector, polynomial_b: Vector) -> Vector: 

111 """_summary_ 

112 

113 Parameters 

114 ---------- 

115 polynomial_a : Vector 

116 _description_ 

117 polynomial_b : Vector 

118 _description_ 

119 

120 Returns 

121 ------- 

122 Vector 

123 _description_ 

124 """ 

125 return self.reduce(poly.mul(polynomial_a, polynomial_b)) 

126 

127 @validate_aliases 

128 def euclidean_div(self, polynomial_a: Vector, polynomial_b: Vector) -> tuple[Vector, Vector]: 

129 """_summary_ 

130 

131 Parameters 

132 ---------- 

133 polynomial_a : Vector 

134 _description_ 

135 polynomial_b : Vector 

136 _description_ 

137 

138 Returns 

139 ------- 

140 tuple[Vector, Vector] 

141 _description_ 

142 

143 Raises 

144 ------ 

145 ZeroDivisionError 

146 _description_ 

147 """ 

148 if self.is_zero(polynomial_b): 

149 raise ZeroDivisionError("Can't divide by zero polynomial") 

150 

151 q = poly.zero_poly() 

152 r = self.reduce(polynomial_a) 

153 

154 d = self.deg(polynomial_b) 

155 c: int = polynomial_b[d] 

156 while (dr := self.deg(r)) >= d: 

157 s = poly.monomial(r[dr] * modinv(c, self.modulus), dr - d) 

158 q = self.add(q, s) 

159 r = self.sub(r, self.mul(s, polynomial_b)) 

160 

161 return q, r 

162 

163 @validate_aliases 

164 def rem(self, polynomial_a: Vector, polynomial_b: Vector) -> Vector: 

165 """_summary_ 

166 

167 Parameters 

168 ---------- 

169 polynomial_a : Vector 

170 _description_ 

171 polynomial_b : Vector 

172 _description_ 

173 

174 Returns 

175 ------- 

176 Vector 

177 _description_ 

178 """ 

179 _, r = self.euclidean_div(polynomial_a, polynomial_b) 

180 return r 

181 

182 def to_monic(self, polynomial: Vector) -> Vector: 

183 """_summary_ 

184 

185 Parameters 

186 ---------- 

187 polynomial : Vector 

188 _description_ 

189 

190 Returns 

191 ------- 

192 Vector 

193 _description_ 

194 """ 

195 leading_coeff: int = polynomial[self.deg(polynomial)] 

196 return self.reduce(modinv(leading_coeff, self.modulus) * polynomial) 

197 

198 def gcd(self, polynomial_a: Vector, polynomial_b: Vector) -> Vector: 

199 """_summary_ 

200 

201 Parameters 

202 ---------- 

203 polynomial_a : Vector 

204 _description_ 

205 polynomial_b : Vector 

206 _description_ 

207 

208 Returns 

209 ------- 

210 Vector 

211 _description_ 

212 """ 

213 r0 = self.reduce(polynomial_a) 

214 r1 = self.reduce(polynomial_b) 

215 if poly.deg(r1) > poly.deg(r0): 

216 r0, r1 = r1, r0 

217 

218 while not self.is_zero(r1): 

219 r0, r1 = r1, self.rem(r0, r1) 

220 

221 return r0 

222 

223 def eea(self, polynomial_a: Vector, polynomial_b: Vector): 

224 """_summary_ 

225 

226 Parameters 

227 ---------- 

228 polynomial_a : Vector 

229 _description_ 

230 polynomial_b : Vector 

231 _description_ 

232 

233 Returns 

234 ------- 

235 _type_ 

236 _description_ 

237 """ 

238 f0, f1 = self.reduce(polynomial_a), self.reduce(polynomial_b) 

239 a0, a1 = poly.monomial(1, 0), poly.zero_poly() 

240 b0, b1 = poly.zero_poly(), poly.monomial(1, 0) 

241 

242 while not self.is_zero(f1): 

243 q, r = self.euclidean_div(f0, f1) 

244 

245 f0, f1 = f1, r 

246 

247 a0, a1 = a1, self.sub(a0, self.mul(q, a1)) 

248 b0, b1 = b1, self.sub(b0, self.mul(q, b1)) 

249 

250 return f0, a0, b0 

251 

252 def coprime(self, polynomial_a: Vector, polynomial_b: Vector) -> bool: 

253 """_summary_ 

254 

255 Parameters 

256 ---------- 

257 polynomial_a : Vector 

258 _description_ 

259 polynomial_b : Vector 

260 _description_ 

261 

262 Returns 

263 ------- 

264 bool 

265 _description_ 

266 """ 

267 return all(self.to_monic(self.gcd(polynomial_a, polynomial_b)) == poly.monomial(1, 0))