aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2025-06-23 11:21:11 +0200
committerSebastiano Tronto <sebastiano@tronto.net>2025-06-23 11:21:11 +0200
commitc07b47ee1a7aa3469753fa2ec49f3b499defac55 (patch)
treef75eaa5878a4b5ba5824dc6eceebb4ba3d6615f7
parent51bb82df499e35cdc13d33dd24eca85d7abd0aaf (diff)
downloadzmodn-rs-master.tar.gz
zmodn-rs-master.zip
FinalizedHEADmaster
Diffstat
-rw-r--r--README.md3
-rw-r--r--src/lib.rs83
2 files changed, 44 insertions, 42 deletions
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..6ea48d6
--- /dev/null
+++ b/README.md
@@ -0,0 +1,3 @@
1A small library for integers modulo n, similar to
2[zmodn](https://git.tronto.net/zmodn/file/README.md.html)
3but in Rust.
diff --git a/src/lib.rs b/src/lib.rs
index 6369b9f..2b0573a 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,20 +1,19 @@
1// TODO: make Zmod argument type generic
2// TODO: re-implement ECM?
3
4use std::fmt; 1use std::fmt;
5use std::ops; 2use std::ops;
6 3
4pub type BaseInt = i64;
5
7// We assume canonical representative, can compare value for PartialEq 6// We assume canonical representative, can compare value for PartialEq
8#[derive(Copy, Clone, Debug, PartialEq)] 7#[derive(Copy, Clone, Debug, PartialEq)]
9pub struct Zmod<const N: i64> { 8pub struct Zmod<const N: BaseInt> {
10 value: i64 9 value: BaseInt
11} 10}
12 11
13fn canonical_rep<const N: i64>(x: i64) -> i64 { 12fn canonical_rep<const N: BaseInt>(x: BaseInt) -> BaseInt {
14 return (x % N + N) % N; 13 return (x % N + N) % N;
15} 14}
16 15
17fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) { 16fn extended_gcd(a: BaseInt, b: BaseInt) -> (BaseInt, BaseInt, BaseInt) {
18 if b == 0 { 17 if b == 0 {
19 return (a, 1, 0); 18 return (a, 1, 0);
20 } 19 }
@@ -22,15 +21,15 @@ fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
22 (g, y, x - y*(a/b)) 21 (g, y, x - y*(a/b))
23} 22}
24 23
25impl<const N: i64> Zmod<N> { 24impl<const N: BaseInt> Zmod<N> {
26 pub fn from(x: i64) -> Zmod<N> { 25 pub fn from(x: BaseInt) -> Zmod<N> {
27 #[cfg(debug_assertions)] 26 #[cfg(debug_assertions)]
28 assert!(N > 1, "modulus must be greater than 1"); 27 assert!(N > 1, "modulus must be greater than 1");
29 28
30 Zmod::<N> { value: canonical_rep::<N>(x) } 29 Zmod::<N> { value: canonical_rep::<N>(x) }
31 } 30 }
32 31
33 fn inverse(self) -> Result<Zmod<N>, i64> { 32 fn inverse(self) -> Result<Zmod<N>, BaseInt> {
34 let (g, a, _) = extended_gcd(self.value, N); 33 let (g, a, _) = extended_gcd(self.value, N);
35 if g == 1 { 34 if g == 1 {
36 Ok(Zmod::<N>::from(a)) 35 Ok(Zmod::<N>::from(a))
@@ -40,13 +39,13 @@ impl<const N: i64> Zmod<N> {
40 } 39 }
41} 40}
42 41
43impl<const N: i64> fmt::Display for Zmod<N> { 42impl<const N: BaseInt> fmt::Display for Zmod<N> {
44 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 43 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
45 write!(f, "({} mod {})", self.value, N) 44 write!(f, "({} mod {})", self.value, N)
46 } 45 }
47} 46}
48 47
49impl<const N: i64> ops::Add for Zmod<N> { 48impl<const N: BaseInt> ops::Add for Zmod<N> {
50 type Output = Zmod<N>; 49 type Output = Zmod<N>;
51 50
52 fn add(self, z: Zmod<N>) -> Zmod<N> { 51 fn add(self, z: Zmod<N>) -> Zmod<N> {
@@ -54,15 +53,15 @@ impl<const N: i64> ops::Add for Zmod<N> {
54 } 53 }
55} 54}
56 55
57impl<const N: i64> ops::Add<i64> for Zmod<N> { 56impl<const N: BaseInt> ops::Add<BaseInt> for Zmod<N> {
58 type Output = Zmod<N>; 57 type Output = Zmod<N>;
59 58
60 fn add(self, z: i64) -> Zmod<N> { 59 fn add(self, z: BaseInt) -> Zmod<N> {
61 Zmod::<N>::from(self.value + z) 60 Zmod::<N>::from(self.value + z)
62 } 61 }
63} 62}
64 63
65impl<const N: i64> ops::Add<Zmod<N>> for i64 { 64impl<const N: BaseInt> ops::Add<Zmod<N>> for BaseInt {
66 type Output = Zmod::<N>; 65 type Output = Zmod::<N>;
67 66
68 fn add(self, z: Zmod::<N>) -> Zmod<N> { 67 fn add(self, z: Zmod::<N>) -> Zmod<N> {
@@ -70,19 +69,19 @@ impl<const N: i64> ops::Add<Zmod<N>> for i64 {
70 } 69 }
71} 70}
72 71
73impl<const N: i64> ops::AddAssign for Zmod<N> { 72impl<const N: BaseInt> ops::AddAssign for Zmod<N> {
74 fn add_assign(&mut self, z: Zmod<N>) { 73 fn add_assign(&mut self, z: Zmod<N>) {
75 self.value = canonical_rep::<N>(self.value + z.value); 74 self.value = canonical_rep::<N>(self.value + z.value);
76 } 75 }
77} 76}
78 77
79impl<const N: i64> ops::AddAssign<i64> for Zmod<N> { 78impl<const N: BaseInt> ops::AddAssign<BaseInt> for Zmod<N> {
80 fn add_assign(&mut self, z: i64) { 79 fn add_assign(&mut self, z: BaseInt) {
81 self.value = canonical_rep::<N>(self.value + z); 80 self.value = canonical_rep::<N>(self.value + z);
82 } 81 }
83} 82}
84 83
85impl<const N: i64> ops::Sub for Zmod<N> { 84impl<const N: BaseInt> ops::Sub for Zmod<N> {
86 type Output = Zmod<N>; 85 type Output = Zmod<N>;
87 86
88 fn sub(self, z: Zmod<N>) -> Zmod<N> { 87 fn sub(self, z: Zmod<N>) -> Zmod<N> {
@@ -90,15 +89,15 @@ impl<const N: i64> ops::Sub for Zmod<N> {
90 } 89 }
91} 90}
92 91
93impl<const N: i64> ops::Sub<i64> for Zmod<N> { 92impl<const N: BaseInt> ops::Sub<BaseInt> for Zmod<N> {
94 type Output = Zmod<N>; 93 type Output = Zmod<N>;
95 94
96 fn sub(self, z: i64) -> Zmod<N> { 95 fn sub(self, z: BaseInt) -> Zmod<N> {
97 Zmod::<N>::from(self.value - z) 96 Zmod::<N>::from(self.value - z)
98 } 97 }
99} 98}
100 99
101impl<const N: i64> ops::Sub<Zmod<N>> for i64 { 100impl<const N: BaseInt> ops::Sub<Zmod<N>> for BaseInt {
102 type Output = Zmod<N>; 101 type Output = Zmod<N>;
103 102
104 fn sub(self, z: Zmod<N>) -> Zmod<N> { 103 fn sub(self, z: Zmod<N>) -> Zmod<N> {
@@ -106,19 +105,19 @@ impl<const N: i64> ops::Sub<Zmod<N>> for i64 {
106 } 105 }
107} 106}
108 107
109impl<const N: i64> ops::SubAssign for Zmod<N> { 108impl<const N: BaseInt> ops::SubAssign for Zmod<N> {
110 fn sub_assign(&mut self, z: Zmod<N>) { 109 fn sub_assign(&mut self, z: Zmod<N>) {
111 self.value = canonical_rep::<N>(self.value - z.value); 110 self.value = canonical_rep::<N>(self.value - z.value);
112 } 111 }
113} 112}
114 113
115impl<const N: i64> ops::SubAssign<i64> for Zmod<N> { 114impl<const N: BaseInt> ops::SubAssign<BaseInt> for Zmod<N> {
116 fn sub_assign(&mut self, z: i64) { 115 fn sub_assign(&mut self, z: BaseInt) {
117 self.value = canonical_rep::<N>(self.value - z); 116 self.value = canonical_rep::<N>(self.value - z);
118 } 117 }
119} 118}
120 119
121impl<const N: i64> ops::Neg for Zmod<N> { 120impl<const N: BaseInt> ops::Neg for Zmod<N> {
122 type Output = Zmod<N>; 121 type Output = Zmod<N>;
123 122
124 fn neg(self) -> Zmod<N> { 123 fn neg(self) -> Zmod<N> {
@@ -126,7 +125,7 @@ impl<const N: i64> ops::Neg for Zmod<N> {
126 } 125 }
127} 126}
128 127
129impl<const N: i64> ops::Mul for Zmod<N> { 128impl<const N: BaseInt> ops::Mul for Zmod<N> {
130 type Output = Zmod<N>; 129 type Output = Zmod<N>;
131 130
132 fn mul(self, z: Zmod<N>) -> Zmod<N> { 131 fn mul(self, z: Zmod<N>) -> Zmod<N> {
@@ -134,15 +133,15 @@ impl<const N: i64> ops::Mul for Zmod<N> {
134 } 133 }
135} 134}
136 135
137impl<const N: i64> ops::Mul<i64> for Zmod<N> { 136impl<const N: BaseInt> ops::Mul<BaseInt> for Zmod<N> {
138 type Output = Zmod<N>; 137 type Output = Zmod<N>;
139 138
140 fn mul(self, z: i64) -> Zmod<N> { 139 fn mul(self, z: BaseInt) -> Zmod<N> {
141 Zmod::<N>::from(self.value * z) 140 Zmod::<N>::from(self.value * z)
142 } 141 }
143} 142}
144 143
145impl<const N: i64> ops::Mul<Zmod<N>> for i64 { 144impl<const N: BaseInt> ops::Mul<Zmod<N>> for BaseInt {
146 type Output = Zmod<N>; 145 type Output = Zmod<N>;
147 146
148 fn mul(self, z: Zmod<N>) -> Zmod<N> { 147 fn mul(self, z: Zmod<N>) -> Zmod<N> {
@@ -150,38 +149,38 @@ impl<const N: i64> ops::Mul<Zmod<N>> for i64 {
150 } 149 }
151} 150}
152 151
153impl<const N: i64> ops::MulAssign for Zmod<N> { 152impl<const N: BaseInt> ops::MulAssign for Zmod<N> {
154 fn mul_assign(&mut self, z: Zmod<N>) { 153 fn mul_assign(&mut self, z: Zmod<N>) {
155 self.value = canonical_rep::<N>(self.value * z.value); 154 self.value = canonical_rep::<N>(self.value * z.value);
156 } 155 }
157} 156}
158 157
159impl<const N: i64> ops::MulAssign<i64> for Zmod<N> { 158impl<const N: BaseInt> ops::MulAssign<BaseInt> for Zmod<N> {
160 fn mul_assign(&mut self, z: i64) { 159 fn mul_assign(&mut self, z: BaseInt) {
161 self.value = canonical_rep::<N>(self.value * z); 160 self.value = canonical_rep::<N>(self.value * z);
162 } 161 }
163} 162}
164 163
165impl<const N: i64> ops::Div for Zmod<N> { 164impl<const N: BaseInt> ops::Div for Zmod<N> {
166 type Output = Result<Zmod<N>, i64>; 165 type Output = Result<Zmod<N>, BaseInt>;
167 166
168 fn div(self, z: Zmod<N>) -> Result<Zmod<N>, i64> { 167 fn div(self, z: Zmod<N>) -> Result<Zmod<N>, BaseInt> {
169 Ok(self * z.inverse()?) 168 Ok(self * z.inverse()?)
170 } 169 }
171} 170}
172 171
173impl<const N: i64> ops::Div<i64> for Zmod<N> { 172impl<const N: BaseInt> ops::Div<BaseInt> for Zmod<N> {
174 type Output = Result<Zmod<N>, i64>; 173 type Output = Result<Zmod<N>, BaseInt>;
175 174
176 fn div(self, z: i64) -> Result<Zmod<N>, i64> { 175 fn div(self, z: BaseInt) -> Result<Zmod<N>, BaseInt> {
177 self / Zmod::<N>::from(z) 176 self / Zmod::<N>::from(z)
178 } 177 }
179} 178}
180 179
181impl<const N: i64> ops::Div<Zmod<N>> for i64 { 180impl<const N: BaseInt> ops::Div<Zmod<N>> for BaseInt {
182 type Output = Result<Zmod<N>, i64>; 181 type Output = Result<Zmod<N>, BaseInt>;
183 182
184 fn div(self, z: Zmod<N>) -> Result<Zmod<N>, i64> { 183 fn div(self, z: Zmod<N>) -> Result<Zmod<N>, BaseInt> {
185 Zmod::<N>::from(self) / z 184 Zmod::<N>::from(self) / z
186 } 185 }
187} 186}

Generated with cgit - Back to sebastiano.tronto.net