Coverage for src\pqlattice\integer\_modring.py: 100%
26 statements
« prev ^ index » next coverage.py v7.11.0, created at 2026-01-07 03:12 +0100
1from typing import overload
3from ..typing import Array
4from ._integer import eea
7@overload
8def mod(a: int, modulus: int) -> int: ...
11@overload
12def mod(a: Array, modulus: int) -> Array: ...
15def mod(a: int | Array, modulus: int) -> int | Array:
16 """_summary_
18 Parameters
19 ----------
20 a : int | Array
21 _description_
22 modulus : int
23 _description_
25 Returns
26 -------
27 int | Array
28 _description_
29 """
30 return a % abs(modulus)
33@overload
34def cmodl(a: int, modulus: int) -> int: ...
37@overload
38def cmodl(a: Array, modulus: int) -> Array: ...
41def cmodl(a: int | Array, modulus: int) -> int | Array:
42 """_summary_
44 Parameters
45 ----------
46 a : int | Array
47 _description_
48 modulus : int
49 _description_
51 Returns
52 -------
53 int | Array
54 _description_
55 """
56 return mod(a, modulus) - modulus // 2
59@overload
60def cmodr(a: int, modulus: int) -> int: ...
63@overload
64def cmodr(a: Array, modulus: int) -> Array: ...
67def cmodr(a: int | Array, modulus: int) -> int | Array:
68 """_summary_
70 Parameters
71 ----------
72 a : int | Array
73 _description_
74 modulus : int
75 _description_
77 Returns
78 -------
79 int | Array
80 _description_
81 """
82 return mod(a, modulus) - int(modulus / 2 - 0.1)
85@overload
86def modinv(a: int, modulus: int) -> int: ...
89@overload
90def modinv(a: Array, modulus: int) -> Array: ...
93def modinv(a: int | Array, modulus: int) -> int | Array:
94 """_summary_
96 Parameters
97 ----------
98 a : int | Array
99 _description_
100 modulus : int
101 _description_
103 Returns
104 -------
105 int | Array
106 _description_
108 Raises
109 ------
110 ValueError
111 _description_
112 ValueError
113 _description_
114 """
115 if mod(a, modulus) == 0:
116 raise ValueError(f"{a} mod {modulus} is zero; Modular inverse does not exist")
117 gcd, a_inv, _ = eea(a, modulus)
118 if gcd != 1:
119 raise ValueError(f"Modular inverse of {a} mod {modulus} does not exist; gcd is equal to {gcd}")
121 return mod(a_inv, modulus)
124@overload
125def modpow(a: Array, r: int, modulus: int) -> Array: ...
128@overload
129def modpow(a: int, r: int, modulus: int) -> int: ...
132def modpow(a: int | Array, r: int, modulus: int) -> int | Array:
133 """_summary_
135 Parameters
136 ----------
137 a : int | Array
138 _description_
139 r : int
140 _description_
141 modulus : int
142 _description_
144 Returns
145 -------
146 int | Array
147 _description_
148 """
149 if r < 0:
150 return modpow(modinv(a, modulus), -r, modulus)
152 y, z = 1, a
153 while r != 0:
154 if r % 2 == 1:
155 y = mod(y * z, modulus)
156 r //= 2
157 z = mod(z * z, modulus)
158 return y