Coverage for src/pqlattice/integer/_modring.py: 84%

1from typing import overload 

2 

3from ..typing import Array 

4from ._integer import eea 

5 

6 

7@overload 

8def mod(a: int, modulus: int) -> int: ... 

9 

10 

11@overload 

12def mod(a: Array, modulus: int) -> Array: ... 

13 

14 

15def mod(a: int | Array, modulus: int) -> int | Array: 

16 """_summary_ 

17 

18 Parameters 

19 ---------- 

20 a : int | Array 

21 _description_ 

22 modulus : int 

23 _description_ 

24 

25 Returns 

26 ------- 

27 int | Array 

28 _description_ 

29 """ 

30 return a % abs(modulus) 

31 

32 

33@overload 

34def cmodl(a: int, modulus: int) -> int: ... 

35 

36 

37@overload 

38def cmodl(a: Array, modulus: int) -> Array: ... 

39 

40 

41def cmodl(a: int | Array, modulus: int) -> int | Array: 

42 """_summary_ 

43 

44 Parameters 

45 ---------- 

46 a : int | Array 

47 _description_ 

48 modulus : int 

49 _description_ 

50 

51 Returns 

52 ------- 

53 int | Array 

54 _description_ 

55 """ 

56 return mod(a, modulus) - modulus // 2 

57 

58 

59@overload 

60def cmodr(a: int, modulus: int) -> int: ... 

61 

62 

63@overload 

64def cmodr(a: Array, modulus: int) -> Array: ... 

65 

66 

67def cmodr(a: int | Array, modulus: int) -> int | Array: 

68 """_summary_ 

69 

70 Parameters 

71 ---------- 

72 a : int | Array 

73 _description_ 

74 modulus : int 

75 _description_ 

76 

77 Returns 

78 ------- 

79 int | Array 

80 _description_ 

81 """ 

82 return mod(a, modulus) - int(modulus / 2 - 0.1) 

83 

84 

85@overload 

86def modinv(a: int, modulus: int) -> int: ... 

87 

88 

89@overload 

90def modinv(a: Array, modulus: int) -> Array: ... 

91 

92 

93def modinv(a: int | Array, modulus: int) -> int | Array: 

94 """_summary_ 

95 

96 Parameters 

97 ---------- 

98 a : int | Array 

99 _description_ 

100 modulus : int 

101 _description_ 

102 

103 Returns 

104 ------- 

105 int | Array 

106 _description_ 

107 

108 Raises 

109 ------ 

110 ValueError 

111 _description_ 

112 ValueError 

113 _description_ 

114 """ 

115 if isinstance(a, int): 

116 if mod(a, modulus) == 0: 

117 raise ValueError(f"{a} mod {modulus} is zero; Modular inverse does not exist") 

118 gcd, a_inv, _ = eea(a, modulus) 

119 if gcd != 1: 

120 raise ValueError(f"Modular inverse of {a} mod {modulus} does not exist; gcd is equal to {gcd}") 

121 else: 

122 if (mod(a, modulus) == 0).all(): 

123 raise ValueError(f"{a} mod {modulus} is zero; Modular inverse does not exist") 

124 gcd, a_inv, _ = eea(a, modulus) 

125 if (gcd != 1).any(): 

126 raise ValueError(f"Modular inverse of {a} mod {modulus} does not exist; gcd is equal to {gcd}") 

127 

128 return mod(a_inv, modulus) 

129 

130 

131@overload 

132def modpow(a: Array, r: int, modulus: int) -> Array: ... 

133 

134 

135@overload 

136def modpow(a: int, r: int, modulus: int) -> int: ... 

137 

138 

139def modpow(a: int | Array, r: int, modulus: int) -> int | Array: 

140 """_summary_ 

141 

142 Parameters 

143 ---------- 

144 a : int | Array 

145 _description_ 

146 r : int 

147 _description_ 

148 modulus : int 

149 _description_ 

150 

151 Returns 

152 ------- 

153 int | Array 

154 _description_ 

155 """ 

156 if r < 0: 

157 return modpow(modinv(a, modulus), -r, modulus) 

158 

159 y, z = 1, a 

160 while r != 0: 

161 if r % 2 == 1: 

162 y = mod(y * z, modulus) 

163 r //= 2 

164 z = mod(z * z, modulus) 

165 return y