Coverage for src\pqlattice\polynomial\_modpolyqring.py: 73%

1from ..integer._modring import mod, modinv 

2from ..typing import Vector, validate_aliases 

3from ._modpolyring import ModIntPolyRing 

4from ._poly import zero_poly 

5 

6 

7class ModIntPolyQuotientRing: 

8 @validate_aliases 

9 def __init__(self, poly_modulus: Vector, int_modulus: int) -> None: 

10 """_summary_ 

11 

12 Parameters 

13 ---------- 

14 poly_modulus : Vector 

15 _description_ 

16 int_modulus : int 

17 _description_ 

18 """ 

19 self.poly_modulus = poly_modulus 

20 self.int_modulus = int_modulus 

21 self.Zm = ModIntPolyRing(int_modulus) 

22 

23 @property 

24 def quotient(self) -> Vector: 

25 """_summary_ 

26 

27 Returns 

28 ------- 

29 Vector 

30 _description_ 

31 """ 

32 return self.poly_modulus 

33 

34 @validate_aliases 

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

36 """_summary_ 

37 

38 Parameters 

39 ---------- 

40 polynomial : Vector 

41 _description_ 

42 

43 Returns 

44 ------- 

45 Vector 

46 _description_ 

47 """ 

48 return self.Zm.rem(polynomial, self.poly_modulus) 

49 

50 @validate_aliases 

51 def center_lift(self, polynomial: Vector) -> Vector: 

52 """ 

53 Hoffstein page. 414 - 415 

54 

55 Parameters 

56 ---------- 

57 polynomial : Vector 

58 _description_ 

59 

60 Returns 

61 ------- 

62 Vector 

63 _description_ 

64 """ 

65 return mod(polynomial + self.int_modulus // 2, self.int_modulus) - self.int_modulus // 2 

66 

67 @validate_aliases 

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

69 """_summary_ 

70 

71 Parameters 

72 ---------- 

73 polynomial_a : Vector 

74 _description_ 

75 polynomial_b : Vector 

76 _description_ 

77 

78 Returns 

79 ------- 

80 Vector 

81 _description_ 

82 """ 

83 return self.reduce(self.Zm.add(polynomial_a, polynomial_b)) 

84 

85 @validate_aliases 

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

87 """_summary_ 

88 

89 Parameters 

90 ---------- 

91 polynomial_a : Vector 

92 _description_ 

93 polynomial_b : Vector 

94 _description_ 

95 

96 Returns 

97 ------- 

98 Vector 

99 _description_ 

100 """ 

101 return self.reduce(self.Zm.sub(polynomial_a, polynomial_b)) 

102 

103 @validate_aliases 

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

105 """_summary_ 

106 

107 Parameters 

108 ---------- 

109 polynomial_a : Vector 

110 _description_ 

111 polynomial_b : Vector 

112 _description_ 

113 

114 Returns 

115 ------- 

116 Vector 

117 _description_ 

118 """ 

119 return self.reduce(self.Zm.mul(polynomial_a, polynomial_b)) 

120 

121 @validate_aliases 

122 def inv(self, polynomial: Vector) -> Vector: 

123 """_summary_ 

124 

125 Parameters 

126 ---------- 

127 polynomial : Vector 

128 _description_ 

129 

130 Returns 

131 ------- 

132 Vector 

133 _description_ 

134 

135 Raises 

136 ------ 

137 ValueError 

138 _description_ 

139 """ 

140 if not self.Zm.coprime(polynomial, self.poly_modulus): 

141 raise ValueError("Inverse does not exists") 

142 

143 gcd, u, _ = self.Zm.eea(polynomial, self.poly_modulus) 

144 

145 c = modinv(gcd, self.int_modulus) 

146 

147 return self.reduce(u * c) 

148 

149 

150def construct_ring(p: str, N: int, q: int) -> ModIntPolyQuotientRing: 

151 """_summary_ 

152 

153 Parameters 

154 ---------- 

155 p : str 

156 _description_ 

157 N : int 

158 _description_ 

159 q : int 

160 _description_ 

161 

162 Returns 

163 ------- 

164 ModIntPolyQuotientRing 

165 _description_ 

166 

167 Raises 

168 ------ 

169 ValueError 

170 _description_ 

171 """ 

172 g = zero_poly(N) 

173 match p: 

174 case "-" | "X^N - 1": 

175 g[[0, N]] = -1, 1 

176 pass 

177 case "+" | "X^N + 1": 

178 g[[0, N]] = 1, 1 

179 pass 

180 case "prime" | "X^N - x - 1": 

181 g[[0, 1, N]] = -1, -1, 1 

182 case _: 

183 raise ValueError(f"Unknown symbol: {p}") 

184 

185 return ModIntPolyQuotientRing(g, q)